Project Euler Problem 12

The sequence of triangle numbers is generated by adding the natural numbers. So the $7$^th triangle number would be $1 + 2 + 3 + 4 + 5 + 6 + 7 = 28$. The first ten terms would be:

$$1, 3, 6, 10, 15, 21, 28, 36, 45, 55, \dots$$

Let us list the factors of the first seven triangle numbers:

$$\begin{align} \mathbf 1 &\colon 1\\ \mathbf 3 &\colon 1,3\\ \mathbf 6 &\colon 1,2,3,6\\ \mathbf{10} &\colon 1,2,5,10\\ \mathbf{15} &\colon 1,3,5,15\\ \mathbf{21} &\colon 1,3,7,21\\ \mathbf{28} &\colon 1,2,4,7,14,28 \end{align}$$

We can see that $28$ is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

First we need a decent method of counting the number of divisors an integer $n$ has. We can do this by testing if each integer from 1 to n is a divisor. But we don't have to test each integer. If $i$ is a divisor of $n$ then $n/i$ is also a divisor of $n$. So we can just search from 1 to $\operatorname{isqrt}(n)$. Instead of storing all divisors in an array, we can just count them directly to avoid memory allocations.

function num_divisors(n)
    count = 0
    sqrt_n = isqrt(n)

    for i in 1:sqrt_n
        if n % i == 0
            count += 2
        end
    end

    if sqrt_n^2 == n
        count -= 1
    end

    return count
end

The $n^\text{th}$ triangle number can be computed as

and we can call num_divisors on each triangle number until we find one with enough divisors, but $T_n$ grows quadratically so this can take a while.

Instead we can rely on the fact that if two integers $a$ and $b$ are coprime, that is $\operatorname{gcd}(a, b) = 1$, then the number of divisors of their product equals the product of their divisor counts: $d(ab) = d(a) \times d(b)$.

It is also useful to know that consecutive integers are always coprime.

To get coprime integers out of $T_n$ we notice that $n$ and $n+1$ must be coprime because they are consecutive integers. Now, one of them must be even. Dividing an even number by 2 doesn't introduce any common factors with the other number since the odd number has no factor of 2 to begin with.

So when $n$ is even, $n/2$ and $n+1$ are coprime, and the number of divisors of $T_n$ is the product of the number of divisors of $n/2$ and $n+1$. Similarly, when $n$ is odd, $n$ and $(n+1)/2$ are coprime. So in both cases we can find the number of divisors of much smaller numbers and multiply them.

We can write

and implement a solution as

function find_first_triangle_with_divisors(min_divisors)
    n = 1

    while true
        if n % 2 == 0
            # T(n) = (n/2)*(n+1) if n is even
            a = n ÷ 2
            b = n + 1
        else
            # T(n) = n*(n+1)/2 if n is odd
            a = n
            b = (n + 1) ÷ 2
        end

        total_divisors = num_divisors(a) * num_divisors(b)

        if total_divisors > min_divisors
            return n, triangle_number(n)
        end

        n += 1
    end
end

This lets us compute the first triangle number to have over 500 divisors in 2.166 ms.

It also lets us compute $T_{41040} = 842161320$ as the first triangle number to have over 1000 divisors in 12.882 ms, and $T_{313599} = 49172323200$ as the first triangle to have over 2000 divisors in 282.720 ms.