Project Euler Problem 12 deals with factorization, so it’s important to get a pretty efficient function to do that. The problem reads:
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?
So, I created a “factor” function that returns all the factors of a given number. I’ll save you the trouble of finding it later, and let you know that this is a useful function (for Euler) that should be put in your re-usable toolbelt–in my case, euler.py.
Here’s my most efficient example:
def factorize(num):
factors = [1, num]
for i in range(2, int(math.sqrt(num))+ 1):
if not num % i:
factors.append(i)
factors.append(num / i)
return list(set(factors))
So we fill the list with 1 and the number, and then check remainders with modulus (%) for all the other numbers up to the square root. That’s as far as we have to go, and we’ll use 36 as an example to see why:
start with [1, 36]
check 2, find [2, 18]
check 3, find [3, 12]
check 4, find [4, 9]
check 5, fail
check 6, find [6]
Done.
So even though we only went to six, we were able to get 9, 12, and 18–numbers greater than six. Any number greater than six will have a corresponding factor lower than six, so for max efficiency we don’t go any higher.
Moving on, it’s now a fairly simple matter to check each triangle number for X number of factors, in this case 500.
First, I imported my factorization function:
from euler import factors
Then I made a function to find the first (triangle) number with X number of factors:
def first_triangle_with_divisors(num):
'''
Find the first triangle number with
at least num number of divisors
'''
count = 1
triangle = 1
factor_count = 0
while factor_count < num:
count += 1
triangle += count
factor_count = len(factors(triangle))
return (triangle, factor_count)
Walking through it, we start with
so we can determine the next number that has to be added–it allows us to make the triangle number sequence. We set
…our first triangle number. And then we set up a spot for the factor_count, so that we can set up a while loop with it.
The loop will iterate until
…with num being an argument the function accepts. We could hard-code this to 500, but I set it as a variable so that I can run the known case (28 is the first number with > 5 factors) to verify working code.
This code fails in one case, if you input 1 for num. It’s trivial to fix, but doesn’t matter for our application. To fix it you would just insert, at the beginning of the function:
if num == 1:
return (1, 1)
During each loop, we increase our count, and then add it to the previous triangle number to get the new one. Then we call our factors() function on the new number, which returns a list of factors. We count them with len() and only finish if they’re over our target.
The end of my file just has a couple of cases:
print first_triangle_with_divisors(1)
print first_triangle_with_divisors(6)
print first_triangle_with_divisors(500)
And returns the correct answer.
We can speed the function for large numbers. It’s hard to be perfect, and probably harder to prove mathematically, but it makes a lot of sense that the first number with 500 divisors is probably divisible by both 2 and 3, and possibly 5 which will give it a lot of “extra” divisors.
On my machine this runs in about 10 seconds, and it’s cut fairly drastically by including an extra line:
while factor_count < num:
count += 1
triangle += count
if num < 100 or num > 100 and not triangle % 2 and not triangle % 3:
factor_count = len(factors(triangle))
return (triangle, factor_count)
This simply means we’ll skip our most time-sinking function, factors(), if we need a high number of factors and the triangle is not evenly divisible by 2 and 3. This ONLY works if you need the FIRST number that qualifies, because you will eventually run into a number, I think, with 500+ divisors that is not evenly divisible by 2 or 3.
Of note:
Do some research on whitespace. I had an invisible error, to the naked eye, that cost me an hour of frustrating debugging–my factor function was exiting early and I couldn’t figure out why. Some weird whitespace accident with Vim, my editor of choice.