Continued Fraction

A ``general'' continued fraction representation of a Real Number $x$ is of the form

$$x=a_0+{\strut\displaystyle b_1\over{\strut\displaystyle a_1+... ...strut\displaystyle b_3\over\strut\displaystyle a_3+\ldots}}}},$$ (1)

which can be written

$$x=a_0 +{b_1\over a_1+} {b_2\over a_2+} \cdots.$$ (2)

The Simple Continued Fraction representation of $x$ (which is usually what is meant when the term ``continued fraction'' is used without qualification) of a number is given by

$$x = a_0+{1\over{\strut\displaystyle a_1+{\strut\displaystyle... ...{\strut\displaystyle 1\over\strut\displaystyle a_3+\ldots}}}},$$ (3)

which can be written in a compact abbreviated Notation as

$$x=[a_0, a_1, a_2, a_3, \ldots].$$ (4)

Here,

$$a_0=\left\lfloor{x}\right\rfloor$$ (5)

is the integral part of $x$ (where $\left\lfloor{x}\right\rfloor$ is the Floor Function),

$$a_1=\left\lfloor{1\over x-a_0}\right\rfloor$$ (6)

is the integral part of the Reciprocal of $x-a_0$, $a_2$ is the integral part of the reciprocal of the remainder, etc. The quantities $a_i$ are called Partial Quotients. An archaic word for a continued fraction is Anthyphairetic Ratio.

Continued fractions provide, in some sense, a series of ``best'' estimates for an Irrational Number. Functions can also be written as continued fractions, providing a series of better and better rational approximations. Continued fractions have also proved useful in the proof of certain properties of numbers such as e and $\pi$ (Pi). Because irrationals which are square roots of Rational Numbers have periodic continued fractions, an exact representation for a tabulated numerical value (i.e., 1.414... for Pythagoras's Constant, $\sqrt{2}$) can sometimes be found.

Continued fractions are also useful for finding near commensurabilities between events with different periods. For example, the Metonic cycle used for calendrical purposes by the Greeks consists of 235 lunar months which very nearly equal 19 solar years, and 235/19 is the sixth Convergent of the ratio of the lunar phase (synodic) period and solar period (365.2425/29.53059). Continued fractions can also be used to calculate gear ratios, and were used for this purpose by the ancient Greeks (Guy 1990).

If only the first few terms of a continued fraction are kept, the result is called a Convergent. Let $P_n/Q_n$ be convergents of a nonsimple continued fraction. Then

$$P_{-1}\equiv 1\qquad Q_{-1}\equiv 0$$ (7)

$$P_0 \equiv b_0\qquad Q_0\equiv 1$$ (8)

and subsequent terms are calculated from the Recurrence Relations

$$P_j=b_jP_{j-1}+a_jP_{j-2}$$ (9)

$$Q_j=b_jQ_{j-1}+a_jQ_{j-2}$$ (10)

for $j=1$, 2, ..., $n$. It is also true that

$$P_nQ_{n-1}-P_{n-1}Q_n=(-1)^{n-1}\prod_{k=1}^n a_k.$$ (11)

The error in approximating a number by a given Convergent is roughly the Multiplicative Inverse of the square of the Denominator of the first neglected term.

A finite simple continued fraction representation terminates after a finite number of terms. To ``round'' a continued fraction, truncate the last term unless it is $\pm 1$, in which case it should be added to the previous term (Beeler et al. 1972, Item 101A). To take one over a continued fraction, add (or possibly delete) an initial 0 term. To negate, take the Negative of all terms, optionally using the identity

$$[-a, -b, -c, -d, \ldots]=[-a-1, 1, b-1, c, d, \ldots].$$ (12)

A particularly beautiful identity involving the terms of the continued fraction is

$${[a_0, a_1, \ldots, a_n]\over[a_0, a_1, \ldots, a_{n-1}]} =... ... a_{n-1}, \ldots, a_1, a_0]\over [a_n, a_{n-1}, \ldots, a_1]}.$$ (13)

