An introduction to Continued Fractions

Continued fractions are just another way of writing fractions. They have some interesting connections with a jigsaw-puzzle problem about splitting a rectangle into squares and also with one of the oldest algorithms known to Greek mathematicians of 300 BC - Euclid's Algorithm - for computing the greatest divisor common to two numbers (gcd).

An online Combined Continued Fraction Calculator is available in a separate window where you see Combined CF in a new window
It is now updated to be a BigNumber Calculator that can handle very long whole numbers! (Jan 2018)
Contents of this page
The You do the maths... icon means there is a You do the maths... section of questions to start your own investigations. The calculator calculator icon indicates that there is a live interactive calculator in that section.

1 Introducing the Continued Fraction...

Here we show 2 ways to "discover" the continued fraction:

1.1 A jigsaw puzzle: splitting rectangles into squares

45x16 rect Let's take an example to introduce you to a continued fraction. We'll convert the ordinary fraction 45/16 into a continued fraction.
We will make extensive use of a picture analogy (from Clark Kimberling of Evansville University, USA, but also mentioned by N N Vorob'ev in 1951 - see references below). For our example fraction of 45/16 we will use a rectangle of 45 units by 16 to show visually what is happening with the mathematics.

Looking at the rectangle the other way, its sides are in the ratio 16/45. We shall use this change of view when expressing 45/16 as a continued fraction. 45/16 suggests that we convert it to a whole number quotient (since 45 is bigger than 16) plus a proper fraction (what is left over after we've taken away multiples of 16 from 45).
45/16 is 2 lots of 16, with 13 left over, or, in terms of ordinary fractions: 45x16 rect

45
16
=
16 + 16 + 13
16
= 2 +
13
16
In terms of the picture, we have just cut off squares from the rectangle until we have another rectangular bit remaining. There are 2 squares (of side 16) and a 13 by 16 rectangle left over. The final rectangle is taller than it is wide, so no more 16x16 squares can be taken from it.

Now, suppose we do the same with the 13-by-16 rectangle, viewing it the other way round, so it is 16 by 13 (so we are expressing 16/13 as a whole number part plus a fraction left over). In terms of the mathematical notation we have:

45 = 16 + 16 + 13 = 2 + 13 = 2 + 1
161616 16/13
Repeating what we did above but on 16/13 now, we see that there is just 1 square of side 13 to cut off, with a 3-by-13 rectangle left over. Writing the same thing mathematically expresses 13/3 as a whole-number-plus-fraction like this:
45x16
45 = 2 + 13 = 2 + 1 = 2 + 1
1616 16/13 1 + 3/13
Notice how we have continued to use fractions and how the maths ties up with the picture.
You will have guessed what to do now: we do the same thing on the left-over 3-by-13 rectangle, but looking at it as a 13-by-3 rectangle. There will be 4 squares (of side 3) and a rectangle 1-by-3 left over:
45x16
45
16
= 2 + 13
16
= 2 + 1
16/13
= 2 + 1
1 + 3/13
2 + 1
1 + 1
13/3
2 + 1
1 + 1
4 + 1
3

But now we have ended up with an exact number of squares in a rectangle, with nothing left over so we cannot split it down any more.
45x16
2 + 1
1 + 1
4 + 1
3

This expression relates directly to the geometry of the rectangle-as-squares jigsaw as follows: Since the numbers always reduce, that is, the size of the remaining rectangle left over will always have one side smaller than the starting rectangle, then the process will always stop with a final n-by-1 rectangle.

1.2 Using Euclid's GCD algorithm to make a continued fraction

One of the often studied algorithms in computing science is Euclid's Algorithm for finding the greatest common divisor (gcd) of two numbers. The greatest common divisor (often just abbreviated to gcd) is also called the highest common factor (or just hcf). It is intimately related to continued fractions, but this is hardly ever mentioned in computing science text books. Here we try to show you the link and introduce a visual way of seeing the algorithm at work as well as giving an alternative look into continued fractions.

So let's look again at the calculations we did above for 45/16.

45=2 ×16+13: 45 is a multiple of 16 with 13 left over
16=1 ×13+ 3: 16 is a multiple of 13 with  3 left over
13=4 × 3+ 1: 13 is a multiple of  3 with  1 left over
3=3 × 1+ 0:  3 is a multiple of  1 e×actly.
L= S+ R 
The bold figures ( N ) are our continued fraction numbers. The L column is the Longest side of each rectangle that we encountered with S the Shortest side and R being the Remainder.
The method shown here is These are the three conditions necessary for an algorithm - a method that a computer can carry out automatically and which eventually stops.

Euclid (a Greek mathematicians and philosopher of about 300 BC) describes this algorithm in Propositions 1, 2 and 3 of Book 7 of The Elements, although it was probably known to the Babylonian and Egyptian mathematicians of 3000-4000 BC also.
If we try it with other numbers, the final non-zero remainder is the greatest number that is an exact divisor of both our original numbers (the greatest common divisor) - here it is 1.

Given any two numbers, they each have 1 as a divisor so there will always be a greatest common divisor of any two (positive) numbers and it will be at least 1.

1.2.1 Using Lists of Divisors to find the GCD

Here are the divisors of 45 and of 16:

  45 has divisors  1, 3, 5, 9, 15 and 45
  16 has divisors  1, 2, 4, 8 and 16
So the largest number in both of these lists is just 1.

Let's take a fraction such as 168/720. It is not in its lowest terms because we can find an equivalent fraction which uses simpler numbers. Since both 168 and 720 are even, then 168/720 is the same (size) as 84/360. This fraction too can be reduced, and perhaps the new one will be reducible too. So can we find the largest number to divide into both numerator 168 and denominator 720 and get to the simplest form immediately?
However, first, let's try to find the largest number to divide into both 168 and 720 directly:
Find the lists of the divisors of 168 and of 720 and pick the largest number in both lists:

168 has divisors 1, 2, 3, 4, 6, 7, 8, 12, 14, 21, 24, 28, 42, 56, 84 and 168
720 has divisors 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 30, 36, 
                 40, 45, 48, 60, 72, 80, 90, 120, 144, 180, 240, 360 and 720
Phew! - that took some work!
Now we just need to find the largest number in both lists. A bit of careful searching soon reveals that it is 24. So 24 is the greatest common divisor (gcd) of 168 and 720. You will often see statements such as this written as follows:
gcd( 168, 720 ) = 24
Another term often used for greatest common divisor is highest common factor (hcf).

The importance of the gcd of a and b is that it tells us how to put the fraction a/b into its simplest form by giving the number to divide the top and the bottom by. The resulting fraction will be the simplest form possible. So

168 = 168 ÷24 = 7 and similarly 720 = 30 = 4 + 2
720720÷243016877

Euclid's algorithm is here applied to 720 and 168: Just keep dividing and noting remainders so that the larger number 720 is 4 lots of the smaller number 168 with 48 left over. Now repeat on the smaller number (168) and the remainder (48) and so on:


   720 = 4 × 168 + 48
   168 = 3 × 48 + 24
    48 = 2 × 24 + 0
so the last multiple before we reach the zero is 24, just as we found above but with rather less effort this time!

168x720 Here is a rectangle 720 by 168 split up into squares, as above where the numbers in the squares are the length of their sides. Note how the quotients 4, 3 and 2 are shown in the picture and also that the gcd is 24 (the side of the smallest squares):
And here is 720/168 expressed as a continued fraction:

720= 4 + 48= 4 + 1= 4 + 1= 4 + 1
168168168/483 + 243 + 1
482
If we simplify the continued fraction starting at the lowest part we will find 720/168 in its lowest form:
720 = 4 + 1 = 4 + 1 = 4 + 2 = 28 + 2 = 30
1683 +17/2777
2

1.3 The List Notation for Continued Fractions

Writing continued fractions (CFs) in the usual way takes up a lots of space so there is a convenient shorthand: make a list of the initial integer part (which may be 0) and the numbers in the denominators (the numerators are always 1).
For example
30= 4 + 1is written as [4; 3, 2]
73 +1
2
We can write down any continued fraction such as
  P/Q = a + 1/(b + 1/(c + 1/(d + ...)))
just as a list of the numbers a; b, c, ... . The first number, a, is special as it is the whole number part of the value. The rest is written as a list with comma separators (,) like this:
 P/Q = [a; b, c, d, ...]
None of the values will be zero, except possibly the first - the one before the semicolon (;) - if the value of the fraction is less than 1.

In some mathematical books and articles you will see one other form of notation which saved space :

P  =  
Q
a + 1
b + 1
c + 1
d + ...
 
  =  a+1/(b+1/(c+1/(d+...)))  =  

a +111...
b +c +d +
The second form is normal mathematical notation but has lots of necessary brackets, making it harder to read and also must easier to miss a bracket.
In the final form note that the + is written below the fraction-line to show that the rest of the expression is also meant to be there too.
On this page and others at this site, we will use the much more convenient list notation [ a; b, c, d, ... ].

1.4/ You do the maths... /

There is another simple way to find gcd's which takes more work than Euclid's method but is quicker than enumerating all the divisors. It involves expressing the two numbers as powers of prime factors, for instance: 720 = 24 x 32 x 51 and 168 = 23 x 31 x 71
First re-write these so that the same prime numbers appear in both lists, using a-prime-to-the-power-of-0 if necessary.
For instance, there are no 7's in the primes product for 720, so, since 70=1, we introduce an extra factor of x70. In the same way we can introduce x50 into the product for 168.
Now both lists contains exactly the same primes: 2, 3, 5 and 7: 720 = 24 x 32 x 51 x 70 and 168 = 23 x 31 x 50 x 71
Since there must be 2's in the gcd of 720 and 168, how many twos do we need for the greatest factor which divides both?
What about the number of 3's? and 5's? and 7's?
So the greatest common divisor has the form:
2a x 3b x 5c x 7d
  1. What numbers stand in place of the letters?
  2. What is the general principle for computing the gcd given two numbers expressed as powers of the same primes?
  3. What is the greatest common divisor of 24 and 18 (call it G)? What is the gcd of 24, 18 and 30? How is it related to the gcd of G and 30? [This is Propositions 3 of Euclid's The Elements, Book 7.]
  4. The gcd is useful in simplifying a fraction. But when adding fractions we find equivalents with the same denominator. This time we need the smallest number into which both denominators will divide exactly, ot the lowest common multiple (lcm).
    Using the prime-powers decomposition of two denominators, how can we find the lcm? Use 168 and 720 as an example.
  5. What is the relationship beween gcd(a,b), lcm(a,b) and a×b?

You can check your answers using the Euclid's Algorithm CF Calculator in the next section or....
The greatest common divisor has the same primes as a and b but the power of each prime is the smaller of its powers in a and b.
720 = 24 × 32 × 51 × 70
168 = 23 × 31 × 50 × 71
GCD(720,168) = 23 × 31 × 50 × 70 = 24

The lowest common multiple of a and b has the same primes as in a and b with each raised to to the larger of its powers in each number. So
720 = 24 × 32 × 51 × 70
168 = 23 × 31 × 50 × 71
LCM(720,168) = 24 × 32 x 51 x 71 = 5040

When we multiply gcd(a,b) by lcm(a,b) we are using each prime power in both a and b. Therefore
gcd(a,b) × lcm(a,b) = a × b

1.5 A Euclid's Algorithm CF Calculator

This Calculator shows

Euclid's Algorithm CF C A L C U L A T O R
Euclid's Algorithm and the CF for

Show all divisors?:
for the CF [ ]

R E S U L T S


calculator: Euclid's Algorithm Fractions Expressions Square roots Quadratics Best Approxs. Silver Means Negatives Combined CF in a new window

2 The General form of a Simple Continued Fraction

Any and every fraction, P/Q where P and Q are whole, positive numbers can be written in the form of a continued fraction as shown above using Euclid's Algortihm in any of the various forms above. We know that any proper fraction can be expressed using a finite number of terms in its continued fraction.

We can write down any continued fraction such as

  P/Q = a + 1/(b + 1/(c + 1/(d + ...)))
just as a list of the numbers [a; b, c, ... ] . The first number, a, is special as it is the whole number part of the value. The rest is written as a list with comma separators (,) like this:
 P/Q = [a; b, c, d, ...]
None of the values will be zero except possibly the first, the one before the semicolon (;).If the first is zero it means the value of the continued fraction is less than 1.

2.1 The first number in the list

For the continued fraction examples above, we can now write them as:
45/16   = [ 2; 1, 4, 3 ]
7/30    = [ 0; 4, 3, 2 ] = [ 0; 4, 3, 1, 1 ]    (*)
If the first number in the list is 0, then the fraction it represents is less than 1.

2.2 An easy method of inverting a fraction

To take the reciprocal of an ordinary fraction, we just turn it upside-down.
For example, the reciprocal of  
16
45
is
1
16
45
or
45
16
.

There is also a simple way to find the reciprocal of a continued fraction.
16/45, the reciprocal of 45/16 is just 0 + 1/(45/16), so we just insert a 0 at the front of the continued fraction in list form:
45/16 = [ 2; 1, 4, 3 ] and 16/45 = [0; 2, 1, 4, 3 ]
If the continued-fraction list already begins with a zero, as in 1/2 = [0; 2] then its reciprocal is found by removing the 0 from the front of the list:
2 = [  0 ; 2 ] = [ 2; ]
2/3 = [  0 ; 1, 2 ] = [ 1; 2 ] = 3/2
So all whole numbers n have the continued fraction form [ n ; ].

2.3 The last number in the list

One half is:
1/2     = [ 0; 2 ]which we can also write as  0+ 1/(1 + 1/1) = [ 0; 1, 1 ]
In fact the last fraction in a continued fraction: 1/n can always be written as 1/( (n−1) + 1/1) so an ending [ ..., n ] = [ ... , n−1, 1] provided that n > 1.

There are two forms for the fraction 7/30 namely [0; 4, 3, 2] and [0; 4, 3, 1, 1]
This is true for all continued fractions. We can always write the last number, n, as (n-1) + 1/1 and so change the n to n − 1 and continue the fraction by one more number, 1, provided n > 1. Alternatively, if the last number is 1, we can remove it by adding it to the number before in the lost; So we have the general rule:

Every finite continued fraction ending with n>1 has two forms:

2.4/ You do the maths... /

You might find the calculator Combined Continued Fraction Calculator useful in this section.

  1. Express the following as continued fractions:
    1. 41/13 = [3; 6, 2] = [3; 6, 1, 1]
    2. 124/37 = [3; 2, 1, 5, 2] = [3; 2, 1, 5, 1, 1]
    3. 5/12 = [0; 2, 2, 2] = [0; 2, 2, 1, 1]
  2. x The three rectangles in the picture are split into squares.
    Assuming that the smallest sized square has sides of length 1, what is the ratio of the two sides of each of the three rectangles?
    1+1/4 =5/4,
    2 + 1/(1 + 1/4) =2 + 4/5=14/5,
    1 + 5/14 = 19/14

  3. In the continued fraction for 45/16 = [ 2; 1, 4, 3 ], let's see what happens when we change the final 3 to another number.
    What fractions correspond to the following continued fractions (in list form)? Can you spot the pattern?
    1. [ 2; 1, 4, 4 ] 59/21 = 2.8095238095238093
    2. [ 2; 1, 4, 5 ] 73/26 = 2.80769230769231
    3. [ 2; 1, 4, 6 ] 87/31 = 2.80645161290323
    4. [ 2; 1, 4, 7 ] 101/36 = 2.8055555555555554
    5. [ 2; 1, 4, n ] (3+14n)/(1+5n)

    How is your pattern related to the proper fraction for [ 2; 1, 4 ] ?
    [2; 1, 4] = 14/5 and the fractions above approach this as n gets larger
    the numerators increasing by 14 and the denominators by 5
  4. This time we take the square numbers:
    1, 22=4, 32=9, 42=16, 52=25, 62=36, 49, 64, 81, 100, 121, 144, ...
    and form fractions from neighbouring squares.

    First let's look at this sequence of fractions formed from neighbouring square numbers in the list above. Change each of these fractions into a continued fraction.
    1. 25/16 = [1; 1, 1, 3, 2]
    2. 49/36 = [1; 2, 1, 3, 3]
    3. 81/64 = [1; 3, 1, 3, 4]
    4. 121/100 = [1; 4, 1, 3, 5]

    Can you spot the pattern for
    (2n+1)2
    (2n)2
    ?
    (2n+1)2 / (2n)2 = [1; n-1, 1, 3, n ]

    With thanks to Anthony Shaw who first brought these patterns to my attention.
  5. Here is another sequence of fractions formed from successive square numbers.
    Convert each of these fractions to a continued fraction.
    1. 36/25 = [1; 2, 3, 1, 2]
    2. 64/49 = [1; 3, 3, 1, 3]
    3. 100/81 = [1; 4, 3, 1, 4]
    4. 144/121 = [1; 5, 3, 1, 5]

    What is the pattern this time?
    (2n)2 / (2n - 1)2 = [1; n-1, 3, 1, n-1 ]

  6. spiral Here is the Fibonacci Spiral from the Fibonacci Numbers in Nature page:
    If the smallest squares have sides of length 1, what continued fraction does it correspond to?
    What proper fraction is this?

    sizes are 1,1,2,3,5,8,13

  7. Convert the successive Fibonacci number ratios into continued fractions. What pattern do your answers show?
    1. 1/1 = [1; ]
    2. 2/1 = [2; ]
    3. 3/2 = [1; 1, 1] = [1; 2]
    4. 5/3 = [1; 1, 1, 1] = [1; 1, 2]
    5. 8/5 = [1; 1, 1, 1, 1] = [1; 1, 1, 2]

    If the ratio of consecutive Fibonacci numbers gets closer and closer to Phi, what do you think the continued fraction might be for Phi=1·618034... which is what the above fractions are tending towards?
  8. The last question made fractions from neighbouring Fibonacci numbers. Suppose we take next-but-one pairs for our fractions:
     5 8 13 21
     2 3 5 8
    Convert each of these to continued fractions, expressing them in the list form. What pattern do you notice?
    2 = [2;]
    3 = [3;]= [2; 1]

    5/2 = [2; 2] = [2; 1, 1]
    8/3 = [2; 1, 2] = [2; 1, 1, 1]
    13/5 = [2; 1, 1, 2] = [2; 1, 1, 1, 1]
    The ratios tend towards Phi2 = 1 + Phi = [2; 1]

3 Converting a Continued Fraction to an ordinary Fraction

3.1 By "unfolding" the CF from the right

The natural way is just to "fold" the continued fraction from the right-hand end, simplifying each part in turn:
[ 2; 1, 3, 4 ] =
2 +1
1 + 1
3 + 1
4
=
2 + 1
1 + 1
13/4
=
2 + 1
1 +4
13
=
2 + 1
17/13
=
2 + 13
17
=
47
17
A short-cut is to notice that
[ ... , a, b ] = [ ... , a + 1/b ]
and we can keep using this rule to reduce the CF all the way down to a single fraction:
  [ 2; 1, 3, 4 ]
= [ 2; 1, 3 + 1/4 ] = [ 2; 1, 13/4 ]
= [ 2; 1 + 4/13 ] = [ 2; 17/13 ]
= [ 2 + 13/17; ] = [47/17; ]
= 47/17
Later we see a simpler method that works from left to right.

3.2 Surprising results about the REVERSE of the CF list

Here is a table of the CFs for all the sevenths fractions between 1/7 and 7/7. Each fraction is given to several decimal places, in its CF list form and, using the previous section, with its alternative CF list ending:
1/7 = 0.142857 142857 142857 …= [ 0; 7 ]= [ 0; 6, 1 ]
2/7 = 0.285714 285714 285714 …= [ 0; 3, 2 ]= [ 0; 3, 1, 1 ]
3/7 = 0.428571 428571 428571 …= [ 0; 2, 3 ]= [ 0; 2, 2, 1 ]
4/7 = 0.571428 571428 571428 …= [ 0; 1, 1, 3 ]= [ 0; 1, 1, 2, 1 ]
5/7 = 0.714285 714285 714285 …= [ 0; 1, 2, 2 ]= [ 0; 1, 2, 1, 1 ]
6/7 = 0.857142 857142 857185 …= [ 0; 1, 6 ]= [ 0; 1, 5, 1 ]
You may have noticed the following patterns in the table: It is the last property that we will investigate in this section.
Are all the above properties coincidences? Let's try another fraction:
1/8 = 0.125 = [ 0; 8 ]= [ 0; 7, 1 ]
2/8 = 0.25 = [ 0; 4 ]= [ 0; 3, 1 ]
3/8 = 0.375 = [ 0; 2, 1, 2 ]= [ 0; 2, 1, 1, 1 ]
4/8 = 0.5 = [ 0; 2 ]= [ 0; 1, 1 ]
5/8 = 0.625 = [ 0; 1, 1, 1, 2 ]= [ 0; 1, 1, 1, 1, 1 ]
6/8 = 0.75 = [ 0; 1, 3 ]= [ 0; 1, 2, 1 ]
7/8 = 0.875 = [ 0; 1, 7 ]= [ 0; 1, 6, 1 ]
This time the decimal fractions do not share the same repeating cycle and are not infinitely long but the final property - that all the CF lists after the initial zero appear in the table in reverse order - is still true!

So there are two "surprising results" and we can see examples of both in the tables at the start of this section.

3.2.1 Reversing a CF list will give a fraction with the same numerator

When we reverse the CF list of a fraction the new fraction will have the same numerator.
If we let [ a0; a1, ... , an−1, an ] be A/B > 1 which means that a0 > 0 and also
if we let [ a0; a1, ... , an−1 ] be C/D
then reversing the CF for A/B gives
[ an; an−1, ... , a0 ] which is A/C
For example: [1;1,1,2] = 8/5 = A/B and [1;1,1] = 3/2 = C/D so [2;1,1,1] = 8/3 = A/C

This result was known to Euler (see references below).

3.2.2 The first number can be transformed to produce the 1-complement of the fraction

We saw above that a finite CF's value is unchanged if we change the final term as follows:
if the last term X is 1, add it to the previous term: [1;2,3,1] = [1;2,4];
if the last term is bigger than 1, subtract one from it and append the 1 as a new final term.
We can do the same things to the first term after the integer part, but we obtain a different value:
If the value of [0; a, B] = x with a>1 and B the (value of the) rest of the list of CF terms, then the value of [0 ;1, a − 1,B] is 1 − x;
Since x⇒1−x is its own inverse operation, then the result applies transforming the second CF back to the first also.
If the integer term is not 0, then [A; a, B] = A + x ⇒ [A; 1, a−1, B] = A + (1−x)

This is very easily established by simple algebra since
[0; a,B] = 0+1/ (a+1/B) = B/(1+aB) whereas [0;1,a-1,B] = 1/(1+1(a-1+1/B)) = 1 − B/(1+aB)

The CF reversal result is proved in an amazing way by Harvey Mudd College's Professor of Mathematics: Art Benjamin in the first of these references:

Euler showed that the CFs [ a1; a2, ... an] and its reversal [ an; an-1, ... a1 ] have the same numerators but we must note that the first and last terms in both CFs are non-zero: see Davenport's book in the References section at the foot of this page.

3.3 The Stern-Brocot Fraction tree and CFs

On another page we looked at making a simple tree of all the fractions. If we restrict fractions to mean pure fractions, positive but less than 1, then, starting from 0/1 and 1/1 as our starting row we can keep making new rows by copying the old row and between every fraction inserting a new one:
oldNEWold
aa + bb
pp + qq
Level 10/11/1
Level 20/11/21/1
Level 30/11/31/22/31/1
Level 40/11/41/32/51/23/52/33/41/1
Level 50/11/51/42/71/33/82/53/71/24/73/55/82/35/73/44/51/1
If we now find the CFs for each of these, a pleasant surprise is that the CFs of level L's new fractions are all the ways writing L as a sum of smaller numbers! These are called compositions of L and include the number L as a composition too.
For the difference between a partition of a number and a composition of a number see the same link as above.
Remember that any CF can be written both as a list of terms that end in 1 or else end in a number greater than 1 so every fraction has two CFs.
For instance The same applies to every row.

See The Stern-Brocot Tree on the Fractions in the Farey Series and the Stern-Brocot Tree page at this site.

3.4 A Fraction ↔ CF Calculator

The and buttons will convert a Fraction to a CF and vice-versa and the converted value is shown in the or boxes too. Note a CF is input as and any following numbers are separated by commas: .
Fraction ↔ CF C A L C U L A T O R
+
Fraction CF

[ ]

R E S U L T S


calculator: Euclid's Algorithm Fractions Expressions Square roots Quadratics Best Approxs. Silver Means Negatives Combined CF in a new window
Here are some investigations for you to do:

3.4.1/ You do the maths... /

Use the Calculator above.
  1. Make a list of the CF lists for all the fractions less than 1 with
    1. a denominator of 5 (1/5, 2/5, 3/5, 4/5)
    2. a denominator of 6
    3. denominators 7 and 8 are above in this section
    4. a denominator of 9
    The calculator link above is useful as it keeps the results in a window so you can use cut-and-paste. Use your results to answer the following questions.
    CFs for N/D:
    ↓DN→12345678
    5 [0; 5]
    [0; 4, 1]
    [0; 2, 2]
    [0; 2, 1, 1]
    [0; 1, 1, 2]
    [0; 1, 1, 1, 1]
    [0; 1, 4]
    [0; 1, 3, 1]
    6 [0; 6]
    [0; 5, 1]
    [0; 3]
    [0; 2, 1]
    [0; 2]
    [0; 1, 1]
    [0; 1, 2]
    [0; 1, 1, 1]
    [0; 1, 5]
    [0; 1, 4, 1]
    7 [0; 7]
    [0; 6, 1]
    [0; 3, 2]
    [0; 3, 1, 1]
    [0; 2, 3]
    [0; 2, 2, 1]
    [0; 1, 1, 3]
    [0; 1, 1, 2, 1]
    [0; 1, 2, 2]
    [0; 1, 2, 1, 1]
    [0; 1, 6]
    [0; 1, 5, 1]
    8 [0; 8]
    [0; 7, 1]
    [0; 4]
    [0; 3, 1]
    [0; 2, 1, 2]
    [0; 2, 1, 1, 1]
    [0; 2]
    [0; 1, 1]
    [0; 1, 1, 1, 2]
    [0; 1, 1, 1, 1, 1]
    [0; 1, 3]
    [0; 1, 2, 1]
    [0; 1, 7]
    [0; 1, 6, 1]
    9 [0; 9]
    [0; 8, 1]
    [0; 4, 2]
    [0; 4, 1, 1]
    [0; 3]
    [0; 2, 1]
    [0; 2, 4]
    [0; 2, 3, 1]
    [0; 1, 1, 4]
    [0; 1, 1, 3, 1]
    [0; 1, 2]
    [0; 1, 1, 1]
    [0; 1, 3, 2]
    [0; 1, 3, 1, 1]
    [0; 1, 8]
    [0; 1, 7, 1]
  2. A composition of N is a sequence (list) of 1 or more positive (non-zero) numbers that sum to L.
    Numbers can be repeated (so the lists are not always sets) and the order of the numbers in the list matters so that {1,1,2}, {1,2,1} and {2,1,1} are classed as different partitions of 4.
    1. Prove that there are 2N−1 paritions of N.
    2. Prove that exactly half of partitions of N end in 1 (and exactly half do not).
    3. Prove that there are 2L−2 new fractions on level L of the Stern-Brocot Fraction tree.
  3. Some fractions have a CF which, after the initial 0 is the same when reversed:
    e.g.
    1/6 = [0; 6]
    6/7 = [0; 1, 5, 1]
    5/8 = [0; 1, 1, 1, 1, 1 ]
    Such sequences are called palindromes or palindromic sequences.
    Find the fractions which do not have a palindromic CF in the table above.
    2/7, 3/7, 4/7, 5/7
    2/9, 4/9, 5/9, 7/9

4 Continued Fractions for decimal fractions?

If we look at irrational numbers (numbers which cannot be written exactly as a fraction) we will find no pattern in their decimal fractions. For instance, here is √2 to 200 decimal places (read as text, left to right, line by line):
41421 35623 73095 04880 16887 24209 69807 85696 71875 37694
80731 76679 73799 07324 78462 10703 88503 87534 32764 15727
35013 84623 09122 97024 92483 60558 50737 21264 41214 97099
93583 14132 22665 92750 55927 55799 95050 11527 82060 57147
...
Indeed, it is not too difficult to show that, if any decimal fraction ever repeats, then it must be a proper fraction, that is a rational number - see the references section at the foot of this page.
The converse is also true, i.e. that every rational number has a decimal fraction that either stops or eventually repeats the same cycle of digits over and over again for ever.

There is a pleasant surprise here since every square-root has a repeating pattern in its continued fraction.

But what about continued fractions for numbers which we only have in the form of a decimal? There are two methods of converting them into continued fractions: using the decimal itself or finding a proper fraction for the decimal number. Both methods are explained here.

4.1 Direct conversion of a decimal to a CF

If we look again at the jigsaw-squares method at the top of this page or further down at Euclid's algorithm then both use the whole number of times one number goes into another. Really all we are using in that case is the whole number part of the value. With decimal numbers, we already have that part - it is just the part before the decimal point!

The method is very easy on a calculator when you use the subtract button and the 1/x or x-1 button only!

Input the decimal number.

  1. Write down the whole number part (before the decimal point) as the next value in the CF list.
    For an input value less than 1, this will be 0.
  2. Subtract it from the display to get a value less than 1.
  3. If 0 is showing, stop
    otherwise press the 1/x button
  4. Start again with the new number which is bigger than 1 in the display.
You can try this on √2, e, π or any computed value but be careful as rounding errors will eventually build up and then the CF terms are meaningless.

For example, 2·875.


2.875 = [2; 1, 7]
Checking shows that when we expand [2; 1, 7] we have 23/8 which is 2 + 7/8 = 2.875 exactly.

4.1.1/ You do the maths... /

You might find the calculator Combined Continued Fraction Calculator useful in this section.

  1. Convert 64/29 into a decimal fraction and approximate it by rounding it off to 3 dps.
    Now convert that decimal fraction to a CF using the method of the last section.
    Was it easy to see when to stop if the real value of our decimal was 64/29?
    64/29 = 2.206896551724138 = 2.207 to 3 dps
    • write down 2 and subtract it: 0.207
    • 1/x gives 4.83091787439614
    • write down 4, subtract it: 0.83091787439614
    • 1/x gives 1.20348837209302
    • write down 1, subtract it: 0.20348837209302
    • 1/x gives 4.91428571428579
    • write down 4, subtract it: 0.91428571428579
    • 1/x gives 1.09374999999991
    • write down 1, subtract it: 0.09374999999991
    • 1/x gives 10.66666666667691
    • write down 10, subtract it: 0.66666666667691
    • 1/x gives 1.49999999997695
    • write down 1, subtract it: 0.49999999997695
    • 1/x gives 2.0000000000922
    • write down 2, subtract it: 0.0000000000922
    The displayed number is now almost 0 so stop.
    2.207 = [2; 4, 1, 4, 1, 10, 1, 2 ]
    Converting the CF to a fraction gives 2207/1000 = 2.207 so the CF is correct and we were right to stop when we did discarding the residual value as rounding error.

4.2 Converting a Decimal to a Fraction

If we have a number in the form of decimal fraction, such as 2·875 then we can always represent it as an exact proper fraction by using a denominator which is a big enough power of 10: For instance, Since all the example decimals are all now fractions, we can now use Euclid's algorithm from earlier on this page to express them as continued fractions.
There is no need to reduce the proper fractions to their lowest forms - Euclid's algorithm will still give the correct CF.

This time, when we convert 2·875 to an equivalent fraction we get 2875/1000 and Euclid's algorithm gives:

2875 = 2 ×1000 + 875
1000 = 1 × 875 + 125
875 = 7 × 125
so 2875/1000 = [2; 1, 7] exactly.
If 2·875 was an exact value then its CF is exactly [2; 1, 7]; if it was only an approximation then [2; 1, 7] is as accurate as we can get as a CF. So, provided we have a finite number of decimal places, we can get a CF equivalent to that decimal value. But suppose we know a number exactly as a decimal and that decimal value does not end? An example is 0.3333.... which we might spot is exactly 1/3.

4.2.1 A CF Calculator for Expressions

The following Calculator might help.
The calculations are from the evaluated numerical value of the input expression which is limited to about 16 places of decimals. Eventually the CF terms will be solely due to rounding error. This is detected and the CF terms shown are correct (except for the final term sometimes), with ... indicating the limit of the conversion.
Since the Calculator uses your Browser's Javascript capability, the expressions you type in needs to use JavaScript syntax:
Expression → CF C A L C U L A T O R
Number or expression:
the CF of

R E S U L T S


calculator: Euclid's Algorithm Fractions Expressions Square roots Quadratics Best Approxs. Silver Means Negatives Combined CF in a new window

5 Proper Fractions and Continued Fraction Patterns

Before we branch out into infinite continued fractions in the following sections, let's pause to look at some patterns in (proper) fractions first.

5.1 CFs of ( 1 + 1/n )2

To start off your investigations, what patterns can you spot in this table:
n(1+1/n)2 = CF
1(1+1/1)2[ 4; ]
3(1+1/3)2[ 1; 1,3,1,1 ]
5(1+1/5)2[ 1; 2,3,1,2 ]
7(1+1/7)2[ 1; 3,3,1,3 ]
9(1+1/9)2[ 1; 4,3,1,4 ]
11(1+1/11)2[ 1; 5,3,1,5 ]
13(1+1/13)2[ 1; 6,3,1,6 ]
15(1+1/15)2[ 1; 7,3,1,7 ]
n(1+1/n)2 = CF
2(1+1/2)2[ 2; 4 ]
4(1+1/4)2[ 1; 1,1,3,2 ]
6(1+1/6)2[ 1; 2,1,3,3 ]
8(1+1/8)2[ 1; 3,1,3,4 ]
10(1+1/10)2[ 1; 4,1,3,5 ]
12(1+1/12)2[ 1; 5,1,3,6 ]
14(1+1/14)2[ 1; 6,1,3,7 ]
16(1+1/16)2[ 1; 7,1,3,8 ]
It seems there are two patterns here, one for even n and one for odd.
Can you make the top lines also fit these patterns?
(1+1/1)2 = [ 4; ] = [1; 0, 3, 1, 0]
(1+1/2)2 = [ 2; 4 ] = [1; 0, 1, 3, 1]

Check by writing out the full fraction form.
We meet this transform later as the collapse a 0 formula.

5.2 CFs of ( 1 + 1/n )3

Extending the fractions to cubes, we have the following table:
CFs for (1+1/n)3
 1=[ 8; ]
 7=[ 1; 2,33,1,4 ]
13=[ 1; 4,60,1,3,2 ]
19=[ 1; 6,87,1,3,3 ]
 2=[ 3; 2,1,2 ]
 8=[ 1; 2,2,1,3,1,1,2,3 ]
14=[ 1; 4,2,1,6,1,1,2,2,2 ]
20=[ 1; 6,2,1,9,1,1,2,2,3 ]
 3=[ 2; 2,1,2,3 ]
 9=[ 1; 2,1,2,4,2,2,1,2 ]
15=[ 1; 4,1,2,7,2,2,1,1,2 ]
21=[ 1; 6,1,2,10,2,2,1,1,3 ]
 4=[ 1; 1,20,3 ]
10=[ 1; 3,47,3,2 ]
16=[ 1; 5,74,3,1,2 ]
22=[ 1; 7,101,3,1,3 ]
 5=[ 1; 1,2,1,2,11 ]
11=[ 1; 3,2,1,5,11,2 ]
17=[ 1; 5,2,1,8,11,1,2 ]
23=[ 1; 7,2,1,11,11,1,3 ]
 6=[ 1; 1,1,2,2,1,12 ]
12=[ 1; 3,1,2,5,1,11,2 ]
18=[ 1; 5,1,2,8,1,11,3 ]
24=[ 1; 7,1,2,11,1,11,4 ]
Patterns here are certainly harder to spot but they seem to go in sixes this time.
David Terr wrote to me in October 2013 with the following patterns in the cubes:
Mod 6 formCF
(1+1/(6n+1))3: [ 1; 2n, 27n+6, 1, 3, n ]
(1+1/(6n+2))3: [ 1; 2n, 2, 1, 3n, 1, 1, 2, 2, n ]
(1+1/(6n+3))3: [ 1; 2n, 1, 2, 3n+1, 2, 2, 1, 1, n ]
(1+1/(6n+4))3: [ 1; 2n+1, 27n+20, 3, 1, n ]
(1+1/(6n+5))3: [ 1; 2n+1, 2, 1, 3n+2, 11, 1, n ]
(1+1/(6n))3: [ 1; 2n−1, 1, 2, 3n−1, 1, 11, n ]
These patterns are indeed true and his discovery suggests many similar questions to ask about powers of finite fractions and the form of their continued fraction.

But now we turn our attention to some infinite continued fractions which, maybe surprisingly, have some very simple forms.

6 Continued fractions for square-roots

6.1 A Simple Way to find √n

Here is another way to introduce or "discover" continued fractions based on finding the square-root of a number. This method differs from those earlier at the top of the page in that it gives us an infinitely long continued fraction, but this turns out to have some very useful properties.

Take, for example, √5. The nearest square below 5 is 4, so we know √5 begins with 2. Let's write:

√5 = 2 + x
5 = (2 + x)2
   = 4 + 4x + x2
   = 4 + x( 4 + x)
If we rearrange the last line we have
5 − 4 = x(4 + x)
1 = x(4 + x)
x = 1
4 + x
Now we have a formula for x, we can use it on the right-hand side and get:
x  →  1  →  1  →  ...
4 + x 4 +
1
4 + x
 
When we repeat this, we get a continued fraction which never ends!
If we put x back in the original line: √5 = 2 + x
√5 = 2 + 1  = 2 + 1  = 2 + 1
4 + x 4 + 1 4 + 1
4 + x 4 + 1
4 + x
Here is another example for √6.
√6 = 2 + x
6 = (2 + x)2 = 4 + 4x + x2
2 = 4x + x2 = x(4 + x)
x = 2 = 2
4 + x4 + 2
4 + x
This time, we can do some careful simplification by dividing top and bottom by 2:
x = 2 = 2 = 1
4 + x4 + 2 2 + 1
4 + x 4 + x
So this time our infinite continued fraction for √6 is
√6 = 2 + 1
2 + 1
4 + 1
2 + 1
4 + ...
This is our first example of a general continued fraction since the numerators of the fractions are not 1. It happens that each of the above simplify to give a simple CF. Can we do this in general?

Suppose n is not a perfect square and that √n = a + x where a2 is any square number less than n. Using the method above, what is the general formula for √n as a continued fraction without reducing the numerators to 1?

√n = a + x
Square both sides:
n = a2 + 2ax + x2
Rearranging to make x a factor:
n − a2 = x ( 2a + x)
x = n − a2
2a + x

Substituting for x in the top equation:
√n = a + x = a + n − a2 = a + n − a2 = ...
2a + x2a + n − a2
2a + x

6.1.1/ You do the maths... /

  1. Try this method with √7 for both of the two smaller squares a = 1, a = 2 .
    a = 1
    √7 = 1 + 6
    2 + 6
    2 + 6
    2 + 6
    2 + ...
    a = 2
    √7 = 2 + 3
    4 + 3
    4 + 3
    4 + 3
    4 + ...

6.1.2 What use is an infinite continued fraction?

Is there any advantage in this infinitely long fractional representation? Yes!
We can stop the continued fraction at any point and then reduce the shortened form to an ordinary fraction (see below). Each time the fraction is a better approximation to the actual square-root than if we stopped it at any earlier point.
In fact, the approximations found by this method are the best approximations possible when the numerators are 1.

6.2 A variation with numerators that are always 1

Sometimes with the simple way to find √n as a CF, we get numerators which are 1, as with √5 above, but not always.
Sometimes it is not too difficult to divide numerators and denominators to reduce the numerator to one as in the √6 example, but in other cases it is much more complicated.

There is a method which will find the exact CF for any (whole-number) square-root and the numerators are always 1. It is not quite as simple as the method above, but it only uses the mathematics and algebra of secondary school.
We will need this useful technique:

6.2.1 Eliminating Square-roots from denominators

The important part uses a special algebraic method that applies only to square roots. It changes a fraction with a square-root in the denominator to a fraction with a square root on top.

If we have a fraction with (√A + B) in the denominator then the secret is to multiply top and bottom by (√A − B), that is, keep the numbers the same but just change the sign between them. If we had √A − B in the denominator then we would use √A + B instead. If you are good at algebra you will recognise that x+y and x−y are the two factors of x2 − y2. You can multiply out the brackets to check this.
For our denominator, we now have (√A + B)(√A − B) which expands to (A − B2) and, since A and B are integers, this is a whole number!

Here is a worked example:

3 = 3(√27 − 4) = 3 (√27 − 4) = 3 (√27 − 4)
√27 + 4(√27 + 4)(√27 − 4)27 −1611
So we have transformed a fraction with a square-root term in the denominator to one with a square root term in the numerator.

6.2.2 An algorithm to find a simple CF for any square-root

In the following we assume n is not an exact square number.
The steps in the algorithm for finding a simple CF for √n are:
Step 1:
Find the nearest square number less than n
Let's call it m2, so that m2<n and n<(m+1)2.
Remember this value as you will need it when you repeat this step!
For example, if n=14 and we are trying to find a CF for √14 then here are two quick ways to find this number
  • 9 = 32 is the nearest square below 14, so m = 3 and m2=9 < n < (m+1)2=16
  • use your calculator:
    and just ignore the part after the decimal point! The number showing is m.
    For our example, √14 is 3.741... so the number we want initially is 3
This whole number part starts off our list of numbers for the continued fraction and is used whenever we return to this step. For instance, the next time we do this step in our example is with (√14 + 3)/5. Since the nearest whole number below √14 is 3, then we look at (3+3)/5= 6/5 and now the integer part is 1.

Now, √n = m + 1/x where n and m are whole numbers.

Step 2:
Rearrange the equation of Step 1 into a form involving the square root which will appear as the denominator of a fraction: x = 1 / (√n - m)
Step 3:
We now have a fraction with a square-root in the denominator. Use the method above to eliminate the square-root from the denominator.
In this case, multiply top and bottom by (√ n + m) and simplify.
either Step 4A:
stop if this expression is the square root plus the original first integer.
or Step 4B:
otherwise start again from Step 1 but using the expression at the end of Step 3
The square root as a continued fraction is the initial whole number from Step 1 and the period is all the numbers but adding the final integer of Step 4 to the initial integer to form the period.

We will take √14 and see how we find the continued fraction [ 3; 1,2,1,6, 1,2,1,6, 1,2,1,6, ... ] = [ 3; 1,2,1,6 ] using the algorithm above:

In order to distinguish the x's at each stage repeating the steps of the method, we will use subscripts to distinguish the different x's as x changes: x1, then x2, x3 and so on:

Finding...Step 1Step 2Step 3
√14:
√14 =3 +
1
--
x1
x1 =1
√14 − 3
=
1(√14 + 3)
--
(√14 − 3)(√14 + 3)
=
√14 + 3
--
14 − 9
=
√14 + 3
--
5
x1 =
√14 + 3
--
5
=1 +
1
--
x2
x2 =
5
--
√14 − 2
=
5(√14 + 2)
--
(√14 − 2)(√14 + 2)
=
5 (√14 + 2)
--
14 − 4
=
√14 + 2
--
2
x2 =
√14 + 2
--
2
=2 +
1
--
x3
x3 =
2
--
√14 − 2
=
2(√14 + 2)
--
(√14 − 2)(√14 + 2)
=
2 (√14 + 2)
--
14 − 4
=
√14 + 2
--
5
x3 =
√14 + 2
--
5
=1 +
1
--
x4
x4 =
5
--
√14 − 3
=
5(√14 + 3)
--
(√14 − 3)(√14 + 3)
=
5 (√14 + 3)
--
14 − 9
= √14 + 3
We stop the algorithm now since √14 + 3 has appeared before on the first line. Substituting for the values of the x's we have:

√14 =3 +
1
--
x1
=3 +
1
--
1 +
1
--
x2
=3 +
1
--
1 +
1
--
2 +
1
--
x3
=3 +
1
--
1 +
1
--
2 +
1
--
1 +
1
--
x4
=3 +
1
--
1 +
1
--
2 +
1
--
1 +
1
--
√14 +3
= [3; 1, 2, 1, √14 + 3]
Now we substitute the first expression for √14 into the last one, so that the final √14 + 3 becomes 3+3+1/... and √14 is [3; 1,2,1, 6, 1,2,1,√14 + 3].
One further substitution gives the cyclic repetition of the pattern and we have our final continued fraction for √14 as [3; 1,2,1,6, 1,2,1, 6, 1,2,1,6, ...]

This method is completely general and applies to all square roots.

6.3 All square-root continued fractions eventually repeat

All square-root simple CFs end with a periodic pattern that repeats forever.

6.3.1 Notation for Periodic CFs

Using the method above method, we can produce the following table of some square root continued fractions. What patterns can you spot in the table? To find out more, look at the books in the References section at the bottom of this page.
√2 = [ 1; 2, 2, 2, 2, 2, 2, 2, 2, ... ] = 1 then repeat 2
√3 = [ 1; 1, 2, 1, 2, 1, 2, 1, 2, ... ] = 1 then repeat 1,2
√4 = 2
√5 = [ 2; 4, 4, 4, 4, 4, 4, 4, 4, ... ] = 2 then repeat 4
√6 = [ 2; 2, 4, 2, 4, 2, 4, 2, 4, ... ] = 2 then repeat 2,4
√7 = [ 2; 1, 1, 1, 4, 1, 1, 1, 4, ... ] = 2 then repeat 1,1,1,4
√8 = [ 2; 1, 4, 1, 4, 1, 4, 1, 4, ... ] = 2 then repeat 1,4
√9 = 3
√10= [ 3; 6, 6, 6, 6, 6, 6, 6, 6, ... ] = 3 then repeat 6
√11= [ 3; 3, 6, 3, 6, 3, 6, 3, 6, ... ] = 3 then repeat 3,6
√12= [ 3; 2, 6, 2, 6, 2, 6, 2, 6, ... ] = 3 then repeat 2,6
We clearly need a notation for the periodic part of a CF.
Notation: we will put a line over the repeating part, in the same way that repeating decimals are often written, for example:
√ 2 = [ 1; 2, 2, 2, 2, ... ] = [ 1; 2 ]
[a; b,  c, d,  c, d, .... ] = [ a; b, c, d ]
The repeating part is always the final part of a CF since it indicates numbers that repeat in a cycle for ever.

6.4 A Table of CFs of Square roots up to √99

Here is a table of the square-roots of numbers up to 100:
√n[ a; Period ]
√1[ 1; ]
√2[ 1; 2 ]
√3[ 1; 1, 2 ]
√4[ 2; ]
√5[ 2; 4 ]
√6[ 2; 2, 4 ]
√7[ 2; 1, 1, 1, 4 ]
√8[ 2; 1, 4 ]
√9[ 3; ]
√10[ 3; 6 ]
√11[ 3; 3, 6 ]
√12[ 3; 2, 6 ]
√13[ 3; 1, 1, 1, 1, 6 ]
√14[ 3; 1, 2, 1, 6 ]
√15[ 3; 1, 6 ]
√16[ 4; ]
√17[ 4; 8 ]
√18[ 4; 4, 8 ]
√19[ 4; 2, 1, 3, 1, 2, 8 ]
√20[ 4; 2, 8 ]
√21[ 4; 1, 1, 2, 1, 1, 8 ]
√22[ 4; 1, 2, 4, 2, 1, 8 ]
√23[ 4; 1, 3, 1, 8 ]
√24[ 4; 1, 8 ]
√25[ 5; ]
√26[ 5; 10 ]
√27[ 5; 5, 10 ]
√28[ 5; 3, 2, 3, 10 ]
√29[ 5; 2, 1, 1, 2, 10 ]
√30[ 5; 2, 10 ]
√31[ 5; 1, 1, 3, 5, 3, 1, 1, 10 ]
√32[ 5; 1, 1, 1, 10 ]
√33[ 5; 1, 2, 1, 10 ]
√34[ 5; 1, 4, 1, 10 ]
√35[ 5; 1, 10 ]
√36[ 6; ]
√37[ 6; 12 ]
√38[ 6; 6, 12 ]
√39[ 6; 4, 12 ]
√40[ 6; 3, 12 ]
√41[ 6; 2, 2, 12 ]
√42[ 6; 2, 12 ]
√43[ 6; 1, 1, 3, 1, 5, 1, 3, 1, 1, 12 ]
√44[ 6; 1, 1, 1, 2, 1, 1, 1, 12 ]
√45[ 6; 1, 2, 2, 2, 1, 12 ]
√46[ 6; 1, 3, 1, 1, 2, 6, 2, 1, 1, 3, 1, 12 ]
√47[ 6; 1, 5, 1, 12 ]
√48[ 6; 1, 12 ]
√49[ 7; ]
√50[ 7; 14 ]
√n [ a; Period ]
√51[ 7; 7, 14 ]
√52[ 7; 4, 1, 2, 1, 4, 14 ]
√53[ 7; 3, 1, 1, 3, 14 ]
√54[ 7; 2, 1, 6, 1, 2, 14 ]
√55[ 7; 2, 2, 2, 14 ]
√56[ 7; 2, 14 ]
√57[ 7; 1, 1, 4, 1, 1, 14 ]
√58[ 7; 1, 1, 1, 1, 1, 1, 14 ]
√59[ 7; 1, 2, 7, 2, 1, 14 ]
√60[ 7; 1, 2, 1, 14 ]
√61[ 7; 1, 4, 3, 1, 2, 2, 1, 3, 4, 1, 14 ]
√62[ 7; 1, 6, 1, 14 ]
√63[ 7; 1, 14 ]
√64[ 8; ]
√65[ 8; 16 ]
√66[ 8; 8, 16 ]
√67[ 8; 5, 2, 1, 1, 7, 1, 1, 2, 5, 16 ]
√68[ 8; 4, 16 ]
√69[ 8; 3, 3, 1, 4, 1, 3, 3, 16 ]
√70[ 8; 2, 1, 2, 1, 2, 16 ]
√71[ 8; 2, 2, 1, 7, 1, 2, 2, 16 ]
√72[ 8; 2, 16 ]
√73[ 8; 1, 1, 5, 5, 1, 1, 16 ]
√74[ 8; 1, 1, 1, 1, 16 ]
√75[ 8; 1, 1, 1, 16 ]
√76[ 8; 1, 2, 1, 1, 5, 4, 5, 1, 1, 2, 1, 16 ]
√77[ 8; 1, 3, 2, 3, 1, 16 ]
√78[ 8; 1, 4, 1, 16 ]
√79[ 8; 1, 7, 1, 16 ]
√80[ 8; 1, 16 ]
√81[ 9; ]
√82[ 9; 18 ]
√83[ 9; 9, 18 ]
√84[ 9; 6, 18 ]
√85[ 9; 4, 1, 1, 4, 18 ]
√86[ 9; 3, 1, 1, 1, 8, 1, 1, 1, 3, 18 ]
√87[ 9; 3, 18 ]
√88[ 9; 2, 1, 1, 1, 2, 18 ]
√89[ 9; 2, 3, 3, 2, 18 ]
√90[ 9; 2, 18 ]
√91[ 9; 1, 1, 5, 1, 5, 1, 1, 18 ]
√92[ 9; 1, 1, 2, 4, 2, 1, 1, 18 ]
√93[ 9; 1, 1, 1, 4, 6, 4, 1, 1, 1, 18 ]
√94[ 9; 1, 2, 3, 1, 1, 5, 1, 8, 1, 5, 1, 1, 3, 2, 1, 18 ]
√95[ 9; 1, 2, 1, 18 ]
√96[ 9; 1, 3, 1, 18 ]
√97[ 9; 1, 5, 1, 1, 1, 1, 1, 1, 5, 1, 18 ]
√98[ 9; 1, 8, 1, 18 ]
√99[ 9; 1, 18 ]

The lengths of the periods in the above table form a series:
0,1,2,0,1,2,4,2,0,1,2,2,5,4,2,0,1,2,6,2,6,6,4,2,0...
where the 0s appear at positions which are perfect squares (so their square-roots are integers).
This is Sloane's A003285.

Is there a pattern behind this table? Justin Miller (University of Arizona) has a list of several patterns within the table (see References). Can you extend his table? Can you find a single overall unifying formula?

Was the table above produced by a computer program?
Yes! The algorithm is explained in Allenby and Redfern's book in the References here. Why not produce your own program and then you can extend the table further, using the values above to check your program (and mine!) The next section on Solving Quadratics, after the Calculator and You do the maths... looks at how you can find these for yourself, with or without a computer.

6.5 A Square-root ↔ CF Calculator

Any expression of the form (R ± √N)/S where R,N,S are integers will have a periodic CF. N must be positive but the others can be negative provided the expression when evaluated is positive. Select the sign before the square-root.
This Calculator lets you explore these expressions and converting to and from a periodic CF.
Optionally leave some input boxes empty and so use this Calculator for fractions and non-periodic CF conversion too.
The and buttons will convert values putting equivalents into the appropriate boxes too.
Square-root ↔ CF C A L C U L A T O R    
Fraction:
+
--

Continued Fraction:
[ ,
]

R E S U L T S

calculator: Euclid's Algorithm Fractions Expressions Square roots Quadratics Best Approxs. Silver Means Negatives Combined CF in a new window

6.5.1/ You do the maths... /

You might find the calculator Combined Continued Fraction Calculator useful in this section.

  1. What patterns do you notice in the table of square-roots above?
    Four easy ones first:
    1. What is special about the first number of the continued fraction?
      It is the whole number part of the square-root: the square root of the nearest square less than the number
    2. What is special about the last number in the periodic part?
      It is twice the first number in the CF (see previous question)
    3. What about the other numbers in the periodic part? Is there a pattern to them that they ALL have?
      Between the first number and the last number, the sequence is palindromic (the same when reversed)
  2. [n; 2n]
    1. Which numbers n have a square-root continued fraction of the form on the line above?
      2, 5, 10, 17, 26, ....
      Their CFs are [n; 2n ]
    2. What formula generates all these numbers
      n2 + 1
    3. Can you prove that all numbers generated by your formula have a square-root CF of this form?
      The proof is quite easy!
      Follow the steps above where we showed [ 1; 2, 2, 2, 2, 2 ... ] was √2, but replace the 2's by 2n's say since the general pattern here is [ n; 2n, 2n, 2n, 2n, ... ].
  3. [ n; n, 2n ]
    What numbers in the table have a square-root CF with this pattern?
    1. What is the formula this time?
      3, 6, 11, 18, 27, ...
      These are the numbers n2 + 2.
      CF of these square-roots is [n; n, 2n ]
    2. Again try to verify your results are always true.
  4. ..or spot the pattern in these sequences of square-roots:
    1. 3, 8, 15, 24, 35, ... n2 − 1 n2 − 1 = [ n-1; 1, 2n−2 ]
    2. 7, 14, 23, 34, 47, ... n2 − 2 n2 − 2 = [ n-1; 1, n-2, 1, 2n-2] if n>2
    3. 12, 39, 84, ... 9 n2 + 3 9 n2 + 3 = [ 3n; 2n, 6n]
    4. We have now covered the patterns of all the square-roots up to 13. There is another pattern that applies to some of these smaller numbers too - what pattern connects the CF lists for the square-roots of :
      6, 12, 20 and 30? n ( n + 1) = [ n; 2, 2n]
    5. So what about 13? What pattern starts with the square-roots of 13, 29 and 53?(2n+1)2 + 4 = [ 2n + 1; n, 1, 1, n, 4n+2]
  5. Elliott Landowne emailed me (16 Sept 2011) about the following pattern that he had spotted in the CFs of some square roots:
    √19 − 4 = [ 0; 2, 1, 3, 1, 2, 8 ]
    √54 − 7 = [ 0; 2, 1, 6, 1, 2, 14 ]
    √107 − 10 = [ 0; 2, 1, 9, 1, 2, 20 ]
    He thinks the general pattern is:
    • √( (3n + 1)2 + 2n + 1) − (3n + 1) = [ 0; 2, 1, 3n, 1, 2, 6n+2]
    Can you provide a proof of this?
  6. What other patterns can you find that cover most of the rest of the numbers up to 100?
    What square-roots are left over?

7 Solving Quadratics with Continued Fractions

7.1 Quadratic Equations and Continued Fractions

Many problems, when modelled in mathematics, involve a quadratic equation - i.e. an equation of the form
A x2 + B x + C = 0
where the A, B, C are numbers and we want to find values for x to make the equation true.

For instance, take x2 − 5 x − 1 = 0
Can you think of an x value for which this equation holds? We can rewrite the equation in a different way as:

x2 = 5 x + 1
and now we can divide both sides by x to get:
x = 5 + 1/x
This means that wherever we have x, we can replace it by 5 + 1/x for example to get:
x = 5 + 1/x = 5 + 1/(5 + 1/x)
We can clearly replace the x again and again and get an infinite (periodic) continued fraction:
x = 5 + 1/x = 5 + 1/(5 + 1/x) = ... = [5; 5, 5, 5, ...]

7.2 But what about the other solution to the quadratic?

Anand Ramanathan asks an interesting question about the meaning of a continued fraction:

Suppose that x is the continued fraction [2; 2] = 2 + 1/(2 + 1/...). We can write this as x = 2 + 1/x and, by multiplying both sides by x we have the quadratic equation

x2 = 2x + 1 or x2 − 2x − 1 = 0
which we can solve to find two solutions for x namely:
x = 1 + √2 or x = 1 − √2
The first is +2·414... and the second is −0·414... and Anand's question is
But what about the other value?
Since both values satisfy the quadratic equation then both satisfy x = 2 + 2/x
so how do we choose?
Certainly, both values satisfy x = 2+1/x and so both are legitimate candidates for the value of [2; 2] as is shown here:
x = 1+√2 1−√2
2+1/x=
2 + 1
--
1+√2
2 + 1
--
1−√2
add fractions
2(1+√2) + 1
--
1+√2
2(1−√2) + 1
--
1−√2
Simplify
3+2√2
--
1+√2
3−2√2
--
1−√2
multiply by 1±√2
top and bottom
(3+2√2)(1-√2)
--
(1+√2)(1−√2)
(3−2√2)(1+√2)
--
(1−√2)(1+√2)
expand brackets
3−4 − √2
--
1 − 2
3−4 + √2
--
1 − 2
Simplify
−1 − √2
--
−1
−1 + √2
--
−1
= x1+√2 1−√2
This means that [2; 2] is ambiguous - it can mean either of two values.
As always in mathematics, we therefore make an arbitrary choice - a convention - that the continued fraction a;b,c,d,... always represents a positive value and we prefix a continued fraction with a minus sign to represent a negative value.
With this convention we can still represent the other value: 1 − √2 = −0·414... as follows:
since 1 − √2 is negative, then √2 − 1 is positive and it has a continued fraction representation as [0; 2].
Thus 1−√2 is −[0; 2].

7.2.1/ You do the maths... /

  1. Repeat the above for [A; A] by writing it as x = A + 1/x and finding a quadratic in x to solve (using the Formula).
    Show that one root is positive (and, if A>1 then that root is also > 1) and the other root is negative but less than 1.

7.3 The Golden section and a quadratic equation

We have seen several times in the other Fibonacci Web pages at this site (see, for example, Formulae for Phi) that Phi is a solution to the quadratic equation x2 −x − 1 = 0.
Rearranging this equation gives x2 = x + 1
and so dividing both sides by x (since x is not zero) we have x = 1 + 1/x
which leads directly a continued fraction for the (positive) root, the value of x which we called Phi:
x = 1 + 1/x = 1 + 1/( 1 + 1/x) = ... = [1; 1]
Of all continued fractions, this is the simplest.
The mathematician Lagrange (1736-1813) proved
the Continued Fraction Theorem
a quadratic equation with integer coefficients has a periodic continued fraction for each of its real roots.

7.3.1/ You do the maths... /

You might find the calculator Combined Continued Fraction Calculator useful in this section.

  1. Find the 2 roots and a continued fraction for a root of these quadratic equations:
    1. x2 + x = 1
    2. x2 − 2x = 1
    1. x2 + x = 1 ⇒ x2 = −x + 1 ⇒ x = −1 + 1/x
      x = [-1; -1, -1, -1, ... ] = -[1;1, 1, 1, ...] = -Phi
    2. x2 − 2x = 1 ⇒ x2 = 2x + 1 ⇒ x = 2 + 1/x
      x = [2; 2, 2, 2, ...] = 1 + √2
  2. What happens if we try to find square-roots of whole numbers using this method? For example, the square root of 2 is a solution to x2 − 2 = 0?
    How does the answer to the second part of the previous question give a continued fraction for √2?

7.4 Quadratics CF Calculator

Note: Empty input boxes have the following default values:
x2 + x +

The Calculator will find the roots of a given quadratic together with their CFs.
Given two roots in the form (R ± √N )/S it will find the integer-coefficient quadratic with those roots.
k( a x2 + b x + c ) = 0 ⇒ x =   R ± √ N  or   −b ± b2 − 4 a c
S2 a
R = −b
N = b2−4ac
S = 2a
a = S/2
b = −R
c = R2 − N
2 S

The quadratic may be multiplied or divided by any constant k.

Quadratic CF C A L C U L A T O R
x2 + x +
has roots
± √

R E S U L T S


calculator: Euclid's Algorithm Fractions Expressions Square roots Quadratics Best Approxs. Silver Means Negatives Combined CF in a new window

8 Best Rational Approximations to Real Numbers

8.1 A Calculator to search for best rational approximations

We can just search all fractions with an increasingly larger denominator and find which are closer to the value we are approximating than any previous fraction (with a smaller denominator).

Although the convergents of simple CFs only are the best approximations, meaning that no smaller denominator will produce a better approximation, not all the "best approximations" are in the list of convergents. The others are those with an identical initial part of the CF of the value being approximated and a final number which can be smaller or the same as the CF term. So in such a list we will find all the convergents of the CF of the value being approximated.
You can experiment with the following Calculator which also allows you to find the best numerator for a given denominator in a fraction approximation of the given numerical value.
As with the CF Calculator for Expressions earlier on this page you can also give an expression to be evaluated in the value box or just a decimal number.

8.1.1 Best Approximating Fraction Calculator

This Calculator will take any positive value and look at all the fractions, with a denominator up to a specified maximum, and find the best fractions for it.
By best here, we mean those fractions which are closer than any with a smaller denominator.
Alternatively, you can try to find the nearest approximation with a particular denominator or range of denominators and the nearest fraction for every denominator in the range is found.
This calculator also computes the error of the approximation and shows the continued fraction for each approximation found. Continued fractions are very useful for finding fractions that are the best approximations to any value.
The value to be approximated can be an expression such as  sqrt(2)+1  or  pi/3 .
The Mathematical functions and constants available in the value to be approximated are:
Note that they are case-sensitive so must be input exactly as given in the left-hand column.
NameDescriptionExample and Notes
+ – * / ( )Arithmetic operations and brackets2*3+4/(5-1) → 7
abs the absolute value (positive size) abs(-3.9) → 3.9
abs(3.9) → 3.9
acos arc cosine, the angle for a given cosine acos(0.5) → 1.0471975511965979
acos(0.5)/Pi*180 → 60.00000000000001 (degrees)
asin arc sine, the angle for a given sine asin(sqrt(3)/2)/Pi*180 → 60 (degrees)
atan arc tangent, the angle A for a given tangent
-π/2 ≤ A ≤ π/2
4 * atan(1) → 3.141592653589793
which is π
atan2 ang2(y,x) is the anticlockwise angle A at (0,0)
between the x>0 axis and the point(x,y)
-π ≤ A ≤ π
atan2(1,-1)/Pi*180 → 135 (degrees)
ceil round up to the nearest integer ceil(-3.9) → -3, ceil(-3.1) → -3
ceil(3.1) → 4, ceil(3.9) → 4
cos cosine of an angle (in radians) cos(60*Pi/180) → 0.5000000000000001
cos(Pi) → -1
E e E → 2.718281828459045
exp exp(p) means e to the power of pexp(1) → 2.718281828459045
floor round down to the nearest integer floor(-3.9) → -4, floor(-3.1) → -4
floor(3.1) → 3, floor(3.9) → 3
log log to base e
logb(x) is log(x)/log(b)
log(E) → 1
log(sqrt(E)) → 0.5
log(3)/log(2) → 1.584962500721156 is log2(3)
Phi golden section Φ=(√5 + 1)/2Phi → 1.618033988749895
phi golden section φ=(√5 – 1)/2phi → 0.6180339887498949
Pi, pi πPi → 3.141592653589793
pow pow(x,p) means xp pow(2,3) → 8
pow(3,2) → 9
pow(2,log(3)/log(2)) → 3
random a random number between 0 and 1 random() → 0.5987956806696484
random() → 0.85393295517764
round round to the nearest integer round(-3.9) → -4, round(-3.1) → -3
round(3.9) → 4, round(3.1) → 3
sin sine of an angle (in radians) sin(Pi/2) → 1
sqrt square root sqrt(2) → 1.4142135623730951
tan tangent of an angle (in radians) tan(Pi/4) → 0.9999999999999999
>   >=
<   <=
==   !=
comparisons between two values, gives true or false
use in the Conditional part of (?:) expressions
Pi>2 → true
cos(Pi/3)==0.5 → false but should be true
This is caused by rounding in the final computed digit
Better is: abs(cos(Pi/3)-0.5)<0.0000001 → true
( expr ? t : f)conditional expression;
if expr is true then t is evaluated as the result,
if false then f is evaluated as the result
(sqrt(10)>=3 ? 4 : 3) → 4
fib, Fib or FFib(n) is the n-th Fibonacci numberF(10) → 55, Fib(-5) → 5
luc, Luc or LLuc(n) is the n-th Lucas numberL(10) → 123, Luc(0) → 2
GG(a,b,n) is the n-th General Fibonacci number where G(a,b,0)=a,G(a,b,1)=bG(3,1,5) → 14, G(1,3,-4) → -4
Best approximating Fraction C A L C U L A T O R
the best fractions with
denominators from to
in best-fit order: in denominator order:
of
smallest denominator best approximations

R E S U L T S

calculator: Euclid's Algorithm Fractions Expressions Square roots Quadratics Best Approxs. Silver Means Negatives Combined CF in a new window

8.2 Best Fractions for Pi

The following is a list of fractions for pi = π = 3.141592653589793... each of which is better than all of those before it and for each, there is no better fraction using smaller denominators:
3,  13,  16,   19,  22,   179,   201,   223,   245,   267,   289,   311,   333,   355,   52163,   52518
14567576471788592991061131660416717
This list also contains all the convergents to pi from its continued fraction, which I have shown like this.
The numerators of Hendrik's complete list are Sloane's A063674 and the denominators are A063673.
The convergents of Pi's continued fraction have denominators and numerators that are subsets of these sequences: A002486 are the convergent's denominators and A046947 are the convergent's numerators.

By truncating the continued fractions for Pi, we quickly find fractions that are best approximations.
These include some interesting fractions as follows:

3 = 3
The nearest whole number.
[ 3; 7 ] = 22/7 = 3.142857 = pi + 0.00126
This is the value everyone knows from school, 22/7. It is a good approximation for Pi, accurate to one-eighth of one percent.
[ 3; 7, 15 ] = 333/106 = 3.1415094.. = pi − 0.00008..,
[ 3; 7, 15, 1 ] = 355/113 = 3.14159292.. = pi + 0.000000266...
This value is easy to remember - think of the first three odd numbers written down twice: 113355, then split it in the middle to form two three-digit numbers, 113 355, and put the larger number above the smaller!
[ 3; 7, 15, 1, 292 ] = 103993/33102 =3.1415926530.. = pi − 0.00000000057..
This is the next convergent to pi. It corresponds to a term in the CF that is a large number so it gives a particularly good approximation to pi. It is over 400 times more accurate than the previous one (355/113), but this time the numbers involved are not so easy to remember!
[ 3; 7, 15, 1, 292, 1 ] = 104348/33215 = pi + 0.00000000033...
The final element of this CF is 1 so the fraction is fairly close to the previous convergent.
Notice that the convergents are alternately above and below the value of Pi; this is true always for all CF convergents.

Continued fractions can be simplified by cutting them off after a certain number of terms. The result - a terminating continued fraction - will give a true fraction but it will only be an approximation to the full value.
Here, we will use the term exact value for the exact (irrational) value of an infinite continued fraction or the final value of a terminating continued fraction.

It turns out - and we shall not prove this here - that these convergents (fractions) are "the best possible approximations". These approximations are called convergents of the continued fraction.
By "best" here, we mean

8.3 Approximating √2 using Fractions

Earlier we saw that the square-root of 2 is [ 1; 2 ] . So the following sequence of values will give rational approximations to root-2:
Shortened CFFractionValueError
1 = 1 = 1= 1 -0.4142135..
[ 1; 2 ] = 1+1/2 = 3/2= 1.5 +0.0857864..
[ 1; 2,2 ] = 1+1/(2+1/2) = 7/5 = 1.4 -0.0142135..
[ 1; 2,2,2 ] = 1+1/(2+1/(2+1/2))= 17/12 = 1.416666.. +0.0024531..
[ 1; 2,2,2,2 ] = 1+1/(2+1/(2+1/(2+1/2)))= 41/29 = 1.4137931.. -0.0004204..
[ 1; 2,2,2,2,2 ] = 99/70 = 1.4142857.. +0.0000721..
There are some intriguing patterns in the numerators and denominators of the successive fractions in the table above, which I leave you to explore on your own.

9 More on convergents

Here we show two more ways to view convergents:
  1. the first is a very easy method of converting a CF into its convergents that also shows why the convergents of the golden ratio number Phi are the Fibonacci numbers
  2. the second is a geometrical interpretation of convergents.

9.1 An easy way to find the convergents of a CF

We saw earlier that we can convert a finite CF to an ordinary fraction by starting at the right-hand end and working backwards using the fact that
[ a; b, ... , x, y] = [ a; b, ..., x+1/y ]
We then repeat on the shortened CF list again using the last term that is now a fraction.
See earlier for an example. But with this method, each time we take an extra term in a CF to find the next convergent, we have to start the CF to fraction conversion again.

Is there an easier way of calculating the convergent fractions without starting from scratch each time?

Yes there is — and it is a simple variation on the method we used to compute the Fibonacci Numbers!
List the CF in a column, as in the table. Here we use the CF a, b, c, ...
By hand, we can calculate that

The last case above shows the simple method for the CFC term c: So our next convergent for the CF [a; b, c, d] is
(d × (c(ab+1) + a) + ab+1 ) / (d × (cb+1) + b)
We can conveniently represent this process in a table with one column for each term in the CF and each column containing the numerator and denominator of its convergent to that point. We include the virtual starting convergent of 1/0 and the first convergent, for the integer part a is just a/1:
CF term abcd
Numerator1ab×a+1 c×( ba+1 )+ad×(c(ba+1)+a) + (ba+1)...
Denom01b×1+0c×b+1d×(cb+1) + b
There is an example in the next section:

9.2 The Convergents of Phi's CF are Ratios of Fibonacci Numbers!

When we try this for the golden section number Phi = [1; 1 ] we get....
CF:11111...
Num:112358...
Den:011235
... the Fibonacci Numbers themselves as the best approximations to Phi=1.6180339...!

So mathematically we can show that if nature was trying to find the best arrangements of leaves, seeds, etc, using Phi as its "goal", then the best approximations involve the Fibonacci Numbers.

9.3 A geometrical interpretation of convergents

1+root3 convergents
1+√3 convergents
Davenport (see References below) mentions a nice geometric interpretation of convergents due to Felix Klein in 1895.
We interpret each convergent y/x as the point (x,y) on a graph so that the numerator of the convergent is the y-value and the denominators its x-value of the point it represents on a grid.
If we are finding convergents to an irrational value r (one that has no fraction exactly equal to it) or of a finite continued fraction for the value r, each convergent will be closer and closer to the line with gradient r through the origin, that is the line y = r x .

In the diagram here, we take the value (1+√3) = 2.7320508... which has an infinite periodic continued fraction [2; 1, 2, 1, 2, 1, 2, ...] with convergents as follows:

CFndn/derror
2.7320508..-n/d
2212.000000000.7320508076
1313.00000000-0.2679491924
2832.666666670.0653841409
11142.75000000-0.0179491924
230112.727272730.0047780803
141152.73333333-0.0012825258
2112412.731707320.0003434905
1153562.73214286-0.0000920496
24181532.732026140.0000246638
...
So the first row is the convergent with CF [2;] which is just the number 2.
The next row is the conververgent fraction CF [2; 1] which has the value 2 + 1/1= 3
The next row is [2; 1, 2] or 2 + 1/(1 + 1/2) = 8/3
... and so on.
The error of the convergent y/x is a measure of how far (x,y) is vertically above or below the line on the grid. For example, the convergent [2; 1, 2] is the fraction 8/3 at the point (3,8) and the blue line y = (1 + √3) x passes 0.0653841409 vertically above this point.

We can interpret the convergents as best approximations geometrically if we imagine the grid as a board full of pins put at each grid point. We attach a piece of fine string from the origin (0,0) along the "true" (blue) line y = (1+√3) x .
Since 1 + √3 is irrational, then the string will never go through any point (y,x) on the whole grid except (0,0).
If we imagine the string is anchored at some far distant point somewhere and we take hold of it at the origin and pull it up, it will rest against all the green points and only those points that correspond to the convergents which exceed the true value; if we pull the string to the right it will then rest exactly and only on those red points which are the convergents that are below the true value.
This remains true for all continued fractions and their convergents.

10 Other numbers with patterns in their CFs

All proper fractions can be expressed as continued fractions using the jigsaw-puzzle technique at the top of this page where we split rectangles up into squares. Such continued fractions will eventually end since they are the ratio of two finite whole numbers.

In the section above, we have seen that expressions involving square-roots can be expressed as continued fractions with repeating patterns in them. Such continued fractions never end, but the pattern keeps repeating for ever.

Are there other numbers that have patterns in their continued fractions?
Yes! This section begins to explore them and introduces e.

10.1 The Silver Means [ n; n ]

Can we find some more numbers with a pattern in their continued fractions that is like that of the golden mean, Phi? Since Phi as a continued fraction is:
Phi = [ 1; 1, 1, 1, ...] = [ 1; 1 ]
then we can look at the numbers whose continued fractions are
[ 2; 2 ]
[ 3; 3 ]
[ 4; 4 ]
[ 5; 5 ]
...
These numbers have some interesting properties and are called the silver means since the most marvellous properties of all are for that rather special number we call the golden mean or Phi! Let's use T(n) for the n-th number in the list above, so that T(1) is just Phi and T(n) = [n; n]
and T(n) = n+1/(n+1/(n+..)) or
T(n) = n + 1/T(n) since the value inside the brackets is just T(n).
We now have a definition of the Silver Means:
A silver mean is a number T(n) which has the property that it is n more than its reciprocal, i.e. T(n) = n + 1/T(n).

10.1.1 Numerical values of the Silver Means

Using the last property can we find values for the silver means? For instance,
T(1) = 1·6180339 = 1 + 1/1·6180339 = 1 + 0·6180339
T(2) = 2·4142135 = 2 + 1/2·4142135 = 2 + 0·4142135
and so on.
Here is one simple way to find the values and all you need is your calculator or try this one:

10.1.2 Silver Mean Calculator

Silver Means C A L C U L A T O R
x=
T()

R E S U L T S


calculator: Euclid's Algorithm Fractions Expressions Square-roots Quadratic Roots Best Fractions Silver Means Negatives Combined CF in a new window
We return to this Silver Means Calculator later on this page.

10.1.3/ You do the maths... /

You might find the calculator Combined Continued Fraction Calculator useful in this section.

  1. The values of T(n) are easy to find on your calculator using the same method that we used to discover Phi from its property that it is "1 more than its reciprocal".
    The method is, for example, to find T(2) on your calculator:
    1. Enter any positive number you like.
    2. Press the reciprocal button (to find 1 divided by the displayed number).
    3. Add 2 (or, to find T(n), add n) and write down the result.
    4. Repeat from step 2 as often as you like.
    After just a few key presses, the numbers you write down will be identical and this is the value of T(n) as accurately as your calculator will allow.
    For T(2), you will soon reach 2·414213562.
  2. For the value of T(2) here, subtract 1 and square the result. What is the answer?
    What exact value does this suggest for T(2)?
    (You will find the answer in next question!)
  3. Use the method above to find numerical values for T(3) and T(4).
    What value is T(n)?
    T(2) = [2; 2 ] = (2 + √8 )/2 = 1 + √2
    T(3) = [3; 3 ] = (3 + √13 )/2
    T(4) = [4; 4 ] = (4 + √20 )/2 = 2 + √5
    T(n) =
    n + n2 + 4
    2

10.1.4 Exact values of the Silver Means

The You do the maths... suggested to us an exact value for T(2). We could guess values for T(3) and T(4), but they are not easy to spot! So it's mathematics to the rescue!

By multiplying both side of the equation T(n) = n + 1/T(n) by T(n) we get: T(n)2 = n T(n) + 1.

For example, the number [5; 5] we have already met above and we found that it had the property that x2=5x+1.
We can solve this quadratic equation or you can just check that there are two values of x with this property:

x = (5 + √29)/2 and
x = (5 − √29)/2
Since √29 > 5, then the second is a negative value, but since all our continued fractions are positive (they do not contain a negative number!) then the first is the value of our continued fraction:
[5; 5,5,5,5,5, ...] = (5 + √29)/2

If we review what we did above, then you will notice that we found

√2=[1; 2,2,2,2,2, ...]
so we can deduce that [2; 2,2,2,2,2, ...] = 1 + √2

Following the same reasoning and including the golden mean also, gives the following pattern:

[ 1; 1,1,1,1, ... ] = (1 + √5 )/2 = 1.61803398874989... ]
[ 2; 2,2,2,2, ... ] = (2 + √8 )/2 = 1 + √2 = 2.41421356237309... ]
[ 3; 3,3,3,3, ... ] = (3 + √13 )/2 = 3.30277563773199... ]
[ 4; 4,4,4,4, ... ] = (4 + √20 )/2 = 2 + √5 = 4.23606797749978... ]
[ 5; 5,5,5,5, ... ] = (5 + √29 )/2 = 5.19258240356725... ]
[ 6; 6,6,6,6, ... ] = (6 + √40 )/2 = 3 + √10 = 6.16227766016837... ]
[ 7; 7,7,7,7, ... ] = (7 + √53 )/2 = 7.14005494464025... ]
[ 8; 8,8,8,8, ... ] = (8 + √68 )/2 = 4 + √17 = 8.12310562561766... ]
[ 9; 9,9,9,9, ... ] = (9 + √85 )/2 = 9.10977222864644... ]
[ 10;10,10,10,... ] = (10+ √104)/2 = 5 + √26 = 10.09901951359278... ]
...

