Project Euler 12: Find the value of the first triangle number to have over five hundred divisors
Project Euler 12 Problem Description
Project Euler 12: 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:
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
This problem sounds simple enough, but it is somewhat dastardly in getting results both quicky and correctly. The premise is to query triangular numbers (recall problem 1) and find the first one to have more than 500 divisors.
Our algorithm for solving this one was markedly improved by a detailed explanation provided by a Project Euler moderator named ‘rayfil’. Yet it still wasn’t fast enough to handle the more challenging hackerRank Project Euler 12 version with finding a triangle number with 1,000 divisors and 10 consecutive trials.
To solve, we sieve the number of divisors as we check each candidate for being a triangular number. The result was being able to solve for 5000 divisors in less than 10 seconds. Now, one may question the somewhat arbitrary value for n=4200. It’s a cap on the potential triangular number index search used to tune the algorithm for performance. It could be set to some other high value to accommodate deeper investigations.
Project Euler 12 Solution
Runs < 0.017 seconds in Python 2.7.
Use this link to get the Project Euler 12 Solution Python 2.7 source.
Afterthoughts
-
No afterthoughts yet.
Would the factors for the number: 14414400 be 504?
Posted by pete | October 26, 2017, 10:29 AMWicked fast! Best solution I have seen for this problem.
Posted by Mark | September 13, 2017, 10:12 AM