Project Euler Problem 12

Project Euler Problem 12

Solution

Answer: 76576500

We seek the first triangle number with more than $500$ divisors.

A triangle number is

$$T_n=\frac{n(n+1)}{2}$$

Since $n$ and $n+1$ are coprime, we can factor them separately and compute the divisor count efficiently.

The number of divisors of an integer with prime factorization

$$p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$$

is

$$(a_1+1)(a_2+1)\cdots(a_k+1)$$

So for each triangle number $T_n$, we:

1. Compute $T_n=n(n+1)/2$
2. Prime-factorize it
3. Compute the divisor count
4. Stop once the count exceeds $500$

Python code:

from math import isqrt

def divisor_count(n):
    count = 1
    d = 2

    while d * d <= n:
        exp = 0
        while n % d == 0:
            n //= d
            exp += 1
        if exp:
            count *= (exp + 1)
        d += 1

    if n > 1:
        count *= 2

    return count

triangle = 0
n = 1

while True:
    triangle += n

    if divisor_count(triangle) > 500:
        print(triangle)
        break

    n += 1

Tracing the computation eventually reaches:

• $T_{12375} = 76576500$

Its divisor count is $576$, which is the first triangle number exceeding $500$ divisors.

Answer: 76576500