The following You do the maths... explores this series and discovers some more amazing connections between Phi and the Fibonacci numbers!

10.1.5/ You do the maths... /

You might find the calculator Combined Continued Fraction Calculator useful in this section.

  1. What is the pattern under the square root signs in the table above: that is, what is the nth term in the series 5, 8, 13, 20, 29, 40,... ?
    n2 + 4
  2. What is the next line in the table above for T(11)? [11; 11,11,11,...] = (11 + √125)/2 = 11.09016994374948
  3. T(1) = Phi = ( 1 + √5 )/2
    1. T(4) = 2 + √5 also involves √5. Using the Table of Properties of Phi express T(4) as a power of Phi.
      T(4) = [4; 4,4,4,...] = 2 + √5 = Phi3
    2. T(11) also involves √5. What is T(11)?
      Is it a power of Phi too?
      T(11) = [11; 11,11,11,...] = (11 + 5 √5)/2 = Phi5
    3. What is the pattern here? Which powers of Phi are also silver means and which silver means are they?
      [Hint: the answer involves the Lucas numbers.]
      T( Lucas(2i+1) ) = Phi2i+1
  4. What powers of Phi are missing in the answers to the previous question? What are their continued fractions?
    Phi2i = [ Lucas(2i) − 1 ;  1, Lucas(2i)−2  ]
  5. Express all the powers of Phi in the form (X+Y√5)/2. Find a formula for Phin in terms of the Lucas and Fibonacci numbers.
    Phin = ( Lucas(n) + Fib(n) √5 ) / 2

