Project Euler — Problem 21 Solution

Problem

Let d(n) be defined as the sum of prop­er divi­sors of n (num­bers less than n which divide even­ly into n).

If d(a) = b and d(b) = a, where a != b, then a and b are an ami­ca­ble pair and each of a and b are called ami­ca­ble num­bers.

For exam­ple, the prop­er divi­sors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; there­fore d(220) = 284. The prop­er divi­sors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Eval­u­ate the sum of all the ami­ca­ble num­bers under 10000.

Solution

open System

let findDivisors(n) =
    let upperBound = int32(Math.Sqrt(double(n)))

    [1..upperBound]
    |> Seq.filter (fun x -> n % x = 0)
    |> Seq.collect (fun x -> [x; n/x])
    |> Seq.filter (fun x -> x <> n)

let d(n) = findDivisors(n) |> Seq.sum
let dList = [ for n = 1 to 9999 do yield (n, d(n)) ]

let answer =
    dList
    |> List.filter (fun (a, da) -> dList
                                   |> List.exists (fun (b, db) -> b = da && a = db && a <> b))
    |> List.sumBy (fun (n, dn) -> n)

First I defined a find­Di­vi­sors func­tion which returns all the divi­sors of a giv­en num­ber exclud­ing itself as is the case in the exam­ple giv­en in the brief. Then I defined the func­tion d which returns the sum of the giv­en number’s prop­er divi­sors.

To get to the answer, I gen­er­at­ed a list of tuples for the num­bers from 1 to 9999 in the form of (n, d(n)) and from there I iter­at­ed through the list and for each tuple check whether there exists anoth­er tuple which match­es the con­di­tions required for the two to be con­sid­ered an ami­ca­ble pair.

You might have noticed in the func­tion applied to List.filter to iden­ti­fy ami­ca­ble pairs that I have decom­posed the tuple into (a, da), as I have men­tioned before this is a form of the pat­tern match­ing in F#. The same pat­tern match­ing tech­nique is also used when I cal­cu­late the sum of the ami­ca­ble pairs.