Skip to content

Project Euler Problem 23

November 16, 2011

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

From → Project Euler

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: