# 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