Thursday, August 26, 2010

Project Euler : What is the value of the first triangle number to have over five hundred divisors?

Problem 12

The sequence of triangle numbers is generated by adding the natural numbers. So the 7^(th) 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?


Solution (in Ruby)

The main aspect about this solution is finding an efficient way to calculate the number of divisors. Lets take a simple example. The number 6 has 4 divisors namely 1,2,3,6. For this number its enough we run upto the Square root of 6 which is integer floored value to be 2. 1 is divisible by 6 by 6 times, so 1 and 6 are divisors. 2 is divisble by 6 3 times, so 2 and 3 are divisors. So totally we have 4 divisors.
There is one more point to be noted here. For a square number such as 16, if we apply this formula, we will end up getting 6 divisors --> 1, 2, 4, 4, 8, 16. You may see we may calculate 4 twice. But it occurs only once for a square number. This special case is handled in the solution given below. The rest is an as-is implementation of the problem statement.

def divisors_count(n)
  return 1 if n==1
  count = 0
  1.upto(Math.sqrt(n)) do |x|
    if n%x == 0
      count+=1 unless n.to_f/x == x
      count+=1
    end
  end
  count
end

INFINITY = 1.0/0.0
1.upto(INFINITY) do |n|
  if divisors_count(n*(n+1)/2) > 500
    puts "The first triangle number to have over 500 divisors is #{n*(n+1)/2}"
    break
  end
end

Hover here to see the solution

Cheers!!
Bragaadeesh.

No comments: