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:
?12= [3;(2,6)], period=2
Exactly four continued fractions, for N <= 13, have an odd period.
How many continued fractions for N <= 10000 have an odd period?
(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 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):
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 :-)