The sequence of triangle numbers is generated by adding the natural numbers. So the 7th 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, …
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?
Our algorithm for solving this one was improved nicely by a detailed explanation provided by a Project Euler moderator named ‘rayfil’. His wonderful explanation is published as a PDF document that is available after you solve the problem. What follows is our own interpretation written in Python.
Runs < 1 second in Python.
from Euler import factor def D(n): nf = 1 for exp in factor(n): nf*=exp+1 return nf limit=500 for n in range(5,100000): t = n*(n+1)/2 if n%2==0: Dt = D(n/2)*D(n+1) else: Dt = D(n)*D((n+1)/2) if Dt>limit: break print "Answer to PE12 =",t,"(",Dt,"factors)"
- More information on the Euler module can be found on the tools page.
- We opted for the
forloop with some high limit instead of a
whileloop because a future problem may ask for a limit much higher than 500. Using a binary search a limit of 5*10^15 would only take a faction of a second to calculate.