# Project Euler Problem 53

Project Euler Problem 53 solution is quite straightforward:

let fact (n: bigint) = [1I..n] |> List.fold (*) 1I let combinations r n = (fact n)/((fact r)*(fact (n-r))) let problem053 () = seq { for n in 1I..100I do yield ( [1I..n] |> Seq.tryFind (fun x -> combinations x n > 1000000I) |> function | None -> 0I | _ as x -> n + 1I - 2I*x.Value) } |> Seq.sum

The only speedup consideration is that finding a single number of combinations **C(r,n)** greater, than 1000000 allows to find all such combinations for this **n** without extra calculations. As for each certain **n** combinations **C(r,n)** constitute a line in Pascale’s triangle and this line is symmetric it is quite simple to calculate number of combinations greater than 1000000 when knowing the number of the first such.

From F# mastery standpoint there is an interesting trick with **yield** in order to package number of sought combinations as a standard comprehension.

Advertisements

Leave a Comment