Skip to content

Project Euler Problem 53

November 29, 2011

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

From → Project Euler

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: