// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (13 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

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?

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
This program and method
solves all test cases for
Project Euler 12 on HackerRank

Project Euler 12 Solution

Runs < 0.017 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

    No afterthoughts yet.
Project Euler 12 Solution last updated

Discussion

3 Responses to “Project Euler 12 Solution”

  1. Would the factors for the number: 14414400 be 504?

    Posted by pete | October 26, 2017, 10:29 AM
  2. Wicked fast! Best solution I have seen for this problem.

    Posted by Mark | September 13, 2017, 10:12 AM

Post a comment