Project Euler 12 Problem Statement

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:

 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?

Solution

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.

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.

HackerRank version

HackerRank Project Euler 12 runs 10 test cases and raises the number of divisors from 500 to 1000.

Python 2.7 Source

Last Word