An Introduction to the Continued Fraction
Continued fractions are just another way of writing fractions.
They have some interesting connections with a jigsaw-puzzle problem
of splitting a rectangle up 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 Continued Fraction Converter and Calculator
is available in a separate window by clicking on this icon:
wherever it appears.
Contents of this Page
The
icon means there is a
Things to do investigation at the end of the section.
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:
| 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 + 16 + 13 | | | 16 |
| = 2 + |
| 13 | | | 16 |
| = 2 + |
| 1 | |
| 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:
| 45 | | | 16 |
| = 2 + |
| 13 | | | 16 |
|
= 2 + |
| 1 | | | 16/13 |
| = 2 + |
| 1 |
|
| 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:
| 45 | | | 16 |
| = 2 + |
| 1 |
|
| 1 + |
| 3 | |
| 13 |
|
|
= 2 + |
| 1 |
|
| 1 + |
| 1 | |
| 13/3 |
|
| = 2 + |
|
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.
| 45 | | | 16 |
| = 2 + |
|
This expression relates directly to the geometry of the rectangle-as-squares jigsaw as follows:
- 2 orange squares (16 x 16)
- 1 brown square (13 x 13)
- 4 red squares (3 x 3)
- 3 yellow squares (1 x 1)
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.
We can do the same to any fraction, P/Q
(P and Q are whole, positive numbers)
expressing it in the form of a continued fraction as follows:
| P | = |  |
Q |
|
a + | |
|
= a+1/(b+1/(c+1/(d+...))) = |
|
where a, b, c, d, e, etc are all whole
numbers. If P/Q is less than 1, then the first number, a, will be 0.
The second form takes lots of vertical space on the page. The third form is
the same mathematically, but all those brackets are confusing to read! The final form is used in some books as a convenient shorthand as it is both
easy to read and takes little space on the page.
There is an even simpler notation (the list notation) that we introduce in the next section.
Note that usually all the numbers in the continued fraction will be positive although alternative
forms are possible where negative whole numbers are allowed, but not on this page.
The fractional form that we have derived is called the continued fraction.
There is no need to draw the rectangles-as-squares pictures each time,
unless you want to, because we can merely look at the numbers.
If the fraction is less than 1, we use its reciprocal and then we can
split it into a whole-number part plus another fraction which will be
less than 1 and repeat. We stop when the fraction has a numerator or
a denominator of 1.
Take for instance, 7/30. It is already less than 1 so we start off by
writing it as
7/30 = 0 + 1/(30/7)
and then we apply the method of the last paragraph:
7/30 = 0 + 1/(4 + 2/7)
= 0 + 1/(4 + 1/(7/2))
= 0 + 1/(4 + 1/(3 + 1/2))
= 0 + 1/(4 + 1/(3 + 1/(1 + 1/1)))
Either of the last two lines is a valid continued fraction form for 7/30 and we can, of course,
just omit the "0 +" part.
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 (it is the whole number part of the value)
and the rest are 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 if the value of the fraction
is less than 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 one.
For instance, one half is:
1/2 = [0,2] which we can also write as [0,1,1]
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 | is |
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,in its list form is just 0 + 1/(45/16), i.e. we 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 list form of the fraction 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 = [2]
The LAST number in the list
Did you notice in the equation marked (*)
above that there were 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 provided n is bigger than one.
So we have the general rule:
Every finite continued fraction ending with n>1 has two forms:
- one ending with n BIGGER THAN 1 i.e. [ ..... , n ]
- one ending with 1 i.e. replace the final n by (n-1) + 1/1 i.e. [ ..... , n-1 , 1 ]
Things to do
You might find the
Continued Fraction Calculator useful in this section.
- Express the following as continued fractions:
- 41/13
- 125/37
- 5/12
-
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? What is the length of each of the rectangle's sides if
the smallest squares have sides of length 2?
- 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?
- [2, 1, 4, 4]
- [2, 1, 4, 5]
- [2, 1, 4, 6]
- [2, 1, 4, 7]
- [2, 1, 4, n]
How is your pattern related to the proper fraction for [2, 1, 4] ?
-
Convert these pairs of continued fractions into a single proper fraction:
- [0, 1,2,3] and [0, 1,2,2,1]
- [1, 1,2] and [1, 1,1,1]
- [3, 2] and [3, 1,1]
What is the general principle here?
- This investigation looks at the square numbers:
1, 22=4, 32=9, 42=16,
52=25, 62=36, 49, 64, 81, 100, 121, 144, ...
and forms fractions from neighbouring pairs.
With thanks to Anthony Shaw who first told me of these patterns.
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.
- 25/16
- 49/36
- 81/64
- 121/100
- ...
Can you spot the pattern?
Hint: express the two numbers in the proper fraction
using the square numbers (2n)2 and (2n+1)2
Does 9/4 fit into this pattern too?
- Here is another sequence of fractions similar to the previous
investigation and again formed from successive square numbers.
Convert each of these fractions to a continued fraction.
- 36/25
- 64/49
- 81/100
- 121/144
- ...
What is the pattern this time?
Again express it in mathematical terms using
(2n)2 and (2n+1)2.
-
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?
- Convert the successive Fibonacci number ratios into continued fractions.
You should notice a striking similarity in your answers.
- 1/1
- 2/1
- 3/2
- 5/3
- 8/5
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?
- The last question made fractions from neighbouring Fibonacci numbers.
Suppose we take next-but-one pairs for our fractions, e.g.
1, 1, 2, 3, 5, 8, 13, etc.
2 3 5 8 13 21 34
Convert each of these to continued fractions, expressing them in the list
form. What pattern do you notice?
Converting a Continued Fraction to a single Fraction
The simplest way is just to "fold" the continued fraction from the right-hand end:
| [2,1,3,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
A surprising result 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.14285714285714285 | = 0, 7 | = 0, 6, 1 |
| 2/7 | = 0.2857142857142857 | = 0, 3, 2 | = 0, 3, 1, 1 |
| 3/7 | = 0.42857142857142855 | = 0, 2, 3 | = 0, 2, 2, 1 |
| 4/7 | = 0.5714285714285714 | = 0, 1, 1, 3 | = 0, 1, 1, 2, 1 |
| 5/7 | = 0.7142857142857143 | = 0, 1, 2, 2 | = 0, 1, 2, 1, 1 |
| 6/7 | = 0.8571428571428571 | = 0, 1, 6 | = 0, 1, 5, 1 |
You may have noticed the following patterns in the table:
- The decimal fractions are made up of the same set of repeating digits: ...142857... in a cycle:
- Each decimal fraction begins at a different place in the cycle:
|
|
- Each CF begins with 0 because all the fractions are less than 1
- After the initial zero, every CF list also appears in the table in reverse.
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, but the final property,
that all the CF lists after the initial zero do appear in the table in reverse order too!
So our "surprising result" is that
When we reverse the CF list of a fraction (after the initial number), the new fraction will have
the same denominator
More precisely,
if [a0, a1, ... an–1, an] is A/B and
[a0, a1, ... an–1] is C/D then
[an, an–1, ... a0] = A/C
For example:
[1,1,1,2] = 8/5 and [1,1,1] = 3/2 so [2,1,1,1] = 8/3
This result is proved in an amazing way by Harvey Mudd College's Professor of Mathematics:
Art Benjamin -
see
Counting on Continued Fractions Arthur T Benjamin, F E Su, J J Quinn
Maths Mag vol 73 (2000), pages 98-104
also on Art's
list of papers, preprints and books
where there is a link to a PDF version to view.
A T Benjamin, J J Quinn, W Watkins,
Proofs That Really Count
published by The Mathematical Association of America (Aug 2003), 208 pages.
This is a wonderful book on using counting methods in proofs by induction to prove many
results in combinatorics and number theory which includes many Fibonacci number formulae. The authors
make the proofs both easy to understand and fun too!
Lev Dolgov of Russia emailed me (Sept 2009) to say that he has found that
if a<b then a/b and (b-a)/b have CFs which are the reverse of
each other when the alternative form of each reversed CF is used.
For example:
2/13 = 0,6,2 and reversing the part after the 0 gives 0,2,6 with alternative form 0,2,5,1
Now reversing the part after the 0 gives the CF of 11/13 = 0,1,5,2
Euler showed that the CFs a1, a2, ... an and its reversal
an, an-1, ... a1 have the same numerators:
see Davenport's book in the References section at the foot of this page.
Here are some investigations for you to do:
Things to do
You might find the
Continued Fraction Calculator useful in this section.
- Make a list of the CF lists for all the fractions less than 1 with
- a denominator of 5 (1/5, 2/5, 3/5, 4/5)
- a denominator of 6
- denominators 7 and 8 are above in this section
- a denominator of 9
- and so on as far as you want to go.
The calculator link above is useful as it keeps the results in a window
so you can cut-and-paste them. Use them to answer the following questions.
- Suppose we know the CF list for a/n. Can you find a rule which tells you which fraction b/n has the CF
which is the reverse of a/n's (after the initial zero)?
If you do find a rule (or a rule that always gives some of the fractions if not all),
please do let me know using the email address at the bottom of
this page.
- In the list of fractions with denominator 7 and 8 in the text above,
some fractions are the same when reversed:
E.g.
6/7 = 0, 1, 5, 1 and 1,5,1 reversed is also 1,5,1
5/8 = 0, 1, 1, 1, 1, 1
Such lists are called palindromes or palindromic.
Find the 6 other palindromic CFs in the two tables above.
- Some word puzzles
- Find some pairs of words where each is the other when reversed: e.g.
evil reversed is live and live reversed is evil
straw and warts
- Find some words which are palindromes, such as
eye, civic, radar, level, madam
What's the longest you can find?
- Another good word game is to find a phrase that is a palindrome. Here we ignore the spaces between letters.
E.g. When Eve, the first woman, was presented to Adam, the first man, he might have said (in English!)
Madam, I'm Adam
(to which she would have replied,
Eve
of course!) and both of these
are palindromic phrases.
Another famous palindromic phrase is about the Panama Canal
connecting the Atlantic and Pacific oceans across the narrow neck of land joining Central to Southern America:
A man, a plan, a canal: Panama!
Invent some of your own. If you can make any about Fibonacci or any topic
on the pages
at this site, do email me and I'll place them here with your name so everyone can see them!
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 x | 16 | + | 13 | : 45 is a multiple of 16 with 13 left over |
| 16 | = | 1 x | 13 | + | 3 | : 16 is a multiple of 13 with 3 left over |
| 13 | = | 4 x | 3 | + | 1 | : 13 is a multiple of 3 with 1 left over |
| 3 | = | 3 x | 1 | + | 0 | : 3 is a multiple of 1 exactly. |
| L | = | Nx | 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
- precise, and
- works for any two numbers in place of 45 and 16, and
- it always terminates since each time L, R and S are reduced until eventually
S is 1 and R is 0.
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 and 2 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.
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
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 | | | 720 |
| = |
| 168 ÷ 24 | | | 720 ÷ 24 |
| = |
| 7 | | | 30 |
| and similarly |
| 720 | | | 168 |
| = |
| 30 | | | 7 |
| = 4 + |
| 2 | | | 7 |
|
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 = 4x168 + 48
168 = 3x 48 + 24
48 = 2x 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!
Here is a rectangle 720 by 168 split up into squares, as above. 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 | | | 168 |
|
= 4 + |
| 48 | | | 168 |
|
= 4 + |
| 1 | | | 168/48 |
|
= 4 + |
| 1 | |
| 3 + |
| 24 | | | 48 |
|
|
= 4 + |
| 1 | |
| 3 + |
| 1 | | | 2 |
|
|
Things to do
You might find the
Continued Fraction Calculator useful in this section.
- For each of the fractions in the previous Things To Do section,
use Euclid's algorithm to check your answers.
- 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
What numbers stand in place of the letters?
What is the general principle for computing the gcd,
given two numbers expressed as powers of the same primes?
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 Proposition 3 of Euclid's The Elements, Book 7.]
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:
| 1· |
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.
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!
For example, 2·875 has a whole part of 2 so write that down to begin its continued fraction:
2·875 = [2, ... ]
As in the jigsaw method, now remove that part and take the reciprocal of the
remainder which, for us, means taking the reciprocal of the part after the decimal point:
1/ ·875 = 1·14285714....
Again, write down the whole part (1) as the next component of the continued fraction and invert the
part after the decimal point:
1/ ·14285714.. = 7.00000014...
This time the whole number part is 7 and the remainder is very close to 0
Now we have a choice: we could
stop here and end the continued fraction:
2·875 = [2,1,7]
or we could continue with the very small part.
Checking, shows that when we expand [2,1,7] we have 23/8 which is 2.875 exactly.
So the only problem with this method is deciding when to stop. Each time we take the reciprocal
of the fractional part we usually get another long list of decimal places. Eventually these are
meaningless because the original decimal number was given only to a finite number of decimal
places.
For this reason, the next method is better as it stops automatically
when we get to the limit of the accuracy of
the starting decimal. [We meet this problem later in the section
Using the decimal value from
your calculator for the Cf of a square-root.]
Things to do
- Convert 64/29 into a continued fraction using the Jigsaw method or Euclid's algorithm.
- 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?
If we have a number in the form of decimal fraction, such as 2·875 then we can always represent
it as a proper fraction by using a denominator which is a big enough power of 10:
- The number of places we have to move the
decimal place to the right until it comes after all the decimal digits
- is the power of ten that appears in the denominator and
- is also the number of 0's in the power of ten in the denominator.
For instance,
- 1·2 means moving the decimal point 1 place to the right so 1·2
is just 12/10
- Similarly 2·875 is 2875/1000
- and 0.00075 is 75/100000.
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 |
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.
The next section shows how we can handle one specific (and common) variety of repeating
non-terminating decimal fraction - those of square-roots.
But what about a continued fraction for √2? Since it's decimal
fraction never ends, and it is not possible to write it as a fraction, how can
we convert it to a continued fraction?
Algebra can come to our assistance here.
To express √2 as a continued fraction, we know its value is
bigger than 1 so we will write it as:
√2 = 1 + 1/x
[We use 1/x so that x will be bigger than one.]
All we have to do now is find x!
So let's rearrange this equation to find the value of x:
(√2 – 1) = 1/x
so x = 1/(√2 – 1)
There is a useful technique for simplifying fractions with square-roots in the
denominator, to get a whole number in the denominator: Here we will
multiply the top and bottom of the fraction by (√2 + 1):
| x = |
| 1 |
|
| √2 – 1 |
| = |
| 1 |
(√2 + 1) |
|
| (√2 – 1) |
(√2 + 1) |
|
= |
| √2 + 1 |
|
| 2 – 1 |
|
= |
√2 + 1 |
x = √2 + 1 = 1 + 1/x + 1 = 2 + 1/x
By substituting 2 + 1/x wherever we see x, we now have our continued fraction for x:
x= 2 + 1 = 2 + 1 = 2 + 1 = ...
x 2 + 1 2 + 1
x 2 + 1
x
So now we can express √2 as a continued fraction, which goes on for ever
but which has a simple pattern for its components:
| √2 = 1 + | 1 | = 1 + | 1 |
| |
| x | 2 + | 1 |
| | |
| 2 + | 1 |
|
| 2 + | 1 |
|
| 2 + ... |
In terms of our list notation, we would write:
√2 = [1, 2, 2, 2, 2, 2, 2, ...]
|
It turns out that every square root has a continued fractions that ends up as a repeating pattern.
Below is a 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]
Here is a table of the square-roots of all numbers from 2 to 100:
| √n | [ a; Period ] |
|---|
| √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. Can you extend his table? Can you find a single overall unifying formula?
Things to do
You might find the
Continued Fraction Calculator useful in this section.
- What patterns do you notice in the table of square-roots above?
Four easy ones first:
- What is special about the first number of the continued fraction?
- What is special about the last number in the periodic part?
- Can you spot the connection between these two numbers in each row of
the table?
- What about the other numbers in the periodic part? Is there a
pattern to them that they ALL have?
- Now let's look for patterns in the table as a whole.
How about the continued fractions for the square-roots of
2, 5, 10, 17 and 26.
- What pattern do they all have?
- What is the next number in this sequence of square-roots
that has the same pattern?
- Can you prove your results?
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,... ].
- How about this pattern:
look at the square-roots of 3, 6, 11, 18 and 27.
- What is the pattern this time? Express the general pattern as
a mathematical expression.
- What is the next square-root with this pattern?
- Again try to verify your results are always true.
- ..or spot the pattern in these sequences of square-roots:
- 3, 8, 15, 24 and 35
- 7, 14, 23, 34 and 47
- 12, 39 and 84
- 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
number's too - what pattern connects the CF lists for the square-roots of :
6, 12, 20 and 30?
- So what about 13? What pattern starts with the square-roots of 13, 29
and 53?
- Elliott Landowne emailed me (16 Sept 2011) about the following pattern that he had spotted in
the CFs of some square roots:
- √19 – 4 = [2, 1, 3, 1, 2, 8]
- √54 – 7 = [2, 1, 6, 1, 2, 14]
- √107 – 10 = [2, 1, 9, 1, 2, 20]
He thinks the general pattern is:
- √( (3n + 1)2 + 2n + 1) – (3n + 1) = [2, 1, 3n, 1, 2, 6n+2]
Can you provide a proof of this?
- What other patterns can you find that cover most of the rest of the
numbers up to 100?
What square-roots are left over?
Was the table above produced by a computer program?
Yes!
The algorithm is explained in R. B. J. T. Allenby and Ed. Redfern's
excellent book
Introduction to Number Theory with Computing,
published by E Arnold in 1989 but now out of print. It is well worth browsing through
if you can find a copy in your library.
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 looks
at how you can find these for yourself, with or without a computer.
Methods of finding continued fractions for square roots
Using the decimal value from your calculator
You can produce the first few numbers of a continued fraction for a square root
as follows:
- Find the first few decimal places of the square root using your calculator e.g. √2 = 1.414
- Then express this decimal fraction as an ordinary fraction: use a large enough power of 10
as the denominator so that the numerator and denominator
are integers, e.g. 1414/1000
- Next use Euclid's algorithm explained earlier on this page
to find the entries in the continued fraction list for this ordinary fraction, e.g.
| 1414 = | 1 x 1000 + 414 |
| 1000 = | 2 x 414 + 172 |
| 414 = | 2 x 172 + 70
|
| 172 = | 2 x 70 + 32
|
| ... |
so √2  1.414 = [1, 2,2,2,...]
|
This will produce enough of the continued fraction for you to spot the pattern for many square-roots.
But since we started with an approximation to the square-root (your calculator or computer will only produce
perhaps up to 15 decimal places at most), this method will be only approximate. The more decimal places
of the square root that you use in your initial integer fraction, the longer will be the list of correct
numbers from Euclid's algorithm for the continued fraction, but eventually, the continued fraction's numbers
will differ from the true square-root.
To illustrate, the approximation for √2 above as 1414/1000 continues as
80 = 6 x 12 + 8
12 = 1 x 8 + 4
8 = 2 x 4
So 1414/1000 = [1, 2, 2, 2, 6, 1, 2] (which is correct and exact) but the true continued fraction for
√2 is [1, 2, 2, 2, 2, 2, 2, 2, 2, ...].
The problem with this method is
If we don't know the CF for the square-root, how do we know when this method stops giving the
CF for the true square-root?
Is there a better method that produces the exact and complete continued
fraction for a square root?
There is, using algebra, and it relies on the fact that we finding square roots.
Using algebra
The CF in the earlier example for √2
stopped quickly so that the period was just the single number: 2.
So let's look at another example as we explain and illustrate
the general method.
Square-roots in 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 (x+y) and (x–y) as the two factors of x2 – y2
or you can just 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 |
|
| √27 + 4 |
| = |
| 3 | (√27 – 4) |
|
| (√27 + 4) | (√27 – 4) |
| = | | 3(√27 – 4) |
|
| 27 – 16 |
|
= | | 3(√27 – 4) |
|
| 11 |
|
So we have transformed a fraction with a square-root term in the denominator to one with a
square root term in the numerator.
The algebraic algorithm
Here is a method which will find the exact CF for any (whole-number) square-root.
In the following we assume n is not an exact square number because in that case finding √n is very simple!
The steps in the algorithm 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.
For example, if n=14 and we are trying to find the CF for √14, then 9 is the nearest square below 14, so
m is 3 and n lies between m2=9 and (m+1)2=16.
The whole number part starts off your list of numbers for the continued fraction.
The easy way to find the largest square number below n is to use your calculator:
Find √n and just ignore the part after the decimal point! The number showing is m.
Now, √n = m + 1/x
where n and m are whole numbers.
- Step 2:
- Rearrange the equation of Step 1 into the form of x equals an expression 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 convert it
into a fraction with whole numbers in the denominator.
In this case, multiply top and bottom by
(√ n + m) and simplify.
- either Step 4A:
- stop if this expression is the original square root plus an integer.
- or Step 4B:
- 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, ...] 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 1 | Step 2 | Step 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 |
|
| √14 | =3 + | | 1 | | | x1 |
| =3 + | | 1 | | | 1 + | | 1 | | | x2 |
|
|
| =3 + | | =3 + | | 1 | | |
| =3 + | | 1 | | |
| = [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].
Substituting again 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.
Solving Quadratics with Continued Fractions
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 and 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".
So we can replace the x in "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, ...]
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,2,..] that is x = 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,2,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 |
|
|---|
| = x | 1+√2 | 1–√2 |
|---|
This means that [2,2,2,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,2,2,2...].
Thus 1–√2 is –[0,2,2,2,2,...].
Things to do
- Repeat the above for [A,A,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.
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, 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
Things to do
You might find the
Continued Fraction Calculator useful in this section.
- Find the 2 roots and a continued fraction for a root of these quadratic equations:
- x2 + x = 1
- x2 – 2x = 1
- What happens if we try to find square-roots using this method,
for example, the square root of 2 is a solution to x2 – 2 = 0.
Why do we not get a continued fraction this time?
How does the answer to the second part of the previous question give a continued fraction for
√2?
The Silver Means
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,2,2,2,2, ...]
[3, 3,3,3,3,3, ...]
[4, 4,4,4,4,4, ...]
[5, 5,5,5,5,5, ...]
...
These also 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!
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,n,n,n,n, ...]
so T(n) = n+1/(n+1/(n+..)) or T(n) = n+1/T(n) since the value inside the brackets
is just T(n)! So we 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).
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!
Things to do
You might find the
Continued Fraction Calculator useful in this section.
- 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:
- Enter any positive number you like.
- Press the reciprocal button (to find 1 divided by the displayed number).
- Add 2 (or, to find T(n), add n) and write down the result.
- 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.
- 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 see the answer in next section!)
- Use the method above to find numerical values for T(3) and T(4).
Exact values of the Silver Means
The Things To Do 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 = nT(n)+1.
For example, the number [5, 5,5,5,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 is bigger than 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 Things To Do explores this series and produces some
more amazing connections between Phi and the Fibonacci numbers!
Things to do
You might find the
Continued Fraction Calculator useful in this section.
- 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,29,29,40,... ?
-
- What is the next line in the table above for T(11)?
- Express the n-th line, that is T(n) as a formula involving
square-roots.
- T(1) is Phi = ( 1 + √5 )/2.
- T(4) = 2 + √5 and also involves √5. Using the
Table of Properties of Phi
express T(4) as a power of Phi.
- T(11) also involves √5. What is T(11)?
Is it a power of Phi too?
- 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.]
- What powers of Phi are missing in the answer to the previous question?
What are their continued fractions?
- 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.
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 shown like this.
| Phi1= | 0 + 1 Phi= | (√5 + 1)/2 | = [1] |
| Phi2= | 1 + 1 Phi= | (√5 + 3)/2 | = [2,1] |
| Phi3= | 1 + 2 Phi= | (2√5 + 4)/2 | = [4] |
| Phi4= | 2 + 3 Phi= | (3√5 + 7)/2 | = [6,1,5] |
| Phi5= | 3 + 5 Phi= | (5√5 + 11)/2 | = [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] |
|
T(3)1 | = 0 + 1 T(3) | = (3 + √13)/2 | = [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] |
T(3)3 | = 3 + 10 T(3) | = (36 + 10 √13)/2 = | = [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] |
T(3)5 | = 33 + 109 T(3) | = (393 + 109 √13)/2 = | = [393] |
Things to do
You might find the
Continued Fraction Calculator useful in this section.
- 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?]
- Make a new Table like that for T(2) above but this time for T(3) = (3 + √13)/2 and its powers.
Answer the previous question for the new series 1, 3, 10, 33, 109, ...
- 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)?
- 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.
-
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?
- 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!
Fibonacci-related Continued Fractions
Here is a table of fractions corresponding to the continued fractions [1,a] for a few values of a:
| a | 1 | 2 | 3 | 4 | 5 | ... |
|---|
| [1,a] | 2 | 3/2 | 4/3 | 5/4 | 6/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]:
| a | 1 | 2 | 3 | 4 | 5 | ... |
|---|
| [1,1,a] | 3/2 | 5/3 | 7/4 | 9/5 | 11/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:
- a numerator which is (a+1)+a, the sum of the numerator and denominator of (equation 1)
- a denominator which is the numerator of the corresponding fraction of (equation 1)
The same thing happens with CFs of the form [1,1,1,a]:
| a | 1 | 2 | 3 | 4 | 5 | ... |
|---|
| [1,1,1,a] | 5/3 | 8/5 | 11/7 | 14/9 | 17/11 | ... |
|---|
Algebra again helps here:
[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:
- a numerator which is (2a+1)+(a+1), the sum of the numerator and denominator of (equation 2)
- a denominator which is the numerator of the corresponding fraction of (equation 2)
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 |
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 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 |
The author reports 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!
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).
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 - those which are closer than any previous ones with a smaller denominator.
It also computes the error of the approximation and shows the continued fraction for each
approximation. Continued fractions are very useful for finding fractions that are
the best approximations to any value.
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 |
| | | | | | | | | | | | | | | |
| 1 | 4 | 5 | 6 | 7 | 57 | 64 | 71 | 78 | 85 | 92 | 99 | 106 | 113 | 16604 | 16717 |
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 ] = 3+1/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] = 3+1/(7+1/15) = 333/106 = 3.1415094.. = pi – 0.00008..,
- [3, 7, 15, 1 ] = 3+1/(7+1/(15+1/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 ] = 3+1/(7+1/(15+1/(1+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 ] = 3.141592653921421 = 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 any set of 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
- the convergents are proper fractions
- the convergents alternate between being larger and smaller than the exact value
- if a convergent is smaller than the exact value, no other fraction with smaller denominator is closer and smaller than the exact value
- if a convergent is larger than the exact value, no other fraction with smaller denominator is closer and larger than the exact value
Earlier we saw that
the square-root of 2 is [1; 2,2,2,2,2,...]. So the following sequence of values will
give rational approximations to root-2:
| Shortened CF | Fraction | Value | Error |
|---|
| [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.
Look again at the table for the convergents for (1+√3) in the previous section.
Is there an easy way of calculating the convergent fractions without starting from scratch each time?
Yes there is -- and it is a simple variation on how we computed 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
- [a] = a
- [a,b] = a+1/b = (ab+1)/b
- [a,b,c] = a+1/(b+1/c) = a+c/(bc+1)= (abc+a+c)/(bc+1)
Here is an easier method of finding these convergent fractions:
| Step 1: | Step 2: | Step 3... |
|---|
|
So if the CF begins with a, the first fraction is a/1.
Also, put an imaginary row before the first one, with the "fraction" 1/0 in it.
So our table looks like this
|
We now continue using the CF element that starts the new row:
For the n column:
multiply the CF element of the new row (here, b)
by the latest n value on the row above (here a)
then add to this the n value of the row before that one
(here 1).
Do the same for the d column to get b×1 + 0 = b
We now have the next convergent n/d:
|
The same procedure fills in the rest of the table as far as we want to go,
using the new CF element and the previous two rows only:
|
|
|
| CF | n | d | n/d |
| | 1 | 0 | 1/0 |
| a | a | 1 | a/1 |
| b | ab+1 | b | (ab+1)/b |
| c | | | |
|
| CF | n | d | n/d |
| | 1 | 0 | 1/0 |
| a | a | 1 | a/1 |
| b | ab+1 | b | (ab+1)/b |
| c | c(ab+1)+a | cb+1 | (c(ab+1)+a)/(cb+1) |
|
There is an example in the next section:
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:
1+√3 convergents
| CF | n | d | n/d | error
2.7320508..-n/d |
| 2 | 2 | 1 | 2.00000000 | 0.7320508076 |
| 1 | 3 | 1 | 3.00000000 | -0.2679491924 |
| 2 | 8 | 3 | 2.66666667 | 0.0653841409 |
| 1 | 11 | 4 | 2.75000000 | -0.0179491924 |
| 2 | 30 | 11 | 2.72727273 | 0.0047780803 |
| 1 | 41 | 15 | 2.73333333 | -0.0012825258 |
| 2 | 112 | 41 | 2.73170732 | 0.0003434905 |
| 1 | 153 | 56 | 2.73214286 | -0.0000920496 |
| 2 | 418 | 153 | 2.73202614 | 0.0000246638 |
| ... |
So the first row is the convergent with CF [2] which is the value 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 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.
When we try this for the golden section number Phi = [1,1,1,1,1,1,...] we get....
| CF | n | d | n/d |
|---|
| | 1 | 0 | 1/0 |
| 1 | 1 | 1 | 1/1 |
| 1 | 2 | 1 | 2/1 |
| 1 | 3 | 2 | 3/2 |
| 1 | 5 | 3 | 5/3 |
| 1 | 8 | 5 | 8/5 |
... 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.
From the examples above, we see that our rational approximations get better if we have large
numbers in the continued fraction of the value we are approximating.
So the "hardest" number to make "rational" would be one with the smallest terms, namely, all ones.
This is Phi - the golden section number!
The best rational approximations to Phi are just the ratios of successive Fibonacci numbers.
So Ian Stewart, and others, have called Phi "the most irrational number" because of this.
But I prefer to call it
the "least irrational number" because it is so easy to approximate it with fractions!!
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/2, 7/5, 17/12, 41/29, 99/70,...
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), or 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!
Click
on the orrery picture for more details and a larger picture.
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(45)=cos(45°)=1/√2
sin(30°)=cos(60°)=1/2 and
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?
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! In particular, e does.
e
e is the base of
natural logarithms and a number which occurs in many places in
mathematics. e is also the number that this series settles down to
eventually:
(1+1/2)2=2·25
(1+1/3)3=2·37037..
(1+1/4)4=2·4414..
(1+1/5)5=2·48832,
(1+1/6)6=2·5216..,
... |
that is: |
e = | Limit (1 + 1/n)n |
| | |
n->infinity |
|
2· | 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 ...
|
As a continued fraction, it can be written as
e – 1 = 1 + | |
|
= 1 + | |
|
The above forms were found by the Swiss mathematician
Leonhard Euler (1707-1783).
Note that the above continued fractions do not always
have 1 as the numerator (the top part) of the fractions. That is why we do not
write them in the abbreviated form as a list inside square brackets. The list notation is
only used for when all numerators are 1.
However, another form for e is possible which does have our "standard" form:
e = [2; 1,2,1, 1,4,1, 1,6,1, 1,8,1, 1,10,1, ...]
The pattern continues with .. 1, 2n, 1, ... repeated for ever.
Hendrik Jager wrote to me with the following:
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 2e.
My proof however is too complicated to give in an email.
What other CFs can you find for e or its powers and multiples?
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:
|
1· | 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 ...
|
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 |
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:
| e |
| 1 | |
2 |
|
= √e = [1, 1,1,1, 5,1,1, 9,1,1, 13,1,1, ...] |
= 1.648721270700128146848651 |
|
|
| e |
| 1 | |
3 |
|
= 3√e = [1, 2,1,1, 8,1,1, 14,1,1, 20,1,1, ...] |
= 1.395612425086089528628125 |
|
|
| e |
| 1 | |
4 |
|
= 4√e = [1, 3,1,1, 11,1,1, 19,1,1, 27,1,1, ...] |
= 1.284025416687741484073421 |
|
|
| e |
| 1 | |
5 |
|
= 5√e = [1, 4,1,1, 14,1,1, 24,1,1, 34,1,1, ...] |
= 1.221402758160169833921072 |
|
|
| e |
| 1 | |
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 |
|
|
We can take odd-numbered roots (cube-roots, fifth-roots, seventh-roots, etc) of e2 and discover
another simple pattern:
| e |
| 2 | |
3 |
|
= [1, 1,18,7, 1,10,54,16, 1,19,90,25, 1,28,126,34, ...] |
= 1.947734041054675856639021 |
|
|
| e |
| 2 | |
5 |
|
= [1, 2,30,12, 1,1,17,90,27, 1,1,32,150,42, 1,1,47,20,57, ...] |
= 1.491824697641270317824853 |
|
|
| e |
| 2 | |
7 |
|
= [1, 3,42,17, 1,1,24,126,38, 1,1,45,210,59, 1,1,66,294,80, ...] |
= 1.3307121974473499773031851 |
|
|
| e |
| 2 | |
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+1, ...] |
|
|
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!
There are other more general forms of continued fraction for pi which, like those for e above, do not have numerators (the top part of fractions) which are always 1.
This one was found sometime around the year 1655 by
William Brouncker:
For more on the two continued fractions below, see An Elegant Continued Fraction for Pi by L J Lange in
American Mathematical Monthly vol 106 (1999), pages 456-8.
|
| |
 = 3 + | |
|
Other numbers
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) or 1/tanh(1) .
| [3; 6, 9, 15, 21, 27, ...] = 3.16365 81744 60733 57425 12504 13949 97067 07498 11590 78820 ... = | 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, ... ] = |
|
which involves the Bessel I function. More about them is 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.
CFs connecting π, Φ and e
The remarkable mathematician
Ramanujan
proved a connection between
π, e and Φ
which involved a continued fraction and another involving
π, e and φ:
| ( √(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 + ... |
|
|
|
Introduction to the Theory of numbers by G H Hardy and E M Wright
Oxford University Press, (6th edition, 2008),
ISBN: 0199219869
has this result in section 19.15.
On Ramanujan's Continued Fraction K G Ramanathan, Acta Arithmetica, 43 (1984) pages 209-226.
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.
Squared Fibonacci Number Ratios
What is the period of the continued fractions of the following numbers?
- 25/9
- 64/25
- 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:
- 25/9 = (5/3)2 = (Fib(5)/Fib(4))2
- 64/25 = (8/5)2 = (Fib(6)/Fib(5))2
- 169/64 = (13/8)2 = (Fib(7)/Fib(6))2
- ...
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?
Continued Fractions of Quadratic Fibonacci Ratios Brother Alfred Brousseau in
The Fibonacci Quarterly vol 9 (1971) pages 427 - 435.
Continued Fractions of Fibonacci and Lucas Ratios Brother Alfred Brousseau in
The Fibonacci Quarterly vol 2 (1964) pages 269 - 276.
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.
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 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!
A Series and Its Associated Continued Fraction J L Davison, Proc Amer Math Soc
vol 63, 1977, pages 29-32, where it is also proved that this CF value is transcendental.
Sequences Associated with t-Ary Coding of Fibonacci's Rabbits
H W Gould, J B Kim, V E Hoggatt Jr Fib Quarterly vol 15 (1977) pages 311-318
show that the continued fraction above and the rabbit sequence are identical and give several other similar
CFs.
A Simple Proof of a Remarkable Continued Fraction Identity P G Anderson, T C Brown, P J-S Shiue
Proceeding American Mathematical Society vol 123 (1995), pgs 2005-2009
has a proof that the Rabbit constant is indeed the continued fraction given above.
| The continued fraction for √5 φ = |
5 – √5 |
= 1.3819660112501051518... is [1;2,1,1,1,1,1,1,1,...] |
|
2 |
| 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.
| Φ |
= | 2 |
= 0.72360679774997896964... = [0;1,2,1,1,1,1,1,1,1,1,...] |
| |
√5 |
5 – √5 |
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 |
The Strong Law of Small Numbers Richard K Guy in The American Mathematical
Monthly, Vol 95, 1988, pages 697-712, Example 14.
WWW Links
Eric Weisstein's page on
The Rabbit Constant
Chaos in Numberland: The secret
life of continued fractions Prof John D Barrow,
a +Plus magazine online article
which, if you have enjoyed this page, will extend your knowledge with more on applications
of continued fractions. Some of it
is at undergrauate mathematics level.
References to articles and books
-
C. Kimberling, A visual Euclidean algorithm in Mathematics Teacher, vol 76
(1983) pages 108-109.
- is an early reference to the excellent Rectangle Jigsaw approach to continued
fractions that we explored at the top of this page. An even earlier description
of this method is found in chapter IV Fibonacci Numbers and Geometry of:
-
Fibonacci Numbers, N N Vorob'ev, Birkhauser (2003 translation of the 1951 Russian original).
- This slim classic is a translation from the Russian
Chisla fibonachchi, Gostekhteoretizdat (1951).
This classic contains many of the fundamental Fibonacci and Golden section
results and proofs as well as a chapter on continued fractions and their properties.
-
Introduction to Number Theory with Computing by R B J T Allenby and E Redfern
- 1989, Edward Arnold publishers, ISBN: 0713136618
is an excellent book on continued fractions and lots of other related and
interesting things to do with numbers and suggestions for programming
exercises and explorations using your computer.
-
The Higher Arithmetic by Harold Davenport,
- Cambridge University Press, (7th edition) 1999, ISBN: 0521422272
is an enjoyable and readable book about Number Theory which has an excellent
chapter on Continued Fractions and proves some of the results we have found above.
(More information and you can order it online via the title-link.)
Beware though! We have used [a,b,c,d,...]=X/Y as our concise notation
for a continued fraction but Davenport uses [a,b,c,d,..] to mean the
numerator only, that is, just the X part of the (ordinary) fraction!
-
Introduction to the Theory of numbers by G H Hardy and E M Wright
- Oxford University Press, (6th edition, 2008),
ISBN: 0199219869
is a classic
but definitely at mathematics undergraduate level.
It takes the reader through some of the
fundamental results on continued fractions.
Earlier editions do not have an Index, but there is
a Web page Index
to editions 4 and 5 that you may find useful. This latest edition, the 6th,
is revised and has some
new material on Elliptic functions too.
-
Continued Fractions by A Y Khinchin,
- This is a Dover book (1997), ISBN: 0 486 69630 8, well produced, slim and cheap, but it is
quite formal and abstract, so probably only of interest to serious mathematicians!
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:
-
A Limited Arithmetic on Simple Continued Fractions, C T Long and J H Jordan,
- Fibonacci Quarterly, Vol 5, 1967, pp 113-128;
-
A Limited Arithmetic on Simple Continued Fractions - II, C T Long and J H Jordan,
- Fibonacci Quarterly, Vol 8, 1970, pp 135-157;
-
A Limited Arithmetic on Simple Continued Fractions - III, C T Long,
- Fibonacci Quarterly, Vol 19, 1981, pp 163-175;
© 1996-2013 Dr Ron Knott
updated 20 February 2013
The Golden Section
Fibonacci Home Page
The Golden String