10.1.6 More Silver Mean Properties

The Table of Properties of Phi shows that all powers of Phi=T(1) are just a whole number plus a multiple of Phi.
Their continued fractions are also shown, with the periodic parts in [ ] brackets.
Phi1=0 + 1 Phi=(√5 + 1)/2 =[ 1 ; 1 ]
Phi2=1 + 1 Phi=(√5 + 3)/2 =[ 2 ; 1 ]
Phi3=1 + 2 Phi=(2√5 + 4)/2 =[ 4 ; 4 ]
Phi4=2 + 3 Phi=(3√5 + 7)/2 =[ 6 ; 1, 5 ]
Phi5=3 + 5 Phi=(5√5 + 11)/2 =[ 11 ; 11 ]
Phi6=5 + 8 Phi=(8√5 + 18)/2 =[ 17 ; 1,16 ]

There are similar patterns for T(2) = 1 + √2 and for T(3) = (3 + √13 )/2 :
T(2)1= 0 + 1 T(2)= 1 + √2 = [ 2; 2 ]   T(3)1= 0 + 1 T(3)= (3 + √13)/2 = [ 3; 3 ]
T(2)2= 1 + 2 T(2)= 3 + 2√2= [ 5; 1,4 ] T(3)2= 1 + 3 T(3)= (11 + 3 √13)/2= [ 10; 1,9 ]
T(2)3= 2 + 5 T(2)= 7 + 5√2= [ 14; 14 ] T(3)3= 3 + 10 T(3)= (36 + 10 √13)/2= [ 36; 36 ]
T(2)4= 5 + 12 T(2)= 17 + 12√2= [ 33; 1,32 ] T(3)4= 10 + 33 T(3)= (119 + 33 √13)/2= [ 118; 1,117 ]
T(2)5= 12 + 29 T(2)= 41 + 29√2= [ 82; 82 ] T(3)5= 33 + 109 T(3)= (393 + 109 √13)/2= [ 393; 393 ]