Finite simple fractions represent rational numbers and all rational numbers are represented by finite continued fractions. There are two possible representations for a finite simple fraction:

$$[a_0, \ldots, a_n]=\cases{ [a_0, \ldots, a_{n-1}, a_n-1, 1] &... ...a_n>1$\cr [a_0, \ldots, a_{n-2}, a_{n-1}+1] & for $a_n=1$.\cr}$$ (14)

On the other hand, an infinite simple fraction represents a unique Irrational Number, and each Irrational Number has a unique infinite continued fraction.

Consider the Convergents $p_n/q_n$ of a simple continued fraction, and define

$$p_{-2}\equiv 0\qquad q_{-2}\equiv 1$$ (15)

$$p_{-1} \equiv 1\qquad q_{-1}\equiv 0$$ (16)

$$p_0\equiv a_0\qquad q_0\equiv 1.$$ (17)

Then subsequent terms can be calculated from the Recurrence Relations

$$p_i=a_ip_{i-1}+p_{i-2}$$ (18)

$$q_i=a_iq_{i-1}+q_{i-2}.$$ (19)

The Continued Fraction Fundamental Recurrence Relation for simple continued fractions is

$$p_nq_{n-1}-p_{n-1}q_n=(-1)^n.$$ (20)

It is also true that if $a_0\not=0$,

$${p_n\over p_{n-1}} = [a_n, a_{n-1}, \ldots, a_1, a_0]$$ (21)

$${q_n\over q_{n-1}} = [a_n, \ldots, a_1].$$ (22)

Furthermore,

$${p_n\over q_n}={p_{n+1}-p_{n-1}\over q_{n+1}-q_{n-1}}.$$ (23)

Also, if a convergent $c_n=p_n/q_n>1$, then

$${q_n\over p_n}=[0, a_0, a_1, \ldots, a_n].$$ (24)

Similarly, if $p_n/q_n<1$, then

$${q_n\over p_n}=[a_0, a_1, \ldots, a_n].$$ (25)

The convergents $c_n=p_n/q_n$ also satisfy

$$c_n-c_{n-1} = {(-1)^{n+1}\over q_nq_{n-1}}$$ (26)

$$c_n-c_{n-2} = {a_n(-1)^n\over q_nq_{n-2}}.$$ (27)

The Even convergents $c_{2n+1}$ of an infinite simple continued fraction form an Increasing Sequence, and the Odd convergents $c_{2n}$ form a Decreasing Sequence (so any Even convergent is less than any Odd convergent). Summarizing,

$$c_{2n}<\cdots<c_6<c_4<c_2\cdots<c_1<c_3<c_5<\cdots<c_{2n+1}<\cdots.$$ (28)

Furthermore, each convergent for $n\geq 3$ lies between the two preceding ones. Each convergent is nearer to the value of the infinite continued fraction than the previous one. In addition, for a number $x=[a_0,a_1,\dots]$,

$${1\over(a_{n+1}+2){q_n}^2} < \left\vert{x-{p_n\over q_n}}\right\vert < {1\over a_{n+1}{q_n}^2}.$$ (29)

The Square Root of a Squarefree Integer has a periodic continued fraction of the form

$$\sqrt{n}=[a_0, \overline{a_1, \ldots, a_n, 2a_0}\,]$$ (30)

(Rose 1994, p. 130). Furthermore, if $D$ is not a Square Number, then the terms of the continued fraction of $\sqrt{D}$ satisfy

$$0<a_n<2\sqrt{D}.$$ (31)

In particular,

$\quad [\overline{a}] = {a+\sqrt{a^2+4}\over 2}$	(32)
$\quad [1, \overline{a}] = {-1+\sqrt{1+4a}\over 2}$	(33)
$\quad [a,\overline{2a}\,] = \sqrt{a^2+1}$	(34)
$\quad [\overline{a, b}] = {ab+\sqrt{ab(ab+4)}\over 2b}$	(35)

