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?
My solution in Ruby:
def calc_divisors(num) res= 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.