(No Ratings Yet)

## Project Euler Problem 12 Solution

#### Problem Description

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:

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

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?

#### Analysis

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

#### Solution

Runs < 1 second in Python.

```from Euler import factor   def D(n): nf = 1 for exp in factor(n): nf*=exp[1]+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 `for` loop with some high limit instead of a `while` loop 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.

## Discussion

### 2 Responses to “Project Euler Problem 12 Solution”

1. You say “euler’s amazing algorithm” — what algorithm is this?

nice solution and excuse me for asking but what is the algorithm you use? or is it combination of things?

thank you

Posted by larry | September 7, 2009, 4:52 AM
• Hi Larry. It’s been quite some time since we solved this one but as I recall our solution was improved by some comments made by Euler, the Project Euler moderator and not Leonhard Euler the 18th century mathematician. I will edit this post to make that clear.

Thank you for you comment and consideration.

Posted by Mike | September 9, 2009, 12:43 PM