The Problem
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.
The Solution
First, we have to find all the divisors of a given n.
let intsqrt i = int(sqrt(float i))
let findDivisors n =
let upperBound = intsqrt n
[1..upperBound]
|> Seq.filter (fun d -> n % d = 0)
|> Seq.collect (fun d -> [d; n/d])
|> Seq.filter (fun d -> d <> n)
|> Seq.distinct
Like some of our prime-finding code, we only have to check for divisors up to the square root of n
.
If d
is a divisor less than the square root of n
, then both d
and n/d
are divisors of n
.
findDivisors
checks all numbers up to the square root of n
for divisibility, and adds any divisors
it finds along with n/d
. Lastly, it filters out n
itself and uses Seq.distinct
to make sure it
only returns unique divisors.
Next, we need to find out if a given a
and b
are "amicable" according to the problem definition.
let sumDivisors n = findDivisors n |> Seq.sum
let d =
seq { 1..9999 }
|> Seq.map (fun n -> n,sumDivisors n)
|> Map.ofSeq
let areAmicable (a,b) = d.[a] = b && d.[b] = a
The sumDivisors
function simply sums the divisors we found above.
Next, we build a map of divisor sums. For the numbers 1 to 9999, n
is the key
and the sum of its divisors is the value.
With that in hand, we can determine if a given a
and b
areAmicable
using the test given in the problem
definition.
And now we can look for the answer.
seq {
for a in 1..9999 do
for b in 1..9999 do
if a <> b then yield a,b
}
|> Seq.filter areAmicable
|> Seq.sumBy fst
First, we build a sequence of all possible pairs of numbers from 1 to 9999, skipping the case when
a
and b
are equal. Then we filter out the pairs that areAmicable
and sum the a
values to
get the answer.