$$[\overline{a_1, \ldots, a_n}]= {-(q_{n-1}-p_n)+\sqrt{(q_{n-1}-p_n)^2+4q_np_{n-1}}\over 2q_n}$$ (36)

$${[}a_0, \overline{b_1, \ldots, b_n}] = a_0+{1\over [\overline{b_1, \ldots, b_n}]}$$ (37)

$${[}\overline{b_1, \ldots, b_n}] = {[\overline{b_1, \ldots, b_n}] p_n+p_{n-1}\over [\overline{b_1, \ldots, b_n}] q_n+q_{n-1}}.$$ (38)

The first follows from

$$\alpha = n+{1\over n+{\strut\displaystyle 1\over\strut\displaystyle n+{\strut 1\over\strut\displaystyle n+\ldots}}}$$

$$= n+{\strut\displaystyle 1\over\strut\displaystyle n+\left({\strut 1 \over{\strut\displaystyle n+{1\over\strut\displaystyle n+\ldots}}}\right)}.$$ (39)

Therefore,

$$\alpha-n= {1\over\strut\displaystyle n+{\strut 1\over\strut\displaystyle n+{\strut 1\over\strut\displaystyle n+\ldots}}},$$ (40)

so plugging (40) into (39) gives

$$\alpha=n+{1\over n+(\alpha- n)} = n+{1\over \alpha}.$$ (41)

Expanding

$$\alpha^2-n\alpha-1=0,$$ (42)

and solving using the Quadratic Formula gives

$$\alpha={n+\sqrt{n^2+4}\over 2}.$$ (43)

The analog of this treatment in the general case gives

$$\alpha={\alpha p_n+p_{n-1}\over \alpha q_n+q_{n-1}}.$$ (44)

The following table gives the repeating simple continued fractions for the square roots of the first few integers (excluding the trivial Square Numbers).

$N$	$\alpha_{\sqrt{N}}$	$N$	$\alpha_{\sqrt{N}}$
2	$[1, \overline{2}]$	22	$[4, \overline{1, 2, 4, 2, 1, 8}]$
3	$[1, \overline{1, 2}]$	23	$[4, \overline{1, 3, 1, 8}]$
5	$[2, \overline{4}]$	24	$[4, \overline{1, 8}]$
6	$[2, \overline{2, 4}]$	26	$[5, \overline{10}]$
7	$[2, \overline{1, 1, 1, 4}]$	27	$[5, \overline{5, 10}]$
8	$[2, \overline{1, 4}]$	28	$[5, \overline{3, 2, 3, 10}]$
10	$[3, \overline{6}]$	29	$[5, \overline{2, 1, 1, 2, 10}]$
11	$[3, \overline{3, 6}]$	30	$[5, \overline{2, 10}]$
12	$[3, \overline{2, 6}]$	31	$[5, \overline{1, 1, 3, 5, 3, 1, 1, 10}]$
13	$[3, \overline{1, 1, 1, 1, 6}]$	32	$[5, \overline{1, 1, 1, 10}]$
14	$[3, \overline{1, 2, 1, 6}]$	33	$[5, \overline{1, 2, 1, 10}]$
15	$[3, \overline{1, 6}]$	34	$[5, \overline{1, 4, 1, 10}]$
17	$[4, \overline{8}]$	35	$[5, \overline{1, 10}]$
18	$[4, \overline{4, 8}]$	37	$[6, \overline{12}]$
19	$[4, \overline{2, 1, 3, 1, 2, 8}]$	38	$[6, \overline{6, 12}]$
20	$[4, \overline{2, 8}]$	39	$[6, \overline{4, 12}]$
21	$[4, \overline{1, 1, 2, 1, 1, 8}]$	40	$[6, \overline{3, 12}]$

The periods of the continued fractions of the square roots of the first few nonsquare integers 2, 3, 5, 6, 7, 8, 10, 11, 12, 13, ... (Sloane's A000037) are 1, 2, 1, 2, 4, 2, 1, 2, 2, 5, ... (Sloane's A013943; Williams 1981, Jacobson et al. 1995). An upper bound for the length is roughly ${\mathcal O}(\ln D \sqrt{D}\,)$.

An even stronger result is that a continued fraction is periodic Iff it is a Root of a quadratic Polynomial. Calling the portion of a number $x$ remaining after a given convergent the ``tail,'' it must be true that the relationship between the number $x$ and terms in its tail is of the form

$$x={ax+b\over cd+d},$$ (45)

which can only lead to a Quadratic Equation.

Logarithms $\log_{b_0} b_1$ can be computed by defining $b_2$, ...and the Positive Integer $n_1$, ...such that

$${b_1}^{n_1} < b_0 < {b_1}^{n_1+1} \qquad b_2={b_0\over {b_1}^{n_1}}$$ (46)

$${b_2}^{n_2} < b_1 < {b_2}^{n_2+1} \qquad b_3={b_1\over {b_2}^{n_2}}$$ (47)

and so on. Then

$$\log_{b_0} b_1 = [n_1, n_2, n_3, \ldots].$$ (48)

A geometric interpretation for a reduced Fraction $y/x$ consists of a string through a Lattice of points with ends at $(1,0)$ and $(x,y)$ (Klein 1907, 1932; Steinhaus 1983; Ball and Coxeter 1987, pp. 86-87; Davenport 1992). This interpretation is closely related to a similar one for the Greatest Common Divisor. The pegs it presses against $(x_i, y_i)$ give alternate Convergents $y_i/x_i$, while the other Convergents are obtained from the pegs it presses against with the initial end at $(0,1)$. The above plot is for $e-2$, which has convergents 0, 1, 2/3, 3/4, 5/7, ....

Let the continued fraction for $x$ be written $[a_0,a_1,a_2,\ldots,a_n]$. Then the limiting value is almost always Khintchine's Constant

$$K\equiv \lim_{n\to\infty} (a_1a_2\cdots a_n)^{1/n} = 2.68545\ldots.$$ (49)

Continued fractions can be used to express the Positive Roots of any Polynomial equation. Continued fractions can also be used to solve linear Diophantine Equations and the Pell Equation. Euler showed that if a Convergent Series can be written in the form

$$c_1+c_1c_2+c_1c_2c_3+\ldots,$$ (50)

then it is equal to the continued fraction

$${c_1\over\strut\displaystyle 1-{\strut\displaystyle c_2\over... ...trut\displaystyle c_3\over\strut\displaystyle 1+c_3-\ldots}}}.$$ (51)

Gosper has invented an Algorithm for performing analytic Addition, Subtraction, Multiplication, and Division using continued fractions. It requires keeping track of eight Integers which are conceptually arranged at the Vertices of a Cube. The Algorithm has not, however, appeared in print (Gosper 1996).

An algorithm for computing the continued fraction for $(ax+b)/(cx+d)$ from the continued fraction for $x$ is given by Beeler et al. (1972, Item 101), Knuth (1981, Exercise 4.5.3.15, pp. 360 and 601), and Fowler (1991). (In line 9 of Knuth's solution, $X_k\leftarrow \left\lfloor{A/C}\right\rfloor$ should be replaced by $X_k\leftarrow \min(\left\lfloor{A/C}\right\rfloor ,\left\lfloor{(A+B)/(C+D)}\right\rfloor )$.) Beeler et al. (1972) and Knuth (1981) also mention the bivariate case $(axy+bx+cy+d)/(Axy+Bx+Cy+D)$.

See also Gaussian Brackets, Hurwitz's Irrational Number Theorem, Khintchine's Constant, Lagrange's Continued Fraction Theorem, Lamé's Theorem, Lévy Constant, Padé Approximant, Partial Quotient, Pi, Quadratic Irrational Number, Quotient-Difference Algorithm, Segre's Theorem

References

Continued Fractions

Abramowitz, M. and Stegun, C. A. (Eds.). Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th printing. New York: Dover, p. 19, 1972.

Acton, F. S. ``Power Series, Continued Fractions, and Rational Approximations.'' Ch. 11 in Numerical Methods That Work, 2nd printing. Washington, DC: Math. Assoc. Amer., 1990.

Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 54-57 and 86-87, 1987.

Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, pp. 36-44, Feb. 1972.

Beskin, N. M. Fascinating Fractions. Moscow: Mir Publishers, 1980.

Brezinski, C. History of Continued Fractions and Padé Approximants. New York: Springer-Verlag, 1980.

Conway, J. H. and Guy, R. K. ``Continued Fractions.'' In The Book of Numbers. New York: Springer-Verlag, pp. 176-179, 1996.

Courant, R. and Robbins, H. ``Continued Fractions. Diophantine Equations.'' §2.4 in Supplement to Ch. 1 in What is Mathematics?: An Elementary Approach to Ideas and Methods, 2nd ed. Oxford, England: Oxford University Press, pp. 49-51, 1996.

Davenport, H. §IV.12 in The Higher Arithmetic: An Introduction to the Theory of Numbers, 6th ed. New York: Cambridge University Press, 1992.

Euler, L. Introduction to Analysis of the Infinite, Book I. New York: Springer-Verlag, 1980.

Fowler, D. H. The Mathematics of Plato's Academy. Oxford, England: Oxford University Press, 1991.

Guy, R. K. ``Continued Fractions'' §F20 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, p. 259, 1994.

Jacobson, M. J. Jr.; Lukes, R. F.; and Williams, H. C. ``An Investigation of Bounds for the Regulator of Quadratic Fields.'' Experiment. Math. 4, 211-225, 1995.

Khinchin, A. Ya. Continued Fractions. New York: Dover, 1997.

Kimberling, C. ``Continued Fractions.'' http://cedar.evansville.edu/~ck6/integer/contfr.html.

Klein, F. Ausgewählte Kapitel der Zahlentheorie. Germany: Teubner, 1907.

Klein, F. Elementary Number Theory. New York, p. 44, 1932.

Kline, M. Mathematical Thought from Ancient to Modern Times. New York: Oxford University Press, 1972.

Knuth, D. E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 2nd ed. Reading, MA: Addison-Wesley, p. 316, 1981.

Moore, C. D. An Introduction to Continued Fractions. Washington, DC: National Council of Teachers of Mathematics, 1964.

Olds, C. D. Continued Fractions. New York: Random House, 1963.

Pettofrezzo, A. J. and Bykrit, D. R. Elements of Number Theory. Englewood Cliffs, NJ: Prentice-Hall, 1970.

Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. ``Evaluation of Continued Fractions.'' §5.2 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 163-167, 1992.

Rose, H. E. A Course in Number Theory, 2nd ed. Oxford, England: Oxford University Press, 1994.

Rosen, K. H. Elementary Number Theory and Its Applications. New York: Addison-Wesley, 1980.

Sloane, N. J. A. Sequences A013943 and A000037/M0613 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

Steinhaus, H. Mathematical Snapshots, 3rd American ed. New York: Oxford University Press, pp. 39-42, 1983.

Van Tuyl, A. L. ``Continued Fractions.'' http://www.calvin.edu/academic/math/confrac/.

Wagon, S. ``Continued Fractions.'' §8.5 in Mathematica in Action. New York: W. H. Freeman, pp. 263-271, 1991.

Wall, H. S. Analytic Theory of Continued Fractions. New York: Chelsea, 1948.

Williams, H. C. ``A Numerical Investigation into the Length of the Period of the Continued Fraction Expansion of $\sqrt{D}$.'' Math. Comp. 36, 593-601, 1981.