// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (9 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 12 Solution

Project Euler 12 Solution

Project Euler 12: Find the value of the first triangle number to have over five hundred divisors


Project Euler 12 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.

If you run the Trinket for an input of 500 it will take about 15 seconds to run.

Project Euler 12 Solution

Runs < 0.113 seconds in Python 2.7.
download arrowUse this link to get the Project Euler 12 Solution Python 2.7 source.

Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
|76576500|

Afterthoughts

  • This is the second incarnation of this solution, the first taking longer and more complicated to understand. This version also passes all the HackerRank test problems.
Project Euler 12 Solution last updated

Discussion

2 Responses to “Project Euler 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

Post a comment