Problem 12: Highly Divisible Triangular Number

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?

Solution Approach

Here, we can use a few clever tricks involving properties of triangular numbers and prime factorisation. We can also use our Sieve of Eratosthenes from Problem 7 and Problem 10.

The $n$^th triangular number is given by: $$T_n = \frac{n(n+1)}{2}$$ Since $n$ and $n+1$ are consecutive integers, one of them must be even. Therefore, either $\frac{n}{2}$ or $\frac{n+1}{2}$ is an integer, making it convenient to factorise.

Trick 1 — Splitting into Two Coprime Parts

Because $n$ and $n+1$ are consecutive, they are coprime (no common prime factors).

Thus, the total number of divisors of their product is simply the product of their divisor counts:

Let $d(k)$ be the number of divisors of $k$. Then:

$$d(T_n) = d\left(\frac{n}{2}\right) \cdot d(n+1) \quad \text{(if $n$ is even)}$$ $$d(T_n) = d(n) \cdot d\left(\frac{n+1}{2}\right) \quad \text{(if $n$ is odd)}$$ This is a key simplification — instead of factoring $T_n$ directly, we can factor two much smaller numbers.

Trick 2 — Counting Divisors via Prime Factorisation

If a number $N$ can be expressed as a product of primes: $$N = p_1^{a_1} \cdot p_2^{a_2} \cdot \dots \cdot p_k^{a_k}$$ then the number of divisors of $N$ is: $$d(N) = (a_1 + 1)(a_2 + 1)\dots(a_k + 1)$$ This follows because each exponent $a_i$ represents how many times that prime can appear in a divisor (from $0$ to $a_i$).

Combining both tricks, we can efficiently calculate $d(T_n)$ without directly factoring huge triangular numbers.

In terms of python:


limit = 1000000 # as a safe upper bound, increase if needed.
sieve = [True] * limit
sieve[0:2] = [False, False]
for i in range(2, int(limit ** 0.5) + 1):
    if sieve[i]:
        sieve[i*i:limit:i] = [False] * len(range(i*i, limit, i))
primes = [i for i, is_prime in enumerate(sieve) if is_prime]


def count_divisors(n, primes):
    temp = n
    div_count = 1
    for p in primes:
        if p * p > temp:
            break
        power = 0
        while temp % p == 0:
            temp //= p
            power += 1
        if power:
            div_count *= (power + 1)
    if temp > 1:
        div_count *= 2
    return div_count


n = 1
while True:
    if n % 2 == 0:
        a = n // 2
        b = n + 1
    else:
        a = n
        b = (n + 1) // 2

    total_divs = count_divisors(a, primes) * count_divisors(b, primes)

    if total_divs > 500:
        print(n * (n + 1) // 2)
        break

    n += 1

Explained line by line:

We set a variable limit to one million, which is a safe upper bound for our sieve to generate prime numbers.
We create a list called sieve initialized to True, indicating that all numbers are initially assumed to be prime. We set the first two entries (0 and 1) to False since they are not prime.
We then iterate through each number starting from 2 up to the square root of the limit. For each prime number found, we mark all its multiples as False (not prime).
After constructing the sieve, we create a list of all indices that are still marked as True, which correspond to prime numbers.
We define a function count_divisors that takes a number n and the list of primes, and returns the count of divisors of n using prime factorisation.
We initialize n to 1 and enter an infinite loop to find the first triangular number with over 500 divisors.
Inside the loop, we check if n is even or odd to determine how to split the triangular number into two coprime parts a and b.
We calculate the total number of divisors of the triangular number by multiplying the divisor counts of a and b using the count_divisors function.
If the total number of divisors exceeds 500, we print the triangular number and break the loop.
If not, we increment n and repeat the process.

Running the above code leads to an answer of $76576500$