10.1.7/ You do the maths... /

You might find the calculator Combined Continued Fraction Calculator useful in this section.

  1. From the powers of T(2), what is the pattern in the series 1,2,5,12,29,...?
    How is each number related the the previous two in the series?
    Can you find a formula for the nth term using n? [Hint: Is it similar to the Fibonacci rule?]
    Each is twice the previous term plus the term before that one: 29 = 2×12 + 5
    The nth term is (1 + √2)n − (1 − √2)n
    2 √2
  2. From the table above for the powers of T(3) = (3 + √13)/2 what is the pattern for the new series 1, 3, 10, 33, 109, ... ?
    Can you find a formula for the nth term using n?
    Each is 3 times the previous term plus the term before that one: 33 = 3×10 + 1
    The nth term is ( 1/2(3 + √13) )n − ( 1/2(3 − √13) )n
    √13
  3. T(1) = Phi has the property that T(1) is 1+ 1/T(1).
    Is there a similar property for T(2)?
    [Hint: calculate T(2) and 1/T(2): what do you notice about their decimal parts?]
    What is the relationship between T(3) and 1/T(3)?
    What is the general pattern here for T(n)?
    T(2) = 2 + 1
    T(2)

    T(3) = 3 + 1
    T(3)

    ...
    T(n) = n + 1
    T(n)

  4. Above we found T(4) is also Phi3, that is T(1)3 = T(4).
    T(2)3 is also a silver mean too -- which one? What about T(3)3?
    Find the general pattern.
    T(2)3 = T(14) = 7 + 5√2
    T(3)3 = T(36) = 18 + 5√3
    ...
    T(n)3 = T( n3 + 3n )
    The series n3 + 3n is 4, 14, 36, 76, 140, 234, 364, 536, ... A079908
  5. The same as the previous question but this time find a silver mean equal to T(1)5 and one for T(2)5 and so on for the other 5-th powers of silver means.
    Hard: What is the general pattern?
    T(1)5 = T(11) = (11 + 5√5 )/2
    T(2)5 = T(82) = 41 + 29 √2
    ...
    T(n)5 = T( n5 + 5n3 + 5n )
    The series n5 + 5n3 + 5n is 11, 82, 393, 1364, 3775, 8886, ...
  6. Hard: There is a pattern here for all the odd powers of the silver means.
    What is it?
    Spoiler: Here is part of the answer!

10.1.8 Silver Means T(n) for real-valued n

Starting from T(n) = [ n; n ] we found the formula T(n) = n + 1/T(n) which we can solve to find
T(n) = n + n2 + 4
2
. This extends not just to positive and negative integers, but to real numbers too, such as
T(2.5) = T(5/2) = 5/2 + (5/2)2 + 4
2
=
5 + √41 = 2.850781059358... = [2.5; 2.5 ] = [ 5/2; 5/2 ]
4
The Silver Means Calculator above will also work on real numbers such as 2.5 and rational numbers for example 5/2 and compute the exact values of T(n) for these values too. For instance if we use it to compute T(7/2) we will see the result with integers
T()
R E S U L T S
T(7/2) = (7+√65)/4 = 3.7655644370746373
but the equivalent T(3.5) will give the result with decimal values:
T()
R E S U L T S
T(3.5) = 1.75+√4.0625 = 3.7655644370746373

10.2 Fibonacci-related and Phi-related Continued Fractions

10.2.1 General Fibonacci Ratios [1; 1,1,1,...,1,a ]

Here is a table of fractions corresponding to the continued fractions [1;a] for a few values of a:
a12345...
[1;a]23/24/35/46/5...
Using the definition of continued fractions in list form, it is easy to see that
[1;a] = 1 + 1/a = (a+1)/a      (equation 1)

Let's extend the pattern to [1;1,a]:

a12345...
[1;1,a] 3/25/37/49/511/6...
Algebra again helps here:
[1;1,a]= 1 + 1/(1 + 1/a) = 1 + 1/(a+1)/a = 1 + a/(a+1) =(2a+1)/a+1      (equation 2)
In fact, the fraction here has: The same thing happens with CFs of the form [1;1,1,a] :
a12345...
[1;1,1,a] 5/38/511/714/917/11...
So
[1;1,1,a] = 1 + 1/(1 + 1/(1 + 1/a)) = 1 + 1/ (2a+1)/(a+1) = 1 + (a+1)/ (2a+1) = (3a+2)/(2a+1)       (equation 3)
Again we see that these fractions have: We can continue this and arrive at the general pattern:
[ 1; 1, 1, ..., 1, a ] =
F(m+1) a + F(m)
F(m) a + F(m−1)
    for m 1s in the list
When we looked at the General Fibonacci Series G(a,b,n) we found a formula for the general term. A General Fibonacci Series uses the Fibonacci Rule of adding the latest two values to get the next, but starting with the pair a,b:
G is a, b, a+b, a+2b, 2a+3b, ...
G(a,b,n) = F(n-1) a + F(n) b
We can reform the formula for [1; 1, 1, ..., 1, a] as the ratio of two terms in the same General Fibonacci series:
[ 1; 1, 1, ..., 1, a ]  = 
F(m+1) a + F(m)
F(m) a + F(m−1)
 = 
G(1,a,m+1)
G(1,a,m)
    for m 1s in the list
Article: The formula above is Lemma 1 of Fifth Roots of Fibonacci Fractions C P French, Fib Quarterly 44 (2006) pages 209-215

The paper above by C P French goes on to find and prove some even more interesting formulae:

[ 1; 1, 1, ..., 1, 2, a ]  = 
F(m+3) a + F(m+1)
F(m+2) a + F(m)
    for m 1s in the list
regarding roots of Fibonacci ratios:
    n+2 1s
