Project Euler – Problem 64 Solution

Yan Cui

I help clients go faster for less using serverless technologies.

Problem

All square roots are periodic when written as continued fractions and can be written in the form:

image

For example, let us consider ?23:

image

If we continue we would get the following expansion:

image

The process can be summarised as follows:

image

It can be seen that the sequence is repeating. For conciseness, we use the notation ?23 = [4;(1,3,1,8)], to indicate that the block (1,3,1,8) repeats indefinitely.

The first ten continued fraction representations of (irrational) square roots are:

?2=[1;(2)], period=1

?3=[1;(1,2)], period=2

?5=[2;(4)], period=1

?6=[2;(2,4)], period=2

?7=[2;(1,1,1,4)], period=4

?8=[2;(1,4)], period=2

?10=[3;(6)], period=1

?11=[3;(3,6)], period=2

?12= [3;(2,6)], period=2

?13=[3;(1,1,1,1,6)], period=5

Exactly four continued fractions, for N <= 13, have an odd period.

How many continued fractions for N <= 10000 have an odd period?

Solution

(see full solution here).

 

Based on the algorithm on continued fractions from Wikipedia, we can implement the expansion algorithm as:

image

From the Wikipedia page:

The algorithm can also terminate on ai when ai = 2 a0, which is easier to implement.

which corresponds to the termination condition we have in the Repeat active pattern (which also checks if the accumulator is empty):

image

Also, this algorithm doesn’t work on numbers that are perfect squares, i.e. 4, 9, 16, … hence we need to exclude them when searching for our answer.

Here’s the solution in full:

image

 

This solution took 92ms to execute on my machine.

Whenever you’re ready, here are 4 ways I can help you:

  1. Production-Ready Serverless: Join 20+ AWS Heroes & Community Builders and 1000+ other students in levelling up your serverless game. This is your one-stop shop for quickly levelling up your serverless skills.
  2. Do you want to know how to test serverless architectures with a fast dev & test loop? Check out my latest course, Testing Serverless Architectures and learn the smart way to test serverless.
  3. I help clients launch product ideas, improve their development processes and upskill their teams. If you’d like to work together, then let’s get in touch.
  4. Join my community on Discord, ask questions, and join the discussion on all things AWS and Serverless.

Leave a Comment

Your email address will not be published. Required fields are marked *