Continued Fractions

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 

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 Fraction Expansions for Special Numbers

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).

Approximation of phi to its continued fraction expansion. phi is rounded in the 10th decimal place and is taken to be 1.61803 39887.

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).

Approximation of e to its continued fraction expansion. e is rounded in the 10th decimal place and is taken to be 2.7182818285.

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).

Approximation of pi to its continued fraction expansion. pi is rounded in the 10th decimal place and is taken to be 3.1415926536.

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