FSharp.it

Some of the problems proposed by Project Euler actually present the solution together with the description of the problem itself.

This is the case with Problem 53:

There are exactly ten ways of selecting three from five, 12345:

123, 124, 125, 134, 135, 145, 234, 235, 245, and 345

In combinatorics, we use the notation, ^(5)C_(3) = 10.

In general,
^(n)C_(r) =
n!

r!(n−r)!
,where r ≤ n, n! = n×(n−1)×…×3×2×1, and 0! = 1.

It is not until n = 23, that a value exceeds one-million: ^(23)C_(10) = 1144066.

How many, not necessarily distinct, values of ^(n)C_(r), for 1 ≤ n ≤ 100, are greater than one-million?

The only knowledge required in this problem is the binomial coefficient, but its formula is also described in the text above, so we can simply generate all couples (n, r) and check if the value of the binomial coefficient is greater than one million.

In F# this is equivalent to coding a function for the binomial coefficient and testing the items of a sequence:

#light
open Microsoft.FSharp.Math

let binomial_coefficient n k = BigInt.Factorial n /
                               (BigInt.Factorial k * BigInt.Factorial (n-k))

let answer =
  seq { for n in 1I .. 100I do
          for k in 1I .. n -> n,k } |> Seq.filter (fun (a,b) -> binomial_coefficient a b > 1000000I ) |> Seq.length

The approach adopted is almost the same that I used to solve Project Euler problem number 9. It is not the smartest nor the quickest since it is essentially a brute-force algorithm, but without any doubt it is the easiest to implement.

Which optimizations would you consider?