Project Euler-Problem 21

Description

From Project Euler:

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 ≠ 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.

Solution

This problem is best broken down into steps. The first thing we need is an easy way to get the proper divisors of a number.

def divisors(n)
  return [] if n <=1
  limit = Math.sqrt(n).floor
  (2..limit).select { |d| n % d == 0 }.inject([1]) do |result,d|
    result << n << n / d
  end.uniq
end

This method is fairly complex for a change, so we’ll break it down. First, we exit fast with an empty set if the number is less than or equal to one. Notice that since a proper divisor must be less than the number, one has no proper divisors.

Next, we figure out what the square root of the number n is. This gives us a good cutoff, since if we add the divisors in pairs, by the time we reach limit we will already have added all the values greater than limit. With this number in hand, we can iterate through the entire range from 2 to limit and select only the numbers that divide evenly into n.

We will create an array by beginning with [1] (remember, n is not a proper divisor of itself, so 1 has no pair and must be added manually). We then proceed to add each divisor to result in pairs, the current divisor and it’s matching dividend above limit.

There is one more thing we have to take into account. If n is a perfect square, then it will have a divisor equal to limit. This divisor will actually be added twice (once as a divisor and once as a dividend). There is a number of ways we could correct this, but I found it easiest to just ask Ruby to return the unique results.

The next method we will need is to test if a number is amicable or not. For this, I've decided to implement a method that will return the other amicable number in a pair, or nil if no such number exists.

# extracted summing proper divisors
def dsum(n)
  divisors(n).reduce(0, :+)
end

def amicable_pair(n)
  pair = dsum(n)
  pair if dsum(pair) == n and pair != n
end

The last thing to do is find all of the amicable numbers from 1 to 10,000. We can use the fact that select will treat nil as false when querying an Enumerable and just call amicable_pair on each value. Then just sum up the results and we are done.

(1..10_000).select { |n| amicable_pair(n) }.reduce(0, :+)

The full source and specifications can be seen on github. Next time, what is the total of all the name scores in a given file of first names?