Project Euler Problem 12: Highly Divisible Triangular Number

The source code for this problem can be found here.

Problem Statement

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{split} 1&: 1 \\ 3&: 1,3 \\ 6&: 1,2,3,6 \\ 10&: 1,2,5,10 \\ 15&: 1,3,5,15 \\ 21&: 1,3,7,21 \\ 28&: 1,2,4,7,14,28\end{split}\]

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 Discussion

This solution uses a sieve to incrementally build up the count of divisors \(d(x)\) for all \(x\) up to some pre-determined upper-bound. With this sieve, the problem is easily solvable.

All triangle numbers are of the form:
\(T_n = 1 + 2 + \dots + n\)
which can be re-expressed in the closed form:
\(T_n = \frac{n \times (n + 1)}{2}\)

Importantly, this expression can be de-composed into pair-wise co-prime components.

Case (\(n\) is even):
\(T_n = \frac{n}{2} \times (n + 1)\)
Case (\(n\) is odd):
\(T_n = n \times (\frac{n + 1}{2})\)

It should be easy to see that only one term in each case is divisible by \(2\), so prior to dividing out by \(2\) we have:

  • (\(n\) is even) n and (n + 1)
  • (\(n\) is odd) n and (n + 1)

Clearly, \(n\) and \((n + 1)\) are co-prime, therefore, the two terms in each case are pair-wise co-prime.

Since these terms are co-prime, the number of divisors in \(T_n\) can be determined by the number of divisors in each term.

\[\begin{split}d(T_n) &= d \bigg(n \times \frac{n + 1}{2} \bigg) & \\ &= d(n) \times d \bigg(\frac{n + 1}{2} \bigg) & \; \; \; \mbox{(if n is odd)} \\ &= d \bigg(\frac{n}{2} \bigg) \times d(n + 1) & \; \; \; \mbox{(if n is even)}\end{split}\]

So, the overall solution is to build a sieve on the number of divisors in the range \(n=1,\dots,answer\)

Finally, we may set a reasonable upper-bound on \(answer\) by applying the following:

\[\begin{split}& d(answer) \lt 2 \times \sqrt{answer} \mbox{ and } d(answer) \gt 500 \\ & \Rightarrow 500 \lt d(answer) \lt 2 \times \sqrt{answer} \\ & \Rightarrow \frac{500}{2} \lt \sqrt{answer} \\ & \Rightarrow 250 \lt \sqrt{answer} \\ & \Rightarrow \sqrt{answer} \gt 250 \\ & \Rightarrow answer \gt 250^2\end{split}\]

While this range will be sufficient, it may be excessive. This algorithm computes the solution quickly enough so I won’t investigate a tighter bound on \(n\).

Solution Implementation

from lib.numbertheory import divisors_sieve, is_even


def solve():
    """ Compute the answer to Project Euler's problem #12 """

    target = 500  # target number of divisors
    limit = (target // 2) ** 2  # search limit for the sieve

    # Build the number of divisors sieve
    divisors = divisors_sieve(limit, proper=False, aggregate="count")
    sieve = {n + 1: divisors_count for n, divisors_count in enumerate(divisors)}

    # Search through the sieve for the first T_n exceeding the targeted number of divisors
    answer = None
    for n in range(1, limit - 1):
        if is_even(n):
            n_divisors = sieve[n // 2] * sieve[n + 1]
        else:
            n_divisors = sieve[n] * sieve[(n + 1) // 2]
        if n_divisors > target:
            answer = n * (n + 1) // 2
            break

    return answer


expected_answer = 76576500
solutions.problem12.solve()

Compute the answer to Project Euler’s problem #12