Also known as Project Euler Problem 12.
This is the first one that has proved to be a bit of a challenge for me, and one that forced me both to do a bit of research and to take a look at the efficiency of some of my functions.
First 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, …
Let us list the factors of the first seven triangle numbers:
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?
Obviously a brute-force approach is not going to work in this case. Since I already had a function for generating prime factors, which I developed for Problem 3, I started thinking about whether it was possible to calculate the total number of divisors of a number based on its prime factors.
The factorisation of a number can be expressed as: P1^F1 * P2^F2 * … * Pn^Fn
And the total number of divisors is: (F1 +1) * (F2 + 1) * … * (Fn + 1)
For example, 28 can be expressed as 2^2 * 7^1 so the total number of divisors is (2 + 1) * (1 + 1) = 6
Or, 36 = 2^2 * 3^2 so the total number of divisors is 3*3 = 9.
Coding this formula was pretty straightforward. Unfortunately, the resulting program ground to a halt once I started looking for more than 200 divisors – and this has had me stumped for a couple of days. I knew my reasoning was sound and I could see the program generating correct results for small numbers of divisors, but I could not figure out why it didn’t scale.
It wasn’t until I went back to look at the efficiency of my factorisation function that the following insight hit me: You don’t need to test whether a number is prime if you can guarantee that your loop will only look at prime mumbers.
This insight resulted in the following, much more efficient, function:
def Factorise(integer): factors= index = 2 while integer > 1: if integer % index == 0: factors.append(index) integer=integer/index else: index += 1 return factors
Starting with an index of 2 (the lowest prime) I simply divide the integer by the index until I get a non integer result. Then I increment the index and start again.
Because the function repeatedly divides out each factor, integer/index can only return an integer result if index is prime.
With this approach, I was able to solve the problem in about half a second.