Continued Fraction

A "general" continued fraction representation of a real number is one of the form

(1)

where , , ... and , are integers. Such representations are sometimes written in the form

(2)

for compactness.

Wallis first used the term "continued fraction" in his Arithmetica infinitorum of 1653 (Havil 2003, p. 93), although other sources list the publication date as 1655 or 1656. An archaic word for a continued fraction is anthyphairetic ratio.

While continued fractions are not the only possible representation of real numbers in terms of a sequence of integers (others include the decimal expansion and the so-called Engel expansion), they are a very common such representation that arises most frequently in number theory.

The simple continued fraction representation (which is usually what is meant when the term "continued fraction" is used without qualification) of a number is given by

(3)

where , , , ... are again integers and . Simple continued fractions can be written in a compact abbreviated notation as

(4)

Some care is needed, since some authors begin indexing the terms at instead of , causing the parity of certain fundamental results in continued fraction theory to be reversed. The first terms of the simple continued fraction of a number can be computed in the Wolfram Language using the command ContinuedFraction[x, n].

Continued fractions with closed forms are given in the following table (cf. Euler 1775).

continued fraction	value	approximate	Sloane
		0.697774...	A052119
		1.541494...	A113011
		0.581976...	A073333
		1.525135...	A111129

Starting the indexing of a continued fraction with ,

(5)

is the integer part of , where is the floor function,

(6)

is the integral part of the reciprocal of ,

(7)

is the integral part of the reciprocal of the remainder, etc. Writing the remainders according to the recurrence relation

			(8)
			(9)

gives the concise formula

(10)

The quantities are called partial quotients, and the quantity obtained by including terms of the continued fraction

			(11)
			(12)
			(13)

is called the th convergent. For example, consider the computation of the continued fraction of , given by .

term	value	PQs	convergent	value
			3	3.00000
				3.14286
				3.14151

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). Because quadratic surds have periodic continued fractions (e.g., Pythagoras's constant has continued fraction [1, 2, 2, 2, 2, ...]), an exact representation for a tabulated numerical value can sometimes be found if it is suspected to represent an unknown quadratic surd.

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

Let the continued fraction for be written . Then the limiting value is almost always Khinchin's constant

(14)

(OEIS A002210).

Similarly, taking the th root of the denominator of the th convergent as almost always gives the Lévy constant

(15)

(OEIS A086702).

Let be convergents of a nonsimple continued fraction. Then

	(16)
	(17)

and subsequent terms are calculated from the recurrence relations

	(18)
	(19)

for , 2, ..., . It is also true that

(20)

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 , in which case it should be added to the previous term (Gosper 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

(21)

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

(22)

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:

(23)

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 of a simple continued fraction, and define

(24)

(25)

(26)

Then subsequent terms can be calculated from the recurrence relations

(27)

(28)

The continued fraction fundamental recurrence relation for simple continued fractions is

(29)

It is also true that if ,

			(30)
			(31)

Furthermore,

(32)

Also, if a convergent , then

(33)

Similarly, if , then and

(34)

The convergents also satisfy

			(35)
			(36)

Plotted above on semilog scales are ( even; left figure) and ( odd; right figure) as a function of for the convergents of . In general, the even convergents of an infinite simple continued fraction for a number form an increasing sequence, and the odd convergents form a decreasing sequence (so any even convergent is less than any odd convergent). Summarizing,

(37)

(38)

Furthermore, each convergent for 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 ,

(39)

The square root of a squarefree integer has a periodic continued fraction of the form

(40)

(Rose 1994, p. 130). Furthermore, if is not a square number, then the terms of the continued fraction of satisfy

(41)

Logarithms can be computed by defining , ... and the positive integer , ... such that

(42)

(43)

and so on. Then

(44)

A geometric interpretation for a reduced fraction consists of a string through a lattice of points with ends at and (Klein 1896, 1932; Steinhaus 1999, p. 40; Gardner 1984, pp. 210-211, 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 give alternate convergents , while the other convergents are obtained from the pegs it presses against with the initial end at . The above plot is for , which has convergents 0, 1, 2/3, 3/4, 5/7, ....

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

(45)

then it is equal to the continued fraction

(46)

(Borwein et al. 2004, p. 30).

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 polyhedron vertices of a cube. Although this algorithm has not appeared in print, similar algorithms have been constructed by Vuillemin (1987) and Liardet and Stambul (1998).

Gosper's algorithm for computing the continued fraction for from the continued fraction for is described by Gosper (1972), Knuth (1998, Exercise 4.5.3.15, pp. 360 and 601), and Fowler (1999). (In line 9 of Knuth's solution, should be replaced by .) Gosper (1972) and Knuth (1981) also mention the bivariate case .

Wolfram Web Resources