«
»

Project Euler Problem 21 (Ruby)

If you intend to solve the problem on your own, I wouldn’t recommend reading any further.

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a \neq b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

(Problem 21 – Project Euler) 

def d(n)
  total = 0
  1.upto n/2 do |i|
    if (n % i) == 0
      total += i
    end  
  end
  total
end
 
amicable_sum = 0
 
10000.times do |a|
  b = d(a)
  if d(b) == a && b > a
    amicable_sum += a + b
  end
end
 
puts amicable_sum

My version of d(n) isn’t as efficient as the one in the PDF you get after solving the problem, but it gets the job done.

Running it takes around 8.5 seconds on my machine. That’s not too bad for ~20 lines of code.

Tags: , ,

This entry was posted on Thursday, September 24th, 2009 at 10:27 pm and is filed under Ruby. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Leave a Reply