WARNING: The text below provides a guidance for a Project Euler problem.

  • If you pride yourself in tackling problems entirely on your own, you are encouraged to exit this post right now.

  • If you are simply looking for a hint for the problem, please visit the »Project Euler’s official forum«. You may find some hints here, but if you don’t want your problem spoiled, scroll cautiously.

  • If you are looking for a readily available copy/paste answer, you will not find it here. All of the code snippets in the post have been stripped of some crucial lines (these are clearly marked). It is my aim that anyone able to replicate the answer based on such snippets will have to understand the solution conceptually. At that point, by virtue of learning something new, I believe he deserves it anyway.

  • Guidance for future problems will not be published before 100 people have solved the problem and there are at least two more recent problems.

Expressing an integer as the sum of triangular numbers

The problem tasks us with computing the function expressing the number of ordered ways to write as a sum of three triangular numbers. Triangular numbers are numbers of the form .

We can readily convert the problem into somehow better looking equivalent. We can see that expressing as a sum of three triangular numbers is equivalent to expressing as a sum of three odd positive squares:

We thus have where is the sum of (k) squares function (tweaked such that the order of squares matters).

def sum_of_three_triangles(n):
    return sum_of_three_squares(8*n+3)

To compute we will use its obvious relation to (a simpler) . If we manage to compute fast enough, this will be sufficient for the problem constraints. \[r_3(n) = \sum_{k = 1}^{\lfloor \sqrt n \rfloor} r_2(n - k^2)\]

def sum_of_three_squares(n):
    return sum(sum_of_two_squares(n - k*k) for k in # <REMOVED>

The formula for is standard enough to be found in most Number theory textbooks. Writing the prime factorization of as \[ n = 2^\gamma \prod_{p \equiv 1 \text{ mod } 4} p^{\alpha_p} \prod_{q \equiv 3 \text{ mod } 4} q^{\beta_q}, \] we have

Notice that if then necessarily some of the must be odd, which accounts for a speedup in our function. Also, we take advantage of the binary representation of numbers and use instead of .

def sum_of_two_squares(n):
    if n <= 1: return 0
    # we do not care about the factors of 2
    # <REMOVED>
    if (n&3) == 3: return 0

    product = 1  # factorize
    for prime in PRIMES:
        if square[prime] > n:
        exp = 0
        while n % prime == 0:
            exp += 1
            n //= prime
        if # < REMOVED >
            return 0
        if (prime&3) == 1:
            product *= exp + 1
    if n > 1:
        product *= 2
    return product

For the value as required by the problem, this is unfortunately way too slow. Luckily, some time of researching1 has brought fruit in form of the recurrence which is very suitable for the problem input. We modify the “sum_of_three_squares” function accordingly.

def sum_of_three_squares(n):
    lamb = 0
    while n % 9 == 0:
        lamb += 1
        # <REMOVED>
    if lamb > 0:
        if n % 24 == 11:
            return 3**lamb * sum_of_three_squares(n)
        if n % 24 == 19:
            return (2 * 3**lamb - 1) * sum_of_three_squares(n)
        if n % 72 in [3, 51]:
            return (3**(lamb + 1) - 1) * sum_of_three_squares(n) // 2
    return # <REMOVED>

Altogether, the code runs in 5 seconds, where the prime sieving takes by far the most time.

  1. Michael D. Hirschhorn and James A. Sellers. ON REPRESENTATIONS OF A NUMBER AS A SUM OF THREE TRIANGLES. Acta Arithmetica 77 (1996), 289 - 301