Project Euler in F# - Problem 23

Here is a quick write-up on how to solve Project Euler’s Problem 23 in F#.

Problem 23 is defined as follows:

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

A number whose proper divisors are less than the number is called deficient and a number whose proper divisors exceed the number is called abundant.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

Sounds simple enough; onto the code!

let problem23 =

    let factors x =

        match x with

        | _ when x < 0 -> failwith "x must be positive or zero."

        | 0 -> [] | 1 -> [1]

        | _ ->

            // Compute the sqrt - subtract epsilon to avoid wackiness with perfect squares...

            let sqrt = int_of_float (Math.Sqrt((float_of_int x)))

            // By returning each pair of factors, we only have to count up to sqrt(x)

            let factorPairs = {for i in 1 .. sqrt - 1 when x % i = 0 -> (i, x / i)}

            // Unzip those factor pairs, which turns {(a;b;...);(c;d;...)} -> ({a;c;...};{b;d;...})

            let (l1, l2) = List.unzip (Seq.to_list factorPairs)

            // Special case if x is a perfect square

            if sqrt * sqrt = x then

                l1 @ [ sqrt ] @ (List.rev l2)

            // Special case if floor(sqrt) is a factor, which we didn't check

            elif x % sqrt = 0 then

                l1 @ [ sqrt; x / sqrt ] @ (List.rev l2)

            else

                l1 @ (List.rev l2)

    // Check if x is an abundant number

    let abundant x =

        let sum = Seq.fold (+) 0 (factors x)

        (sum - x > x)

    // Array with 28,123 elements where element [i] is whether or not i is abundant

    let abNumberLookup = [| for i in 0 .. 28123 -> abundant i |]

    // Checks if x can be expressed as a pair of abundant numbers.

    // (We will use a cached list of all abundant numbers < 28,123)

    let abdList = List.filter (fun i -> abundant i) [1 .. 28123]

    let rec isPairOfAb list x =

        if (List.hd list) > x then false

        elif abNumberLookup.[x - (List.hd list)] = true then true

        else isPairOfAb (List.tl list) x

    // Now we have all the primitives we need, get the list of non-abundant numbers.

    let nonPairOfAb = List.filter (fun i -> (isPairOfAb abdList i) = false) [1 .. 28123]

    // Return their sum

    List.fold_left (+) 0 nonPairOfAb

First I define a function that computes the factors of an integer. Initially to compute the factors of a number I used a very simple and very straightforward Sequence Comprehension:

let factors x = {for i in 1 .. x when x % i = 0 -> x}

While that one liner looks great, the problem is that its running time is on order O(n). While that doesn’t sound like much, it really adds up when you need to compute the factors of 28,000 5-digit numbers. So instead, I went with an O(n^0.5) implementation, which keeps track of factor pairs. This also gave me an opportunity to use the List.unzip function, which takes a list of tuples and ‘unzips’ them into two separate lists.

For the last part of my implementation I needed an abundant number lookup. So I used a Sequence Comprehension again, this time producing an array. (Note: I’m not sure what the exact terminology here is – does this make it an Array Comprehension?) Notice that I started the counter at 0, since that will produce the first element of the array which is zero-indexed. It is easy to mistakenly start the sequence at 1, not realizing you are introducing an off-by one error.

Finally, to check if a number is the sum of two abundant numbers I simply compare each abundant number I know of, a, and x. If (x – a) is also abundant, then x is the sum of two abundant numbers, (x-a) and a. I can do this efficently by using my lookup array and indexing into it by (x – a).

Anyways, I think problem 23 was well suited for F#. I don’t doubt there is a more concise way to write that function for producing factors; if you can improve on this please post a comment. I’m always eager to see how other people approach and use F#.

The programming problem described here was obtained from and is copyright of Project Euler.

Comments

• Anonymous
  December 08, 2007
  Here is a quick write-up on how to solve Project Euler’s Problem 23 in F#......( read more )