Skip to main content

Project Euler #020

n! means n × (n − 1) × … × 3 × 2 × 1
Find the sum of the digits in the number 100!

let factorial n : bigint = List.fold (*) 1I [1I .. n]

let sum (n:bigint) = n |> string |> Seq.fold (fun acc x -> acc + System.Int32.Parse(x.ToString())) 0

sum (factorial 100I)

If you consider using bigint to be cheating, here's a solution that will calculate it with the use of lists instead.

let rec plan overflow l =
    match l with
    | head :: tail ->
        let column = head + overflow
        if column > 9 then
            let nextoverflow = column / 10 |> float |> System.Math.Truncate |> int
            (column - nextoverflow * 10) :: plan next_overflow tail
        else
            column :: plan 0 tail
    | _ -> if overflow > 0 then 
              (overflow % 10) :: plan ((overflow - (overflow % 10)) / 10) []
           else 
              []

let add (l1 : int list) (l2 : int list) = l1 |> List.map2 (fun i1 i2 -> i1 + i2) l2

let prod (l1 : int list) (l2 : int list) = let tenths i = 10.0 ** (i |> float) |> int l2 |> List.mapi (fun i x -> l1 |> List.map (fun y -> x * y * tenths (-1 + l2.Length - i))) |> List.fold (fun acc l -> add acc l) (List.init l1.Length (fun i -> 0)) |> List.rev |> plan 0 // from outer space |> List.rev

let to_list n = let rec calc x = if x > 0 then (x % 10) :: calc ((x - (x % 10)) / 10) else [] calc n |> List.rev

[2..100] |> List.map (fun x -> tolist x) |> List.fold (fun acc y -> prod acc y) [1] |> List.sum

<script src="https://gist.github.com/miklund/366cb7f0459131ee5bcb.js?file=E020B.fs">

comments powered by Disqus