The Problem

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.

Find the sum of all numbers which are equal to the sum of the factorial of their digits.

Note: as 1! = 1 and 2! = 2 are not sums they are not included.

The Solution

As usual, we'll start out with some helper functions.

let digitize (n : bigint) =
    let str = n.ToString()
    str |> Seq.map (fun x -> int(x) - int('0'))

let rec factorialBig n =
    match n with 
    | 0 -> 1I
    | 1 -> 1I
    | _ -> bigint(n) * factorialBig (n-1)

let facts = 
    [0..9]
    |> List.map (fun x -> (x,factorialBig x))
    |> Map.ofList

digitize is a function I use over and over in these Project Euler problems. It converts a number into a sequence of digits.

The factorialBig function is the classic recursive factorial function using BigInteger values.

During the course of execution, we're going to need the factorial for the numbers 0-9 over and over and over again. So we'll pre-generate all those and turn them into a Map so we can quickly look them up later.

let factorialSum n =
    digitize n
    |> Seq.map (fun x -> facts.[x])
    |> Seq.sum

The factorialSum function turns a number into digits, maps those digits to their factorials, and then returns the sum of those.

With that in hand, we can solve the problem:

#time
seq { 3I..99999I }
|> Seq.filter (fun x -> factorialSum x = x)
|> Seq.sum
#time

I love it when Project Euler problems use the wording "all numbers". That means it's our job to figure out where the program is supposed to stop, otherwise we can just keep looking at numbers forever. I arbitrarily chose to stop looking after 5 digits, and it turns out that works.

Other Posts in This Series