Project Euler – Problem 64 Solution

Problem

All square roots are peri­od­ic when writ­ten as con­tin­ued frac­tions and can be writ­ten in the form:

image

For exam­ple, let us con­sid­er ?23:

image

If we con­tin­ue we would get the fol­low­ing expan­sion:

image

The process can be sum­marised as fol­lows:

image

It can be seen that the sequence is repeat­ing. For con­cise­ness, we use the nota­tion ?23 = [4;(1,3,1,8)], to indi­cate that the block (1,3,1,8) repeats indef­i­nite­ly.

The first ten con­tin­ued frac­tion rep­re­sen­ta­tions of (irra­tional) 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

Exact­ly four con­tin­ued frac­tions, for N <= 13, have an odd peri­od.

How many con­tin­ued frac­tions for N <= 10000 have an odd peri­od?

Solution

(see full solu­tion here).

 

Based on the algo­rithm on con­tin­ued frac­tions from Wikipedia, we can imple­ment the expan­sion algo­rithm as:

image

From the Wikipedia page:

The algo­rithm can also ter­mi­nate on ai when ai = 2 a0, which is eas­i­er to imple­ment.

which cor­re­sponds to the ter­mi­na­tion con­di­tion we have in the Repeat active pat­tern (which also checks if the accu­mu­la­tor is emp­ty):

image

Also, this algo­rithm doesn’t work on num­bers that are per­fect squares, i.e. 4, 9, 16, … hence we need to exclude them when search­ing for our answer.

Here’s the solu­tion in full:

image

 

This solu­tion took 92ms to exe­cute on my machine.