Project Euler — Problem 23 Solution

Problem

A per­fect num­ber is a num­ber for which the sum of its prop­er divi­sors is exact­ly equal to the num­ber. For exam­ple, the sum of the prop­er divi­sors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a per­fect num­ber.

A num­ber n is called defi­cient if the sum of its prop­er divi­sors is less than n and it is called abun­dant if this sum exceeds n.

As 12 is the small­est abun­dant num­ber, 1 + 2 + 3 + 4 + 6 = 16, the small­est num­ber that can be writ­ten as the sum of two abun­dant num­bers is 24. By math­e­mat­i­cal analy­sis, it can be shown that all inte­gers greater than 28123 can be writ­ten as the sum of two abun­dant num­bers. How­ev­er, this upper lim­it can­not be reduced any fur­ther by analy­sis even though it is known that the great­est num­ber that can­not be expressed as the sum of two abun­dant num­bers is less than this lim­it.

Find the sum of all the pos­i­tive inte­gers which can­not be writ­ten as the sum of two abun­dant num­bers.

Solution

let findDivisors(n) =
   let upperBound = int32(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)
   |> Seq.distinct

let isAbundantNumber(n) = (findDivisors(n) |> Seq.sum) > n

let abundantNumbers =
   Seq.unfold (fun x -> if x < 28123 then Some(x, x+1) else None) 1
   |> Seq.filter isAbundantNumber
   |> Seq.toList

let abundantNumbersSums =
   abundantNumbers
   |> Seq.collect (fun n -> abundantNumbers |> List.map (fun m -> n + m))
   |> Seq.filter (fun n -> n <= 28123)
   |> Seq.distinct
   |> Seq.toList

let answer = ([1..28123] |> List.sum) - (abundantNumbersSums |> List.sum)

I had to make a small mod­i­fi­ca­tion to the find­Di­vi­sors func­tion which I had used pre­vi­ous­ly to make sure we don’t have any dupli­cates in there as we now need to sum the divi­sors.

I first defined the isAbun­dant­Num­ber func­tion to check if the sum of the divi­sors of a num­ber n is greater than n itself as per the def­i­n­i­tion giv­en in the brief.

Then I gen­er­at­ed the list of ALL abun­dant num­bers from 1 to 28122 because though 28123 is the upper lim­it, if it it’s to be the sum of two POSITIVE inte­gers then the two inte­gers must be in the range of 1 to 28122.

The next list abun­dant­Num­bersSums is the one that will take up the bulk of the 15 sec­onds it takes this code to run, it gen­er­ates all the unique sums less or equal to 28123 that you can gen­er­ate using two abun­dant num­bers.

The answer is then achieved by find­ing the dif­fer­ence between a) the sum of all num­bers from 1 to 28123, and b) the sum of the abun­dant­Num­bersSum list.