Project Euler – Problem 57 Solution

Problem

It is possible to show that the square root of two can be expressed as an infinite continued fraction.

image

By expanding this for the first four iterations, we get:

1 + 1/2 = 3/2 = 1.5

1 + 1/(2 + 1/2) = 7/5 = 1.4

1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666…

1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379…

The next three expansions are 99/70, 239/169, and 577/408, but the eighth expansion, 1393/985, is the first example where the number of digits in the numerator exceeds the number of digits in the denominator.

In the first one-thousand expansions, how many fractions contain a numerator with more digits than denominator?

Solution

// define function to return all the numerator-denominator pairs for the first n expand
let expand n =
    Seq.unfold (fun (num, denom) -> Some((num, denom), (denom*2I+num, denom+num))) (3I, 2I)
    |> Seq.take n

let answer =
    expand 1000
    |> Seq.filter (fun (num, denom) -> num.ToString().Length > denom.ToString().Length)
    |> Seq.length

If you look at the patterns 3/2, 7/5, 17/12, 41/29, and so on, it’s easy to spot a pattern where the numerator and denominator of iteration n can be derived from the iteration n-1:

Numerator(n) = Numerator(n-1) + 2 * Denominator(n-1)

Denominator(n) = Numerator(n-1) + Denominator(n-1)

Enjoy what you’re reading? Subscribe to my newsletter and get more content on AWS and serverless technologies delivered straight to your inbox.


Yan Cui

I’m an AWS Serverless Hero and the author of Production-Ready Serverless. I have run production workload at scale in AWS for nearly 10 years and I have been an architect or principal engineer with a variety of industries ranging from banking, e-commerce, sports streaming to mobile gaming. I currently work as an independent consultant focused on AWS and serverless.

You can contact me via Email, Twitter and LinkedIn.

Hire me.


Check out my new course, Complete Guide to AWS Step Functions.

In this course, we’ll cover everything you need to know to use AWS Step Functions service effectively. Including basic concepts, HTTP and event triggers, activities, design patterns and best practices.

Get Your Copy