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

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

Written by on 8 October 2011

Topics: Project Euler

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

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

13 Comments For This Post I'd Love to Hear Yours!

  1. coreyog says:

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

  2. Kristian says:

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

  3. Tom says:

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

  4. Kristian says:

    Think I fixed it now.

  5. Jean-Marie Hachey says:

    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

  6. Jean-Marie Hachey says:

    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)

  7. Thang Lat says:

    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

  8. Anthony says:

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

  9. Mr.unease says:

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

  10. Imesh says:

    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.

  11. Tilmann Bruckhaus says:

    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

  12. (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

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.