The Continued Fraction Procedure

Let $x\in\mathbb{R}$ and write

$$x = a_0 + t_0$$

with $a_0\in\mathbb{Z}$ and $0\leq t_0 < 1$ . We call the number $a_0$ the floor of $x$ , and we also sometimes write $a_0 = \lfloor x \rfloor$ . If $t_0\neq 0$ , write

$$\frac{1}{t_0} = a_1 + t_1$$

with $a_1\in\mathbb{N}$ and $0\leq t_1 < 1$ . Thus $t_0 = \frac{1}{a_1 + t_1}=[0,a_1+t_1]$ , which is a (non-simple) continued fraction expansion of $t_0$ . Continue in this manner so long as $t_n\neq 0$ writing

$$\frac{1}{t_n} = a_{n+1} + t_{n+1}$$

with $a_{n+1}\in\mathbb{N}$ and $0\leq t_{n+1}<1$ . We call this procedure, which associates to a real number $x$ the sequence of integers $a_0, a_1, a_2, \ldots$ , the continued fraction process.

Example 5.2   Let $x=\frac{8}{3}$ . Then $x=2+\frac{2}{3}$ , so $a_0=2$ and $t_0=\frac{2}{3}$ . Then $\frac{1}{t_0}=\frac{3}{2} = 1+\frac{1}{2}$ , so $a_1=1$ and $t_1=\frac{1}{2}$ . Then $\frac{1}{t_1} = 2$ , so $a_2=2$ , $t_2=0$ , and the sequence terminates. Notice that

$$\frac{8}{3} = [2,1,2],$$

so the continued fraction procedure produces the continued fraction of $\frac{8}{3}$ .

Example 5.2   Let $x = \frac{1+\sqrt{5}}{2}.$ Then

$$x = 1 + \frac{-1 + \sqrt{5}}{2},$$

so $a_0 = 1$ and $t_0 = \frac{-1+\sqrt{5}}{2}$ . We have

$$\frac{1}{t_0} = \frac{2}{-1+\sqrt{5}} = \frac{-2-2\sqrt{5}}{-4} = \frac{1+\sqrt{5}}{2}$$

so again $a_1=1$ and $t_1 = \frac{-1+\sqrt{5}}{2}$ . Likewise, $a_n = 1$ for all $n$ . As we will see below, the following exciting equality makes sense.

$$\frac{1+\sqrt{5}}{2} = 1 + \frac{1}{\displaystyle 1 + \frac{1}{\... ...laystyle 1 + \frac{1}{\displaystyle 1 + \frac{1}{\displaystyle 1 + \cdots}}}}}$$

SAGE Example 5.2   The equality of Example 5.2.2 is consistent with the following SAGE calculation:

sage: def cf(bits):
...   x = (1 + sqrt(RealField(bits)(5))) / 2
...   return continued_fraction(x)
sage: cf(10)
[1, 1, 1, 1, 1, 1, 1, 3]
sage: cf(30) 
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2]
sage: cf(50) 
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Example 5.2   Suppose $x = e = 2.71828182\ldots$ . Using the continued fraction procedure, we find that

$$a_0, a_1, a_2, \ldots = 2,1,2,1,1,4,1,1,6,1,1,8,1,1,10,\ldots$$

For example, $a_0=2$ is the floor of $2$ . Subtracting $2$ and inverting, we obtain $1/0.718\ldots = 1.3922\ldots$ , so $a_1=1$ . Subtracting $1$ and inverting yields $1/0.3922\ldots = 2.5496\ldots$ , so $a_2=2$ . We will prove in Section 5.3 that the continued fraction of $e$ obeys a simple pattern.

The $5$ th partial convergent of the continued fraction of $e$ is

$$[a_0,a_1,a_2,a_3,a_4,a_5] = \frac{87}{32} = 2.71875,$$

which is a good rational approximation to $e$ , in the sense that

$$\left\vert\frac{87}{32} - e\right\vert = 0.000468\ldots.$$

Note that $0.000468\ldots < 1/32^2 = 0.000976\ldots$ , which illustrates the bound in Corollary 5.2.11 below.

Let's do the same thing with $\pi=3.14159265358979\ldots$ : Applying the continued fraction procedure, we find that the continued fraction of $\pi$ is

$$a_0, a_1, a_2, \ldots = 3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14,\ldots$$

The first few partial convergents are

$$3, \frac{22}{7}, \frac{333}{106}, \frac{355}{113}, \frac{103993}{33102}, \cdots$$

These are good rational approximations to $\pi$ ; for example,

$$\frac{103993}{33102} = 3.14159265301\ldots.$$

Notice that the continued fraction of $e$ exhibits a nice pattern (see Section 5.3 for a proof), whereas the continued fraction of $\pi$ exhibits no pattern that is obvious to the author. The continued fraction of $\pi$ has been extensively studied, and over 20 million terms have been computed. The data suggests that every integers appears infinitely often as a partial convergent. For much more about the continued fraction of $\pi$ or of any other sequence in this book, type the first few terms of the sequence into [#!sloane!#].