Project Euler Problem 12 Solution

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?

My solution in Ruby:

def calc_divisors(num)
  res=[1]
  2.upto(Math.sqrt(num).floor) do |i|
    if num % i == 0
      res << i
    end
  end
  res.reverse.each do |i|
    res << num / i
  end
  res.uniq
end

triangle = 0
count = 0
while calc_divisors(triangle).count < 500
  count += 1
  triangle += count
end
puts triangle

This code takes a little while to run, and so far, this is my favourite Project Euler Solution. I did originally try brute-forcing the divisors for each number, but as you can imagine, testing half of every possible candidate for numbers in the millions meant that the loops were getting too long. Interestingly, I never let that original method find the answer so instead I hit google, looking for a faster way. I discovered a lot about sieves and old math geniuses, but the the best example I found was using prime factorials. The function ‘calc_divisors’ in the above code seems to be the fastest way I could find to determine the factors of a specified Integer. If you think there is a faster way, I’d be interested to hear.

Leave a Reply

Your email address will not be published. Required fields are marked *