Thursday, November 11, 2010

Numerically, the next Project Euler problem is number 20:

Find the sum of digits in 100!

Hmmm... what to do, what to do? Well, as always, lets start with the helper functions. 100! is a very big number. Thus we will have to use F#'s BigInt type. Here's a factorial function:

let factorial n = Seq.fold ( * ) 1I [1I .. n]

Of course, F# already has a factorial function for BigInts but since this is a learning exercise I felt that I had to write my own.

Next I want to turn a big number into a series of digits. This is the function I used for that purpose in my solution to problem number 16:

let rec digits n =
    seq {
        if n > 0I then
            yield n%10I
            yield! digits (n/10I)
    }

Finally we can put these together to create a solution:

factorial 100I |> digits |> Seq.sum |> printfn "sum = %A"

On my computer I get the answer in less time than it takes to threaten the monitor with my fist.

No comments: