#### Problem

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

For example, let us consider ?23:

If we continue we would get the following expansion:

The process can be summarised as follows:

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:

From the Wikipedia page:

The algorithm can also terminate on a

_{i}when a_{i}= 2 a_{0}, 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):

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:

This solution took 92ms to execute on my machine.

Subscribe to my newsletter and get new contents delivered straight to your inbox :-)