Posts tagged mathematics

Two days ago I had been looking at re-playing with Project Euler problems, after I solved a few of them last time (quite some time ago). I looked at the problem list, and decided to try solve the top-most unsolved problem I have: Problem 12. I managed to come up with a brute-force code that calculated the answer in about 403 ms on an Intel Core2 Duo T9600 @ 2.80GHz machine.

Understanding the problem

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, …

Given the example, I guess the mathematical function explanation of the triangle numbers would be something along this line: f(n) –> 1+2+3+…+n where n=1, 2, 3, …

We are then required to come up with something to find the first triangle number to have over 500 divisors. In clearer words, we are required to find the first triangle number to have 501 divisors, within one minute, complying to the Project Euler’s one-minute rule:

I’ve written my program but should it take days to get to the answer?

Absolutely not! Each problem has been designed according to a “one-minute rule”, which means that although it may take several hours to design a successful algorithm with more difficult problems, an efficient implementation will allow a solution to be obtained on a modestly powered computer in less than one minute.

Spoiler alert! Read on to know my solution to this problem >