Project Euler 64:How many continued fractions for N ≤ 10000 have an odd period?

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 = a0 + 1 a1 + 1 a2 + 1 a3 + …

For example, let us consider √23:

 √23 = 4 + √23 — 4 = 4 + 1 = 4 + 1 1 √23—4 1 + √23 – 3 7

If we continue we would get the following expansion:

 √23 = 4 + 1 1 + 1 3 + 1 1 + 1 8 + …

The process can be summarised as follows:

 a0 = 4, 1 √23—4 = √23+4 7 = 1 + √23—3 7 a1 = 1, 7 √23—3 = 7(√23+3) 14 = 3 + √23—3 2 a2 = 3, 2 √23—3 = 2(√23+3) 14 = 1 + √23—4 7 a3 = 1, 7 √23—4 = 7(√23+4) 7 = 8 + √23—4 a4 = 8, 1 √23—4 = √23+4 7 = 1 + √23—3 7 a5 = 1, 7 √23—3 = 7(√23+3) 14 = 3 + √23—3 2 a6 = 3, 2 √23—3 = 2(√23+3) 14 = 1 + √23—4 7 a7 = 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, for N ≤ 13, have an odd period.

How many continued fractions for N ≤ 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

$\displaystyle m_0 = 0$ $\displaystyle d_0 = 1$ $\displaystyle a_0 = \lfloor\sqrt{S}\rfloor$

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

$\displaystyle m_{n+ 1} = d_na_n - m_n$ $\displaystyle d_{n+1} = \frac{S-m_{n+1}^2}{d_n}$ $\displaystyle a_{n+1} = \lfloor\frac{\sqrt{S} + m_{n+1}}{d_{n+1}}\rfloor$

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

Posted by Kristian

coreyog

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

Kristian

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.

Kristian

Think I fixed it now.

Jean-Marie Hachey

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

Jean-Marie Hachey

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)

Thang Lat

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

Anthony

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

Kristian

Yes it is.

Mr.unease

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

Imesh

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.

Tilmann Bruckhaus

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

Tilmann Bruckhaus