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:
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.
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:
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