*Mark Herkommer
February 24, 2014
*

( Excerpted from my book:
Number Theory: A Programmer's Guide )

Introduction

Number theory has many tools but probably none is more fascinating or elegant than continued fractions. It was once said that God invented the integers and man invented everything else. It might be added God probably invented continued fractions as well. Continued fractions were developed (or discovered) in part as a response to a need to approximate irrational numbers. Since that time they have distinguished themselves as important tools for solving problems in probability theory, analysis, and especially number theory. Continued fractions give us something more than solutions to specific problems. They offer another way to represent real numbers and this affords us an insight obscured by traditional decimal representations.

Because continued fractions are be developed using Euclid's algorithm it is
tempting to believe that the great geometrician used them, but this is
probably not true. The first known examples come from Rafael Bombelli (ca.
1526 - 1573), the Italian algebraist best known for having a "wild thought"
and developing the concept of complex numbers (Boyer and Merzbach, 1991). In
his Algebra, published in 1572, he gave a reasonable approximation for the
square root of 13:

4 3 + -------- 4 6 + --- 6

The formal study of continued fractions continued throughout the 17th
century with contributions from C. Schwenter and Christiaan Huygens (1629 -
1695). In 1695 John Wallis (1616 - 1703) gave continued fractions a thorough
analysis and bestowed on them the name they now bear. In their more general
form continued fractions look like:

a1 b0 + ------------------------ a2 b1 + ------------------ a3 b2 + ------------ b3 + . . . an + ---- bn

a1 a2 a3 an b0 + ---- ---- ---- . . . ---- b1 + b2 + b3 + bn

The numbers ai and bi are called the ith partial numerator and denominator of the continued fraction. Finite (or terminating) continued fractions have a finite n and therefore a finite number of terms. If there are an infinite number of terms then the continued fractions are called infinite (or non- terminating). If we consider only those continued fractions ai = 1 for all i:, and bi are all positive integers (with the possible exception of bn), then we have the special case of simple or regular continued fractions:

1 1 1 1 b0 + ---- ---- ---- . . . ---- b1 + b2 + b3 + bn

[ b0, b1, b2, b3, ... , bn ]

The bi are called the partial quotients. There should be no confusion between this notation and the greatest integer function which takes only one term.

An important fact about continued fractions is that they can be used to represent any real number; a fact which should be stated as a formal theorem.

**Theorem:** For every real number a, there corresponds a unique
continued fraction with value equal to a. This fraction is finite if a is
rational and infinite if a is irrational.

One final note: although fractions where ai and bi are complex numbers are
outside our scope, there are a many good books on the subject including Jones
and Thron (1980), Khinchin, Eagle, and Khinchin (1997), and Wall (1948). For
the rest of this chapter unless otherwise noted I will be considering only
simple continued fractions with partial quotients having integral values.

Finite Continued Fractions

Any positive rational number can be written as a finite continued fraction. Recall the Euclid's algorithm from Chapter 2 for finding the greatest common divisor. The methodology is identical for finding the continued fraction representation of a rational number. In the example from Chapter 2 where we were seeking the greatest common divisor for 13,020 and 5,797:

13,020 = 5,797 * 2 + 1,426 5,797 = 1,426 * 4 + 93 1,426 = 93 * 15 + 31 93 = 31 * 3 + 0

13,020 1,426 -------- = 2 + ------- 5,797 5,797

a / b | decimal | continued fraction | length |
---|---|---|---|

1 / 2 | 0.500000 | [ 0, 2 ] | 2 |

1 / 3 | 0.333333 | [ 0, 3 ] | 2 |

2 / 3 | 0.666667 | [ 0, 1, 2 ] | 3 |

1 / 4 | 0.250000 | [ 0, 4 ] | 2 |

3 / 4 | 0.750000 | [ 0, 1, 3 ] | 3 |

1 / 5 | 0.200000 | [ 0, 5 ] | 2 |

2 / 5 | 0.400000 | [ 0, 2, 2 ] | 3 |

3 / 5 | 0.600000 | [ 0, 1, 1, 2 ] | 4 |

4 / 5 | 0.800000 | [ 0, 1, 4 ] | 3 |

1 / 6 | 0.166667 | [ 0, 6 ] | 2 |

5 / 6 | 0.833333 | [ 0, 1, 5 ] | 3 |

1 / 7 | 0.142857 | [ 0, 7 ] | 2 |

2 / 7 | 0.285714 | [ 0, 3, 2 ] | 3 |

3 / 7 | 0.428571 | [ 0, 2, 3 ] | 3 |

4 / 7 | 0.571429 | [ 0, 1, 1, 3 ] | 4 |

5 / 7 | 0.714286 | [ 0, 1, 2, 2 ] | 4 |

6 / 7 | 0.857143 | [ 0, 1, 6 ] | 3 |

1 / 8 | 0.125000 | [ 0, 8 ] | 2 |

3 / 8 | 0.375000 | [ 0, 2, 1, 2 ] | 4 |

5 / 8 | 0.625000 | [ 0, 1, 1, 1, 2 ] | 5 |

7 / 8 | 0.875000 | [ 0, 1, 7 ] | 3 |

1 / 9 | 0.111111 | [ 0, 9 ] | 2 |

2 / 9 | 0.222222 | [ 0, 4, 2 ] | 3 |

4 / 9 | 0.444444 | [ 0, 2, 4 ] | 3 |

5 / 9 | 0.555556 | [ 0, 1, 1, 4 ] | 4 |

7 / 9 | 0.777778 | [ 0, 1, 3, 2 ] | 4 |

8 / 9 | 0.888889 | [ 0, 1, 8 ] | 3 |

1 / 10 | 0.100000 | [ 0, 10 ] | 2 |

3 / 10 | 0.300000 | [ 0, 3, 3 ] | 3 |

7 / 10 | 0.700000 | [ 0, 1, 2, 3 ] | 4 |

9 / 10 | 0.900000 | [ 0, 1, 9 ] | 3 |

Convergents

It is often productive to look at the behavior of a continued fraction as
terms are added. We call

[ b0, b1, b2, b3, ... , bn ]

for 0 < n < N the nth convergent to [ b0, b1, b2, b3, ... , bn ]. We can
look at approximations to a continued fractions by computing its convergents.
The nth convergent (also called approximant) fn is the value obtained by
evaluating the continue fraction to the nth convergent:

f0 = [ b0 ]

f1 = [ b0, b1 ]

...

fn = [ b0, b1, b2, b3, ... , bn ]

Consider the example from the preceding section: 13,020 / 5,797 = [2, 4,
15, 3]. Evaluating at the convergents to six decimal places we have

f0 = [2] = 2.000000

f1 = [2, 4] = 2.250000

f2 = [2, 4, 15] = 2.245902

f3 = [2, 4, 15, 3] = 2.245989

with the last being equal to 13,020 / 5,797.

Obviously each additional convergent adds a level of refinement to the approximation. What is probably not apparent is that as the convergents are added the approximation alternates between values less than and greater than the rational number.

**Theorem:** If fk is the kth convergent to the continued fraction [
b0, b1, b2, b3, ... , bn ], then

f0 < f2 < f4 < ... < f5 < f3 < f1 .

The direct consequence of Theorem 6.2 is that all continued fractions,
whether finite or infinite, converge. Put another way,

lim [ b0, b1, b2, b3, ... , bn ] exists and is finite.

n->inf

Continued fractions representations for well-known constants have long been investigated. When they can be expressed in closed form they have the ability to provide approximations to irrational numbers within any desired degree of precision. Also the rate of convergence is high so it doesn't take too many iterations to compute the number any desired degree of precision.

The golden ratio, called the precious jewel of geometry by Kepler, is the talisman of aesthetic beauty of mathematics. The golden ratio, defined as

phi = (1 + sqrt(5)) / 2

is arrived at as one of two solutions to geometric ratio problem

phi + 1 phi ------- = ----- phi 1

It is rationally approximated by successive numbers from the Fibonacci sequence. Of continued fractions,

phi = [ 1, 1, 1, 1, 1, 1, 1, 1, ... ]

has the distinct honor of being the slowest to converge of all continued
fractions; taking 26 iterations to converge to 10 decimal places (see below).

n | pn | qn | fn | phi - fn |
---|---|---|---|---|

0 | 1 | 1 | 1.0000000000 | 0.6180339887 |

1 | 2 | 1 | 2.0000000000 | -0.3819660113 |

2 | 3 | 2 | 1.5000000000 | 0.1180339887 |

3 | 5 | 3 | 1.6666666667 | -0.0486326779 |

4 | 8 | 5 | 1.6000000000 | 0.0180339887 |

5 | 13 | 8 | 1.6250000000 | -0.0069660113 |

6 | 21 | 13 | 1.6153846154 | 0.0026493734 |

7 | 34 | 21 | 1.6190476190 | -0.0010136303 |

8 | 55 | 34 | 1.6176470588 | 0.0003869299 |

9 | 89 | 55 | 1.6181818182 | -0.0001478294 |

10 | 144 | 89 | 1.6179775281 | 0.0000564607 |

11 | 233 | 144 | 1.6180555556 | -0.0000215668 |

12 | 377 | 233 | 1.6180257511 | 0.0000082377 |

13 | 610 | 377 | 1.6180371353 | -0.0000031465 |

14 | 987 | 610 | 1.6180327869 | 0.0000012019 |

15 | 1597 | 987 | 1.6180344478 | -0.0000004591 |

16 | 2584 | 1597 | 1.6180338134 | 0.0000001753 |

17 | 4181 | 2584 | 1.6180340557 | -0.0000000670 |

18 | 6765 | 4181 | 1.6180339632 | 0.0000000256 |

19 | 10946 | 6765 | 1.6180339985 | -0.0000000098 |

20 | 17711 | 10946 | 1.6180339850 | 0.0000000037 |

21 | 28657 | 17711 | 1.6180339902 | -0.0000000014 |

22 | 46368 | 28657 | 1.6180339882 | 0.0000000005 |

23 | 75025 | 46368 | 1.6180339890 | -0.0000000002 |

24 | 121393 | 75025 | 1.6180339887 | 0.0000000001 |

25 | 196418 | 121393 | 1.6180339888 | -0.0000000000 |

26 | 317811 | 196418 | 1.6180339887 | 0.0000000000 |

An algebraic number is a number that satisfies an algebraic equation
with integer coefficients. Clearly *phi* is an algebraic number because
it satisfies *phi*^2 - *phi* - 1 = 0. Numbers that do not satisfy
algebraic equations are called transcendental numbers. While the proof that a
given number is transcendental is beyond the scope of this book, there are
numerous transcendental constants known. Hermite was the first to prove in
1873 that e, the natural logarithm base, is a transcendental number. Cantor
later proved that almost all real numbers are transcendental.

With respect to continued fractions, the natural logarithm base *e*
can be represented by

e = [ 2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, ... ] .

While *phi* is a periodic continued fraction where the bn are all 1,
*e* has a recognizable pattern in bn. Knowing this regularity permits us
to compute *e* to any degree of precision. The continued fraction
converges to *e* to 10 decimal places in 15 steps (see below).

n | pn | qn | fn | e - fn |
---|---|---|---|---|

0 | 2 | 1 | 2.0000000000 | 0.7182818285 |

1 | 3 | 1 | 3.0000000000 | -0.2817181715 |

2 | 8 | 3 | 2.6666666667 | 0.0516151618 |

3 | 11 | 4 | 2.7500000000 | -0.0317181715 |

4 | 19 | 7 | 2.7142857143 | 0.0039961142 |

5 | 87 | 32 | 2.7187500000 | -0.0004681715 |

6 | 106 | 39 | 2.7179487179 | 0.0003331105 |

7 | 193 | 71 | 2.7183098592 | -0.0000280307 |

8 | 1264 | 465 | 2.7182795699 | 0.0000022586 |

9 | 1457 | 536 | 2.7182835821 | -0.0000017536 |

10 | 2721 | 1001 | 2.7182817183 | 0.0000001102 |

11 | 23225 | 8544 | 2.7182818352 | -0.0000000067 |

12 | 25946 | 9545 | 2.7182818229 | 0.0000000055 |

13 | 49171 | 18089 | 2.7182818287 | -0.0000000003 |

14 | 517656 | 190435 | 2.7182818284 | 0.0000000001 |

15 | 566827 | 208524 | 2.7182818285 | 0.0000000000 |

Unlike *phi* and *e*, the transcendental number *pi* cannot be
expressed in a general formula for bn. This fact leads us to ask "why" and I
regret that no satisfactory explanation exists. It does however suggest that
there are something like degrees of "transcendentalism", which can be
discerned through the lens of continued fractions. Under this method of
examination we might say that *pi* then is more transcendental than e.

Even though it cannot be expressed in closed form the representations for pi has been studied for many, many years. As a continued fraction its rate of convergence is quite fast. In fact,

pi = [ 3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, ... ]

can be computed to 10 decimal places of accuracy in just 7 iterations of
the forward recursion formula (see below).

n | pn | qn | fn | pi - fn |
---|---|---|---|---|

0 | 3 | 1 | 3.0000000000 | 0.1415926536 |

1 | 22 | 7 | 3.1428571429 | -0.0012644893 |

2 | 333 | 106 | 3.1415094340 | 0.0000832196 |

3 | 355 | 113 | 3.1415929204 | -0.0000002668 |

4 | 103993 | 33102 | 3.1415926530 | 0.0000000006 |

5 | 104348 | 33215 | 3.1415926539 | -0.0000000003 |

6 | 208341 | 66317 | 3.1415926535 | 0.0000000001 |

7 | 312689 | 99532 | 3.1415926536 | -0.0000000000 |

However, if we consider continued fractions more complex than simple
continued fractions, we can express *pi* in closed form. Certain
functions can be evaluated using continued. fractions, and the arctan is one
of these. Generally,

z z^2 4z^2 9z^2 16z^2 arctan z = --- ----- ------ ------ ------- . . . 1 + 3 + 5 + 7 + 11 +

4 pi = ----------------------------------- 1 1 + ------------------------------ 4 3 + ------------------------- 9 5 + -------------------- 16 7 + --------------- 25 9 + ---------- 11 + ...

Knowing a regular formula exists for *pi* compels one to conjecture if
there may exist transcendental numbers that cannot be expressed with a general
formula as ordered pairs (an, bn). It is possible to construct a number more
transcendental than pi; all we need is to make a continued fraction that
cannot be expressed in closed form under any circumstances. A simple example
I shall call the *h*, is defined by

3 h = 2 + --------------------------------------- 7 5 + ---------------------------------- 13 11 + ---------------------------- 19 17 + ---------------------- 29 23 + ---------------- 37 31 + ---------- 41 + ...

where each integral an and bn are successive prime numbers. Even using
just integers, using the continued fraction representation as a defining
characteristic, we must conclude that *h* is more trancendental than
*pi*. In fact, all such numbers defined in a similar manner would have a
degree of "transcendentalism" higher than pi.

Incidently, *h* = 2.53602 70816 89339 (approximately).

*© Copyright, 2000, 2003, 2014. All Rights Reserved.*
*Mark A. Herkommer*