Euler Problem 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?

On first glance, this sounds rather similar to problem 3 which asked about prime factors:

def listfactors( value )
	list = []
	factor = 2
	while factor <= Math.sqrt(value) do
		if( value % factor == 0 )
			list << factor 
			value /= factor
		else
			factor = factor + 1
		end
	end
	list << value
	return list
end

Divisors are a little different from prime factors though, we’ll need to find every number that divides evenly into one of our triangle numbers (including 1 and the number itself).

A straightforward approach would be simply to iterate through all the numbers less than the triangle number to see which divide in evenly, but that sounds like a lot of work. Instead, I decided to generate divisors from the list of factors.

We can do this because the divisors of any number are always: 1, the number, all the prime factors, all combinations of the prime factors that multiply to less than the number. (Of course we have to make sure every element in the list is unique since our prime factors list often contains multiple instances of a factor.) So given the factors list, our code looks like the following:

def listdivisors( value )
	divisors = [1,value]
	factors = listfactors(value)
	n = factors.count - 1
	while n > 0 do
		factors.combination(n){ |combo|
			divisors << combo.reduce(:*)
		}
		n -= 1
	end
	return divisors.uniq
end

Now all that’s left is to generate the triangle numbers and find their divisors. A generator for triangle numbers is pretty simple:

def triangle_gen()
	return  Generator.new { |g| 
		n = 1
		tri = 0
		while 1 do
			tri += n
			g.yield tri
			n += 1
		end
	}
end

And iterating until we find one that generates more than 500 divisors is pretty easy too:

g = triangle_gen()
length = 0
while length < 500 do
	n = g.next
	length = listdivisors(n).count
end
puts n

Is there any way to speed this up? Probably, since we don’t actually care about what the divisors are, just their quantity we shouldn’t actually need to generate them, we could just calculate the number of divisors we expect based on the number of prime factors. If there are no duplicate prime factors, the calculation is trivial (The sum of n choose k for all 0 <= k <= n is 2^n .), but the effect of repeated prime factors confounds the problem a bit, possibly negating the savings (something interesting to calculate in the future).


About this entry