Problem 57 was all about continued fractions, and in Problem 64 of Project Euler we are visiting that subject again. The problem reads

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

√N=a_{0}+1a_{1}+1a_{2}+1a_{3}+ …

For example, let us consider √23:

√23 = 4 + √23 — 4 = 4 +1= 4 +11

√23—41 +√23 – 3

7

If we continue we would get the following expansion:

√23 = 4 +11 +13 +11 +18 + …

The process can be summarised as follows:

a_{0}= 4,1

√23—4=√23+4

7= 1 +√23—3

7a_{1}= 1,7

√23—3=7(√23+3)

14= 3 +√23—3

2a_{2}= 3,2

√23—3=2(√23+3)

14= 1 +√23—4

7a_{3}= 1,7

√23—4=7(√23+4)

7= 8 +√23—4a_{4}= 8,1

√23—4=√23+4

7= 1 +√23—3

7a_{5}= 1,7

√23—3=7(√23+3)

14= 3 +√23—3

2a_{6}= 3,2

√23—3=2(√23+3)

14= 1 +√23—4

7a_{7}= 1,7

√23—4=7(√23+4)

7= 8 +√23—4

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, forN≤ 13, have an odd period.

How many continued fractions forN≤ 10000 have an odd period?

I shall be the first person here to admit that all I got from the problem description was the question, the helping text didn’t help me at all. So I had to ask uncle wiki how to solve this problem, and it returned me an algorithm which I could use.

## Algorithm

The algorithm on Wikipedia works for non perfect squares. Since perfect squares can’t be described as continued fractions. The algorithm uses two variables plus the a variable that we are looking for. It states that for a number S we can initialize the algorithm as

Looking at the algorithm it turns out that the 4 that magically appears in the example in the problem description is indeed the floored square root of the number we are looking for, now it all starts to make sense.

The iterative part of the algorithm goes

Going through the algorithm this fits with the results we get from the example given in the problem description.

Wikipedia then says that the period part has been found once we get a tuple of a,d and m which is equal to one already encountered. However a bit more investigation turned up a paper by Alexandra Ioana Gliga on the of continued fractions of square roots where corollary 3.3 shows that the periodic part ends with when we encounter an . This reduces the search to something which is far easy to handle when implementing the code.

## C# implementation

Once we have found this algorithm the implementation is really straight forward. I have made the following implementation

int upperbound = 10000; int result = 0; for (int n = 2; n n int a0 = (int) Math.Sqrt(n); if (a0 * a0 == n) continue; int period = 0; int d = 1; int m = 0; int a = a0; do{ m = d*a – m; d = (n – m * m) / d; a = (limit + m) / d; period++; }while(a != 2*a0); if (period % 2 == 1) result++; }

It gives the following result in 5ms

There are 1322 sqaureroots with odd period below 10000 Solution took 5 ms

## Wrapping up

I don’t think I completely understand continued fractions, but this problem gave me a much better idea how to work with them and what they do. You are welcome to peek at the full source code for the problem, it follows the outline given in this post very well.

Questions comments and other approaches for solution are as always welcome. Maybe you can spread light on applications of continued fractions.

I really lacked imagination for the photo for this blog post, but since we are dealing with infinite fractions I thought a photo of the infinity bridge was appropriate. The photo is kindly provide by Freefoto.com

What page on wikipedia showed you this algorithm? You never posted it and I’m not finding it on the Continued Fraction page.

Hmmm, no apparently I forgot to link to the article. It is here, and I have updated the blog post to include the link.

There is a typo in the second equation in the Algorithm section.

Think I fixed it now.

Table 1

Distribution of even and odd periods in continued fractions of square roots below 10000

http://img15.hostingpics.net/pics/996483pe64tableone.jpg

In Table 1, we can see that the proportion of even length periods is always more important as compared to odd periods by a general factor around 6 to 7.

Results in Table 1 were obtained using Kristian’s algorithm (1).

Even periods calculated with this line of code:

if (period % 2 == 0) result++;

___

Sources :

1) Project Euler – Problem 64

Kristian’s code:

http://www.mathblog.dk/files/euler/Problem64.cs

2) Microsoft Visual C# 2010 Express

3) Microsoft Office Excel (2007)

4) Even and odd periods in continued fractions of square roots

Rippon, Philip and Taylor, Harold (2004)

Fibonacci Quarterly, 42(2) pp. 170–180.

http://www.fq.math.ca/Papers1/42-2/quartrippon02_2004.pdf

5) An Introduction to Continued Fractions

http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/cfINTRO.html#genCF

Using the OEIS list (1,2) as starting material, here are some results and comments on continued fractions (CF) of square roots for the sequence 1-5000.

Table 1

Continued fractions of square roots:

Variation of the number of continued fractions per period lengths (0-422)

as a function of the period lengths (0-152)

http://img15.hostingpics.net/pics/268509pe64table1f.jpg

Fig. 1

Continued fractions of square roots:

Variation of the number of continued fractions per period lengths (0-422) as a function of the period lengths (0-152)

http://img15.hostingpics.net/pics/932951pe64figure1f.jpg

The number of perfect squares is equal to the quantity continued fractions (CF) of square roots of period length 1 (70 between 1 and 5000).

The number of CF of square roots (CF.SQRT) per period lengths reaches a maximum at the period length of 2 (422). For many period lengths, there are no CF.SQRT (77, 101, 105, 109, 111, 113, 117, 120, 121, 123, 126, 127, 129, 131-135, 137-140, 142-147, 149-151).

___

Sources:

1) Period of continued fraction for square root of n (or 0 if n is a square).

(Formerly M0018)

http://oeis.org/A003285

And references cited therein.

2) LINKS T. D. Noe, Table of n, a(n) for n = 1..5000

http://oeis.org/A003285/b003285.txt

3) Microsoft Office Excel (2007)

every rational number can be written as a finite continued fraction

every finite continued fraction is a continued fraction

perfect squares are rational numbers

————————————

perfect squares can be be written as continued fractions

Hi, I’m curious about the photo from this article – is it the millennium bridge in Stockton?

Yes it is.

Forgive my possible ignorance but on line 15, where do limit pop into existence. Would it not be more straight forward to use a0?

I think it’s easy to use prime numbers and get the multiphications cus modulo & division take time to process .Every prime has a unique continued fractions patterns.

Hi Kristian,

Nice website!

Line 4 in your source code is mangled. It looks like a few characters from lines 4 and 5 were deleted.

BTW, I have used your solutions in my Java and Python solutions for Euler:

https://github.com/bruckhaus/challenges/tree/master/python_challenges/project_euler

https://github.com/bruckhaus/challenges/tree/master/java_challenges/ProjectEuler/src/main/java

Tilmann

(I added my website)

Hi Kristian,

Nice website!

Line 4 in your source code is mangled. It looks like a few characters from lines 4 and 5 were deleted.

BTW, I have used your solutions in my Java and Python solutions for Euler:

https://github.com/bruckhaus/challenges/tree/master/python_challenges/project_euler

https://github.com/bruckhaus/challenges/tree/master/java_challenges/ProjectEuler/src/main/java

Tilmann