Skip to content

Project Euler Problem 57

December 4, 2011

Project Euler Problem 57 allows for an elegant purely functional solution. Easy to notice that the relationship between n-th and (n+1)-th expansions is:

(numerator(n+1), denominator(n+1)) =

   (numerator(n) + 2*denominator(n), numerator(n) + denominator(n))

We build an infinite sequence of expansions, take first 1000 members of it, and finally filter in those that fulfill the sought relationship about number of digits and count them. As values of numerators and denominators can be substantial we operate with bigints.

let numberOfDigits n = n.ToString().ToCharArray().GetLength(0)

let expansions = Seq.unfold (fun (n,d) -> Some((n, d),(n+2I*d, n+d)))(3I,2I)

let problem057 () =
    expansions
    |> Seq.take 1000
    |> Seq.filter (fun (numerator, denominator) ->
                    numberOfDigits numerator > numberOfDigits denominator)
    |> Seq.length

Interesting how fast that values in expansions grow – nominator of 1000-th expansion is a number having 383 digits!

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: