# Project Euler Problem 23

Project Euler Problem 23 would allow us reusing divisorSum function from solution to Project Euler Problem 21. Finding if a number is abundant is trivial; what is non-trivial is finding numbers that cannot be presented as a sum of two abundant numbers. After a fair amount of consideration I was able to come up with a solution based on a mutable data structure: on interval [0..28122] we will mark all members that are sums of two abundant numbers; those left unmarked would be sought unrepresentable:

let divisorSum n = let divisors n = [ yield 1 for i in 2..int (sqrt(float n)) do if n%i = 0 then yield i if i <> n/i then yield n/i ] divisors n |> List.sum let isAbundant n = n < divisorSum n let fastSolution abundant = let numbers = Array.create 28123 0 let rec markPresentable l = match l with | [] -> () | x::xs -> List.iter (fun a -> if x + a <= 28123 then numbers.[x + a - 1] <- 1) l markPresentable xs markPresentable abundant [for i in 0..28122 do if numbers.[i] = 0 then yield i + 1] |> List.sum let problem023 () = [1..28123] |> Seq.filter isAbundant |> (Seq.toList >> fastSolution)

Advertisements

Leave a Comment