5
F(n+5)
F(n)
 = { [ 1; 1, .... 1, 1, 1, F(2n + 5) + 2, ... ] if n is odd
[ 1; 1, .... 1, 2, F(2n + 5) − 4, ... ] if n is even
    n 1s
and, more generally,
The CF for k
F(n+k)
F(n)
 begins with at least k 1's
He mentions that there are more patterns if we replace both 5s on the left hand side above by either 13 or else 34 or 89 or 233 ... that is by alternate Fibonacci numbers!

10.3 The Noble Numbers [ 0; a1, a2, ..., an, 1 ]

When we look at decimal fractions, they fall into two types: those that terminate such as 3/8 = 0.375 and those that end with an infinite series of the same digits, the periodic fractions such as 1/3 = 0.333 and 679/5500 = 0.123 45 45 45 45 ... = 0.12345.
We can begin to analyse continued fractions in the same way, except their structure is much richer.
Earlier we looked at the square roots of whole numbers and found that their fractional parts are purely periodic CFs. A special class of CFs are those that are less than 1 and end with the period [1], called the Noble Numbers
[0; a1, a2, ..., an, 1 ]
Here are some examples and their related initial parts as CFs:
FractionCFconvergentsNoble number CF
2/3 =[ 0; 1, 2 ]1/1, 2/3 ( phi + 2 )/( phi + 3 ) = (5 + √5)/10 =[ 0; 1, 2, 1 ]
4/7 =[ 0; 1, 1, 3 ]1/2, 4/7 ( phi + 4 )/( 2 phi + 7) = (37 - √5)/62 =[ 0; 1, 1, 3, 1 ]
The general pattern is
if the fraction P/Q < 1 has the (finite) CF [0; a1, a2, ..., an] where an > 1 and
if its final two convergents are p/q, P/Q then
the noble number [ 0; a1, a2, ..., an, 1 ] = p + P Phi = p phi + P = 2 p + P + √5 P
q + Q Phiq phi + Q2 q + Q + √5 Q

where
Phi = √5 + 1 = [ 1; 1 ] and phi = √5 − 1 = [ 0; 1 ]are the golden ratio numbers.
22
For more about these numbers and applications, see M Schroeder's book in the References below.

10.4 The Near-Noble Numbers [0; 1, 1, 1, ..., a ]

If we now make the pattern [ 1; 1, 1, ..., a] the period of a continued fraction for a value less than 1, i.e. [0; 1,1,1,...,a ], then we have the Near Noble Numbers.

Using the calculator Continued Fraction Calculator we can verify that, for example, if a = 2 after n 1's:

Period
length
CFValue
2 [ 0; 1,2 ]√3 − 1
3 [ 0; 1,1,2 ]√(5/2) − 1
4 [ 0; 1,1,1,2 ]√(8/3) − 1
5 [ 0; 1,1,1,1,2 ]√(13/5) − 1
6 [ 0; 1,1,1,1,1,2 ]√(21/8) − 1
It is not difficult to spot the pattern here:
[ 0; 1, 1, 1, ..., 1, 2] = 
F(n+2)
F(n)
  − 1
With a = 3 we have the following:
Period
length
CFValue
2 [ 0; 1,3 ] ( √21 − 3 ) / 2
3 [ 0; 1,1,3 ] ( √68 − 6 ) / 4 = (√17 − 3) / 2
4 [ 0; 1,1,1,3 ] ( √165 − 9 ) / 6
5 [ 0; 1,1,1,1,3 ] ( √445 − 15 ) / 10
6 [ 0; 1,1,1,1,1,3 ] ( √1152 − 24 ) / 16 = ( √2 − 1 ) 3/2
The pattern here does not jump out at us. A little probing, consulting a table of Fibonacci numbers reveals the pattern:
Period
length
CFValue
n [ 0; 1, 1, 1, ..., 1, 3 ]
F(n+6)
4 F(n)
3
2
Manfred Schroeder gives the general formula in Fractals, Chaos and Power Laws ( see references) as:
For a period of length n: [0; 1, 1, 1, ..., 1, a] = 
a
2
(
1 + 4 a F(n-1) + F(n-2)
a2 F(n)
− 1 )

11 Expressions involving e

The number e is the base of natural logarithms and occurs in many places in mathematics. It is also the number that this series settles down to eventually:
(1 + 1/2)2 = 2·25
(1 + 1/3)3 = 2·370370..
(1 + 1/4)4 = 2·441406..
(1 + 1/5)5 = 2·488320..
(1 + 1/6)6 = 2·521626..
...

e = Limit
n → ∞
(1 +   1/n)n = 2·718281828459045...

e = 1 + 1 + 1 + 1 + ... where n! = 1×2×3× … ×n
1!2!3!
Its value to 200 dps is
71828 18284 59045 23536 02874 71352 66249 77572 47093 69995
95749 66967 62772 40766 30353 54759 45713 82178 52516 64274
27466 39193 20030 59921 81741 35966 29043 57290 03342 95260
59563 07381 32328 62794 34907 63233 82988 07531 95251 01901 ...
e is irrational - it is not a fraction - so its decimal expression (and indeed in any other base apart from 10) never ends up as a recurring pattern.
We can write this in the list notation as
e = [ 2; 1,2,1, 1,4,1, 1,6,1, 1,8,1, 1,10,1, ..., 1,2n,1, ... ]

In October 2009 Hendrik Jager of the Netherlands wrote to me about a result that he had proved:

Sometime ago I discovered an amusing continued fraction in which e plays a role:
Start with [5; 2 ,
and follow it with the numbers 3,2n,3,1,2n,1 with n=1,
after that the same numbers with n=2,
then these numbers with n=3, and so on.
So one gets [5; 2, 3,2,3,1,2,1, 3,4,3,1,4,1, 3,6,3,1,6,1, 3,8,3,1,8,1, ... ].
This is the continued fraction of 2 e.
What other CFs can you find for e or its powers and multiples?

11.1 Powers and Roots of e

Euler also found the following:
√e = [1; 1,1,1, 5,1,1, 9,1,1, 13,1,1, 17,1,1, ...]

√e to 200 dps is:

64872 12707 00128 14684 86507 87814 16357 16537 76100 71014
80115 75079 31164 06610 21194 21560 86327 76520 05636 66430
02866 63775 63077 97004 67116 69752 19609 15984 09714 52490
05979 69294 22659 09840 39147 19948 46465 94892 44896 86890 ...

By playing with a computer algebra package (because they do computations to large numbers of decimal places), you can discover more continued fraction patterns involving e:

e1/2 = √e = [1; 1,1,1, 5,1,1, 9,1,1, 13,1,1, ...] = 1.648721270700128146848651
e1/3 = 3√e = [1; 2,1,1, 8,1,1, 14,1,1, 20,1,1, ... ] = 1.395612425086089528628125
e1/4 = 4√e = [1; 3,1,1, 11,1,1, 19,1,1, 27,1,1, ...] = 1.284025416687741484073421
e1/5 = 5√e = [1; 4,1,1, 14,1,1, 24,1,1, 34,1,1, ... ] = 1.221402758160169833921072
e1/n = n√e = [1; n-1,1,1,  3n-1,1,1,  5n-1,1,1,  7n-1,1,1, ...]
e2 also has a pattern in its continued fraction a property not shared with any other natural number power of e:
e 2 = [7; 2, 1,1,3,18,5, 1,1,6,30,8, 1,1,9,42,11, ...] = 7.389056098930650227230427
The CF for e2 is included in the pattern in the next table with n=0:
Note that
We can take odd-numbered roots (cube-roots, fifth-roots, seventh-roots, etc) of e2 and discover another simple pattern:
e2/3 = [1; 1,18,7, 1,1,10,54,16, 1,1,19,90,25,1,1,28,126,34, ...] = 1.947734041054675856639021
e2/5 = [1; 2,30,12, 1,1,17,90,27, 1,1,32,150,42, 1,1,47,20,57, ... ] = 1.491824697641270317824853
e2/7 = [1; 3,42,17,1,1,24,126,38, 1,1,45,210,59, 1,1,66,294,80, ... ] = 1.3307121974473499773031851
e2/(2n+1) = [1; n,12n+6,
 5n+2,
1,1,7n+3,
 36n+18,11n+5,
1,1,13n+6,
 60n+30,17n+8,
1,1,19n+9,
 84n+42, 23n+11, ...]
18 July 2013: With thanks to Glenn Leider for some corrections here.

Professor Gleb Beliakov of the School of Information Technology at Deakin University in Australia emailed me (May 2020) with the following general CF formula for p times e to a power of the form 1/M where M is a multiple of p:

p e1/pq = [ p,    q-1,1,2p-1,    3q-1,1,2p-1,    5q-1,1,2p-1, ...]
The CF terms are in sets of 3 but only the first of the three changes each time. Some simpler examples are:
pqe form and CF
32 3 e1/6 = [3, 1, 1, 5, 5, 1, 5, 9, 1, 5, 13, 1, 5, 17, 1, 5, 21, 1, 5, 25, 1, 5, 29, 1, 5, 33, ... ]
25 2 e1/10 = [2, 4, 1, 3, 14, 1, 3, 24, 1, 3, 34, 1, 3, 44, 1, 3, 54, 1, 3, 64, 1, 3, 74, 1, 3, 84, ...]

11.2 Simple series CFs are expressions in e

Two other expressions with e that have patterns in their continued fractions are
e − 1 = [ 0; 2, 6, 10, 14, ... ]
e + 1
which has the value 0.462117157.. and is a special case (k=2) of the following:
e2/k − 1 = [ 0; k, 3k, 5k, 7k, 9k, ... ]
e2/k + 1
The above is also called the hyperbolic function tanh(1/k).

If we let k=1, we have another special case:

e2 − 1 = [ 0; 1, 3, 5, 7, 9, 11, ... ]
e2 + 1
which is tanh(1) = sinh(1) / cosh(1) = 0.761594..
Substituting 2k for k in the general case doubles all the continued fraction entries ...
e1/k − 1 = [ 0; 2k, 6k, 10k, 14k, 18k, ... ]
e1/k + 1
and Euler gave the following variation too:
2 = [ 1; 6, 10, 14, 18, 22, 26, ... ]
e − 1
We can also substitute 4k for k and quadruple the numbers ...
e1/(2k) − 1 = [ 0; 4k, 12k, 20k, 28k, 36k, ... ]
e1/(2k) + 1>
Suppose we look at some simple patterns in a continued fraction, such as [1;2,3,4,5,...] and [2;4,6,8,10,...] . Do these have a simple mathematical expression too?
[2; 4, 6, 8, 10, 12, ... ] = 2.24019 37238 70089 74110 52206 41729 82977 20272 46867 29039 ..
[1; 2, 3, 4, 5, 6, 7, ...] = 1.43312 74267 22311 75831 71834 55775 99182 04315 12767 9060 ...
I do not know of a simple expression for the above two continued fractions, but here are two for which we do know exact values:
[1; 3, 5, 7, 9, 11, 13, ...] = 1.31303 52854 99331 30363 61612 46930 84783 29120 13941 24045 ... =   e2 + 1
e2 − 1

We have already looked at this one above, but here we note that, using hyperbolic trig. functions, it is also cosh(1)/sinh(1) = 1/tanh(1) = coth(1) .
[3; 6, 9, 15, 21, 27, ... ] = 3.16365 81744 60733 57425 12504 13949 ... = 13 e2/3 − 7
4 e2/3 − 2

In general, if a continued fraction is an arithmetic progression (the difference between any two consecutive numbers is always the same; let's call it d and suppose the series starts with a), then the number itself is :
[a; a+d, a+2d, a+3d, a+4d, ... ] =
BesselI( a − 1, 2)
dd
BesselI(a,  2)
dd

which involves the Bessel I function. More about this function is far outside the scope of this introductory page!

For more on Continued Fractions, see M Beeler, R W Gosper and R Schroeppel's HAKMEM. MIT AI Memo 239 of 1972.

11.3 Pi

Compare the above continued fractions involving e with the continued fraction for Pi and for √Pi which begin :
Pi = [3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, 1, 84, 2, 1, 1, 15, 3, 13, 1, 4, 2, 6, 6, 99, 1, 2, 2, 6, 3, 5, 1, 1, 6, 8, 1, 7, 1, 2, 3, 7, 1, 2, 1, 1, 12, 1, 1, 1, 3, 1, 1, 8, 1, 1, 2, 1, 6, 1, 1, 5, 2, 2, 3, 1, 2, 4, 4, 16, 1, 161, 45, 1, 22, 1, 2, 2, 1, 4, 1, 2, ... ]
√Pi =  [1; 1, 3, 2, 1, 1, 6, 1, 28, 13, 1, 1, 2, 18, 1, 1, 1, 83, 1, 4, 1, 2, 4, 1, 288, 1, 90, 1, 12, 1, 1, 7, 1, 3, 1, 6, 1, 2, 71, 9, 3, 1, 5, 36, 1, 2, 2, 1, 1, 1, 2, 5, 9, 8, 1, 7, 1, 2, 2, 1, 63, 1, 4, 3, 1, 6, 1, 1, 1, 5, 1, 9, 2, 5, 4, 1, 2, 1, 1, 2, 20, 1, 1, 2, 1, 10, 5, 2, 1, 100, 11, 1, 9, 1, 2, 1, 1, 1, 1, 3, ... ]

These series are not known to have any pattern in them in contrast to those of e and √e above. Why? At present no one knows!

11.4 CFs connecting π, Φ and e

The remarkable mathematician Ramanujan proved two connections between π, e and Φ =1/φ=(√5+1)/2 that involve continued fractions:
( 2 + ΦΦ ) e2π/5 = 1 + e−2π
1 + e−4π
1 + e−6π
1 + ...

( 2 − φφ ) eπ/5 = 1 − eπ
1 + e−2π
1 − e−3π
1 + ...

12 Continued Fractions and the Fibonacci Numbers

In this section we will take a closer look at the links between continued fractions and the Fibonacci Numbers.

12.1 Squared Fibonacci Number Ratios

What is the period of the continued fractions of the following numbers?
  1. 25/9
  2. 64/25
  3. 169/64
You might have noticed that in all the fractions, both the numerator (top) and denominator (bottom) are square numbers (in the sequence 1, 4, 9, 16, 25, 36 ,49, 64,... ). The numbers that are squared are Fibonacci numbers (starting with 0 and 1 we add the latest two numbers to get the next, giving the series 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... ).
The fractions above are the squares of the ratio of successive Fibonacci numbers:
  1. 25/9 = (5/3)2 = (Fib(5)/Fib(4))2
  2. 64/25 = (8/5)2 = (Fib(6)/Fib(5))2
  3. 169/64 = (13/8)2 = (Fib(7)/Fib(6))2
  4. ...
There is a simple pattern in the continued fractions of all the fractions in this series.

What other continued fraction patterns in fractions formed from Fibonacci numbers (and the Lucas Numbers 2, 1, 3, 4, 7, 11, 18, 29, 47, ... ) can you find?

Brother Alfred Brousseau (1907-1988) was a founder member of the The Fibonacci Association and also of a large collection of photos of Californian plants. (with thanks to Bob Sills for this information).
He wrote many very readable and introductory articles on the Fibonacci numbers in plants in the early volumes of the Fibonacci Quarterly, which are now available free and online.

12.2 A link between The Golden string, Continued Fractions and The Fibonacci Series

Suppose we make the golden sequence into a binary number (base 2) so that its columns are interpreted not as (fractional) powers of 10, but as powers of 2:
0·1011010110 1101011010 1101101011 ...
= 1x2−1 + 0x2−2 + 1x2−3 + 1x2−4 + 0x2−5 + 1x2−6 + ...
It is called the Rabbit Constant.
Expressed as a normal decimal fraction, it is
0·70980 34428 61291 3... .
Its value has been computed to many decimal places where our Phi is referred to as tau.

The surprise in store is what happens if we express this number as a continued fraction. It is

[0; 1, 2, 2, 4, 8, 32, 256,...]
These look like powers of 2 and indeed all of the numbers in this continued fraction are powers of two. So which powers are they? Here is the continued fraction with the powers written in:
[0; 20, 21, 21, 22, 23, 25, 28, .. ]
Surprise! The powers of two are the Fibonacci numbers!!!
[ 0; 2F(0), 2F(1), 2F(2), ... , 2F(i), ...]

Perhaps even more remarkably, a discussion on sci.math newsgroup of Oct 1997 proves a result that Robert Sawyer posted:- that we can replace the base 2 by any real number bigger than 1 and the result is still true!

12.3 Two Continued Fractions involving the Fibonacci and the Lucas Numbers

The continued fraction for √5 φ = 1.3819660112501051518... =
5 − √5
2
is [1; 2, 1 ] and its convergents are:
1,  3 4 7 11 18 29, ...
2 3 5 8 13 21

The pattern continues with the Lucas Numbers on the top and the Fibonacci Numbers on the bottom of the convergent's fractions.

Taking the reciprocal of this value, i.e.

1 Φ  =  2 5 + √5  = 0.72360 67977 49978 96964... = [ 0; 1, 2, 1 ]
√5 φ √5 5 − √5 10
we get the Fibonacci numbers on the top and the Lucas numbers on the bottom of the convergents:
1 2 3 5 8 13 21, ...
3 4 7 11 18 29


13 Applications

13.1 An Application to the Solar System

cogs A cog wheel has a whole number of teeth round its rim that connect with (mesh with) the teeth on another cog. The ratio of the two numbers of teeth governs the speed ratio between the two cogs. Thus a cog with 10 teeth meshing with one with 50 means the 10-tooth cog will rotate 5 times quicker than the 50-toothed cog (but in the opposite direction). So a cog can only revolve at a fixed fraction of the rate of any other to which it is connected, and so on for a train of cogs (a gear train).
Most vehicles, from bicycles to cars and trains, use cogs like this in a gearbox to "change gear", that is, to keep the engine (or pedals) rotating in a narrow range of speeds but allowing the wheels to go at increasingly faster or slower speeds.

An application of continued fraction convergents is if we wish to make two cog wheels where one rotates √2 times faster than the other, for example. Since √2 is irrational, there is no cog mechanism that will give this exactly so we have to approximate using fractions.

The convergent's for √2 that we found above are:

3 7 17 41 99 
25122970
We could have 7 teeth on one cog and 5 on another, but it is difficult to get efficient meshing with so few teeth so we would use perhaps 70 and 50. 17 and 12 teeth would give a closer approximation. If we allow ourselves up to 100 teeth on a cog, then the best approximation to √2 is given by 99 teeth and 70, which gives an error of only 0.007%.

Such fractions would be useful to know if you were building a clockwork model of the Solar System (an orrery) where we wanted the planets to rotate accurately in relation to one another. For example we would want the earth to spin around its own axis exactly 365.242199 times ("days") in the time it takes it to turn exactly once around the sun (a "year"), for example. Similarly the moon must take 29.53059 "days" to rotate exactly once around the earth. Such an accurate (mechanical) model is called an orrery. Christian Huygens (1629 - 1695) used continued fractions when constructing his orrery. You can still buy an orrery today -- they are beautiful pieces of scientific equipment!

13.2 An Application to Trig. functions

We know that sin(0) = cos(90°) = 0 and sin(90°) = cos(0) = 1.
There are a few other angles which have exact expressions (involving square-roots) that we generally use:
sin(30°) = cos(60°) = 1/2
sin(45°) = cos(45°) = 1/√2
sin(60°) = cos(30°) = √3/2

But are there any more? You can try using the trig. formulas for half-angle and double-angles. Alternatively, we could try investigating their numerical values and seeing if we can spot any repeating part in their continued fractions. Since all and only those mathematical expressions which involve square-roots have a periodic continued fraction, we can spot those when they occur as trig values. We need first a calculator that can give lots of decimal places because the continued fraction of (a+√b)/c where a,b and c are whole numbers can involve a period of up to 2√b elements. Here is an attempt to list all the trig values with simple exact expressions. Can you add any more?

14 Other kinds of simple CF

Later we will examine CFs with numerators that are not 1 but this section explores what happens if we have more general integers in the denominators of our simple CFs and why positive integers are so much better.

All of our (simple) CFs have involved positive integers.

What if we allowed negative numbers in the denominators of our CFs? Why not allow subtraction as well as addition in a CF?
In his "Additions" or as we would put it today, Appendices, to his translation of Euler's Elements of Algebra LaGrange gives a nice answer to these questions. He shows that all negative numbers and subtractions in a (simple) CF can be removed to find an equivalent CF with positive values only. Here is how he did it.

14.1 Negative numbers and their CFs

There are several ways of finding a CF for a negative value.

14.1.1 A negative integer part

If we allow the integer part of the CF to be negative, then we can use a little algebra as follows to change any negative number into a positive fractional CF (less than 1) but with a negative integer part:
Let r = W + F
where W is the whole number part and
F is the fractional part so that 0 < F < 1.
−r = −W − F
−r = −W −1 + (1 − F)
The whole number part of −r is −W −1 and since 0 < F < 1 then 0 < 1−F < 1 is the fractional part and positive so it has a simple CF.
The only negative number in the new CF is the first, the integer part.
For example
1 + 5/12 = 17/12 = [1; 2, 2, 2] therefore
−17/12 = −1−5/12 = −2 + 7/12 .
But 7/12 = [0; 1, 1, 2, 2] so we have
−17/12 = [ −2; 1, 1, 2, 2]

14.1.2 Short Negation

A little more algebra will show that
( a + 1) = −a −1 = −a − 1 +1
b + 1b + 11 + 1
CCb − 1 +1
C
This method of negating a positive CF introduces an extra term (1) before changing the first fractional-part term. C in the above may be a single number, a list (the rest of the CF) or empty. We will call this ...
The Short negation Rule
if r = [a; b, c, d, ...] then −r = [−a−1; 1, b−1, c, d, ...]
For our example above, r = 17/12 = [1; 2, 2, 2], a=1; b=2 so −17/12 = [−2; 1, 2−1 , 2, 2] = [−2; 1, 1, 2, 2].

14.1.3 Negate everything

A simpler way to find a CF for a negative number is to take the CF of the positive value and then negate all its terms:
−[a; b, c, ...] = [−a; −b, −c, −...]
The alternative on the right moves the minus signs into the rest of the terms.
This brings us to CFs with negative numbers in them. We shall see that we can always find an equivalent form where all terms in the CF are positive, so all we need is the (simple) CFs we introduced at the start of this page.

14.1.4 Removing zeroes

The only problem is when b = 1 because that gives a 0 in our negated CF! A little algebra can come to the rescue and shows that a 0 anywhere after the first place in a CF can be removed using this collapse a zero formula:
If 0 is not the last item: note that C here may be a list of numbers, one number or empty:
a + 1
0 + 1
b +1
C
= (a + b) +1
C
If 0 is the last item:
a + 1 = a + 1 = a + 1 = a + 0 = a
b + 1b + ∞
0
Remove 0 Rule
[..., a, 0, b, C] = [ ..., a + b, C]
[..., a, 0, b] = [ ..., a + b]
[..., a, b, 0] = [ ..., a]
So when we try our method on 2 + 5/8 = 21/8 = [2; 1, 1, 1, 2] where a=2; b=1 then we get −21/8 = [−2−1; 1, 0, 1, 1, 2]
Applyng the collapse a 0 formula this becomes [−3; 1+1, 1, 2] = −3 + [0; 2, 1, 2] = −3 + 5/8

So we can now find a CF for a negative value by changing all terms of CF of the positive value to be negative or else we can use the latter method and have a the integer part the only negative term and all the rest positive.

Now we look at other negative terms in a CF and show how to remove them too.

14.2 Subtraction and Negative values in a CF

14.2.1 How to change Subtraction into addition

LaGrange points out that it is a simple matter of algebra to show that we can remove subtractions in favour of addtions.
Wherever there is a subtraction, "push" it into the rest of the CF making positive numbers into negatives. We use C to be the rest of a CF which may be empty or one or more terms:
a − 1 = a + 1
b + C−b − C
and repeat after negating all the terms in C if necessary.
Now all we have is additions but we may have negative numbers in our (simple) CF.

14.2.2 Removing negative numbers from a CF

If a term in a CF is negative we use the remove a negative formula:
[..., a, −b, C] : a +1= (a − 1) + 1
−b + 11 + 1
C(b − 1) − 1
C


We can remove a final negative too:
a − 1 = a + 1 = (a − 1) + 1
b−b1 + 1
b − 1
Negative to positive:
[..., a, −b, C] = [ ..., a − 1, 1, b − 1, −C]
C may be a single number or the rest of the CF (a list), or empty:
[ ... , a, −b] = [..., a−1, 1, b−1]

We have seen how to remove any 0's that might arise in a section above.

In terms of CFs this becomes [..., a, −b, C ] = [..., a−1, 1, b−1, −C] where C is (the value of) the rest of the CF. Also to negate a CF is to negate all of its terms.
We can therefore "push" the negative signs to the right in the CF, leaving positive values to the left.
To negate a CF is to negate all of its terms and results in its total value being negated too.

For example, [2; −2] = 2 + 1/−2 = 2 − 1/2 = 3/2 = [1;2]
Using Lagrange's formula above we have

[2; -2] = [2−1 ; 1, 1] = [1; 1,1] = [1; 2]
Here is a longer example for a CF for −24/13 = −30/13:
−30/13 = [ −3; 1, 2, 4]
Remove the negative number
[− 3; 1, 2, 4 ] → −[2;1, 0, 2, 4]
collapse the 0
−2;1, [0, 2, 4] → −[2; 3, 4 ]
−[2; 3, 4] all terms are now positive.

We can also try negating all the terms and simplifying again:
−30/13 = [ −3; 1, 2, 4] = [3; −1, −2, − 4]
Remove the −1
−[3; −1, −2, − 4] → −[2; 1, 0, 2, 4]
Collapse the 0:
−[2; 1, 0, 2, 4] → −[2; 3, 4]
−[2; 3, 4] all terms are now positive.

In this way we can successively eliminate any negative number in a CF, provided the first number, the integer part, is positive.

However... we now have CFs such as [1;-1] which is 0.
Another example is [1;1,1,-1,3], but we have more problems since [0; 1,-1] is 1/0 or Infinity ()!
We avoid these problem cases if we only use positive terms in our CFs or if we disallow a 0 in a CF except as the initial (integer part) term.

14.3 Remove all 1s

The Negative to Positive rule shows that we can remove a 1 in a CF by increasing the size of the values on either side and negating all terms further to the right. Any later 1s will be changed to −1s.
But if we apply it to the right-most 1, it will not introduce any −1s.
But if we start from the right-hand end and work to the left, we can remove all 1s and not introduce any −1s. Thus we can remove all 1's positive or negative if first we change all negatives into positive and then start from the right-hand end and change any 1s, though this again may introduce more negative terms but all will have a size bigger than 1.

You can explore this in the following Calculator for CFs with negative terms.

14.4 CF with negatives Calculator

Zeroes and negative numbers are allowed as input terms in the CF in this Calculator.
It can also remove all 1s turning them into negative numbers.
Also, it is possible to remove all 1s and -1s so all terms are <-1 or >1.
If you want to see each of the steps in these conversions, click to change the "Show step-by-step" box to .

The You do the maths... section after the Calculator will show that there are many ways to write a CF if it contains a negative number.
CF with Negatives C A L C U L A T O R



Show step-by-step:
from Continued Fraction: [ ]

R E S U L T S



calculator: Euclid's Algorithm Fractions Expressions Square roots Quadratics Best Approxs. Silver Means Negatives Combined CF in a new window

14.4.1/ You do the maths... /

  1. How many CFs containing some negative terms can you find for 0? For example [1; -1]?
    0 = [1; -1] = [1; -1,   1, -1, 1] = [1; -1,   1, -1, 1,   -1, 1, -1] = ...
    0 = [0; 1, -1, 1] = [0; 1, -1, 1, -1, 1,-1] = [0; 1, -1, 1, -1, 1, -1, 1, -1, 1] = ...
    and the negatives of the above:
    [-1; 1] = [-1; 1, -1, 1, -1] = [-1; 1, -1, 1, -1, 1, -1 , 1]
    [0; -1, 1, -1] = [0; -1, 1, -1, 1, -1, 1] = [0; -1, 1, -1, 1, -1, 1, -1, 1, -1] = ...
    Also see Question 4 below.
  2. What are the values of
    1. [1; 2, -1]
    2. [1; 2, -1, 2]
    3. [1; 2, -1, 2, -1]
    4. [1; 2, -1, 2, -1, 2]
    Find a general expression for your results.
    The values cycle through 1, 3/2, 2, Infinity
  3. Repeat the above on the first 2, 3, 4, ... items in these CFs
    1. [ 0; -2, 2, -2, 2, -2, 2, -2, 2 ]
    2. [1; 2, -2, 2, -2, 2, -2, 2, ...]
    3. [1; 1, -3, 1, -3, 1 -3, 1, ...]
    [ 0; -2, 2, -2, 2, -2, 2, -2, 2 ]:
    0 / 1 = 0
    -1 / 2 = -0.5
    -2 / 3 = -0.6666666666666666
    -3 / 4 = -0.75
    -4 / 5 = -0.8
    -5 / 6 = -0.8333333333333334
    -6 / 7 = -0.8571428571428571
    -7 / 8 = -0.875

    [1; 2, -2, 2, -2, 2, -2, 2, ...] = [1; 1, L−1] = (2L-1)/L where L is the length of the CF.
    [1; 1, -3, 1, -3, 1 -3, 1, ...] the values cycle through 1, 2, 5/2, 3, 4, Infinity

  4. Have you included any relevant answers to the previous question in your answer to the first question?
    0 = [0;1,1,-3,1,-3,1] = [0;1,1,-3,1,-3,1, -3,1,-3,1,-3,1] = ...
    0 = [0; 1,-3,1,-3,1,-3] = [0; 1,-3,1,-3,1,-3, 1,-3,1,-3,1,-3] ...

    0 = [-1; 1, -2, 1, -2, 1] = [0; 1, 1, -2, 1, -2, 1, -2, 1] = ...

14.5 The disadvantages of negative terms in a CF

The You do the maths... above reveals major problems with CFs that contain negative terms:
Arbitrary lengths of a CF may reduce to 0
We found many (infinitely many!) ways of making 0 but these sequences may occur anywhere in a CF and reduce to a 0 term! As we saw above this collapses the terms before and after the zero part into one term, or just obliterates the term before if the CF ends with a 0 sequence.
We do not know if a term is needed because what follows might obliterate it.
This makes it very hard to simplify CFs with negatives and zeroes in them because arbitrarily long strings of these non-positive terms can "collapse to 0". Also, in the simple CFs we can use a term to find a convergent knowing that it is a better approximation than any previous convergent but if we are not even sure that a particular term exists -- the 0 part might be the final part of the CF and so this term is irrelevant - then we cannot even be sure we need it to make a "convergent".
There are infinitely many CFs for any value if we allow negative terms
For simple CFs, with all terms positive, any positive number has a unique CF. But because of the many forms of 0 of any length at any part of a CF, each value has an infinite number of CFs which use negative terms - but only one if all the terms are positive.
"Convergents" may be infinite
For a CF which is 0, we take its reciprocal by introducing a 0 in the integer part:
[1;−1] = 0 so [0; 1, −1] = 1/0 = ∞
[1;-2,1,-2,1,-2] = 1/2 but its "convergents" are 1, 1/2, 0, ∞, 1, 1/2
Since they do not always converge to the actual value (get closer and closer to it), they should not really be called "convergents" but we will play a little loose with the language and use that word for the values of successive truncations of a CF.
"Convergents" do not always alternate between being larger and smaller
[2;1,1,1,1,1,1,1,2] = 144/55 = [3;-3,3,-3,3] but all the convergents of the simple CF [2;1,1,1,1,1,1,1,2] except the last are alternately above and below 144/55 = 2.618181818181818
The "convergents" of [3;-3,3,-3,3] successively decrease down to the final exact fraction 144/55 whereas those of [3;3,-3,3,-3] successively increase to the final exact value of 186/55.
"Convergents" may not converge!
From the You do the maths... we saw that first few "convergents" of [0; 2, -2 ] have a pattern, which continues indefinitely. There is no value to which this CF converges. Though the word is not always appropriate nor correct in some cases, though it is in others, but we will continue to call the successive fractions formed by truncating the CF at successive terms its "convergents".
A more precise word may be its truncations though some mathematicians use the word approximants.
There are other ways to represent negative values without negative terms
We can represent a negative value using simple CFs in two ways without needing negative terms in the fractional part (after the semicolon):
A simple CF will converge if
all the terms are positive and the accumulated sums of those terms increases without limit (the sum of the first r terms tends to infinity as r increases). If we have positive integers only as terms then this condition is clearly satisified.
See the Pickett and Coleman reference in the next section
All the reasons above show why we focussed on simple CFs - the ones that use only positive numbers and addition.

But note on the positive side (yes, a pun!) that

phi = √5 − 1 = [ 0; 1 ] with convergents   1, 1, 2, 3, 5,8, 13, ...
21 2 3 5 81321

is also
phi = √5 − 1 = [ 1; −3, 3 ] with convergents   1, 2, 5, 13 ,34, ...
21 3 8 21 55

showing that the CF form with the negative numbers converges faster than the simple CF does.
The same is true for the reciprocal value
1 = Phi = √5 + 1 = [1; 1 ] = [2; −3, 3 ]
phi2

15 The General CF

If we remove the restriction that the numerators in our (simple) CFs are 1, we have a General CF. Here are some examples for the numbers e and π.
Earlier we saw a simple CF for e but it also has these forms:

e – 1 = 1 + 
2

2
3

3
4

4
5

5 + ...

= 1 + 
1

1
1

2
2

3
3

4
4

5 + ...
The above forms were found by the Swiss mathematician Leonhard Euler (1707-1783). The alternative notation mentioned above comes into its own here as it is readily extended for Euler's general CF:
e – 1 = 1 +2345 ... = 1 + 11234 ...
2 + 3 + 4 + 5 + 1 + 2 + 3 + 4 + 5 +

There are other more general forms of continued fraction for π which, like those for e above, do not have all numerators 1. This one was found sometime around the year 1655 by William Brouncker:

4 = 1 +12
π2 + 32
2 + 52
2 + 72
2 + ...
This has an extremely slow rate of convergence and even after 1000 terms (fractions) two successive convergents are 3.14059... and 3.14259... .

Here are two more, the second one is from Euler:


4 = 1 + 

π
12

3 + 
22

5 + 
32

7 + 
42

9 +  ...
   

π = 3 + 
12

6 + 
32

6 + 
52

6 + 
72

6 + 
92

6 +  ...
The first takes only 10 terms to find Pi to 4dps and 16 terms to find 10dps but the second takes 33 terms (ending with a 6 as a denominator) to find 4dps and even after 1000 terms only has only 9 dps accuracy.

In 1748 Euler found these:

π = 1 + 21×33×55×7
23 +4 +4 +4 + ...

π = 1 + 11×22×33×4
21 +1 +1 +1 + ...
Pickett and Coleman have a simple CF for π - the numerators are all 1 - but which has fractions as the terms in the denominators and these fractions are the Harmonic Series (which increases without limit so the resulting simple CF will converge):
π = [1; 1, 1/2, 1/3, 1/4, 1/5, ... ]
2
However, it converges very slowly. Stopping at 1000 terms we have 3.14124... with only the first 3 dps being accurate.

16 Links and References

Three articles on continued fractions with a single repeated digit or a pair of repeated digits or with a single different digit followed by these patterns:

Valid HTML 4.01! © 1996-2018 Dr Ron Knott ronknott AT mac DOT com updated: 31 August 2023