#### Description

From Project Euler:

Let d(

n) be defined as the sum of proper divisors ofn(numbers less thannwhich divide evenly inton).

If d(a) =band d(b) =a, wherea≠b, thenaandbare an amicable pair and each ofaandbare 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 `uniq`

ue 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?

## No comments:

Post a Comment