Regular Continued Fraction

A regular continued fraction is a simple continued fraction

where is an integer and is a positive integer for (Rockett and Szüsz 1992, p. 3).

While regular continued fractions are not the only possible representation of real numbers in terms of a sequence of integers (others include the decimal expansion and Engel expansion), they are a very common such representation that arises most frequently in number theory. Lochs' theorem relates the efficiency of a regular continued fraction expansion with that of a decimal expansion in representing a real number.

A finite regular continued fraction representation terminates after a finite number of terms and therefore corresponds to a rational number. (Bach and Shallit (1996) show how to compute the Jacobi symbol in terms of the simple continued fraction of a rational number .) On the other hand, an infinite regular continued fraction represents a unique irrational number, and each irrational number has a unique infinite regular continued fraction. Infinite periodic continued fractions have a number of special properties.

Regular 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 solar period to the lunar phase (synodic) period (365.2425/29.53059). Regular continued fractions can also be used to calculate gear ratios, and were used for this purpose by the ancient Greeks (Guy 1990).

Lagrange's continued fraction theorem states that a quadratic surd has an eventually periodic continued fraction. For example, the Pythagoras's constant has continued fraction [1; 2, 2, 2, 2, ...]. As a result, an exact representation for a numeric constant can sometimes be inferred if it is suspected to represent an unknown quadratic surd.

Regular continued fractions provide, in some sense, a series of "best" estimates for an irrational number. Functions can also be written as (simple or generalized) continued fractions, whose convergents provide rational approximations when the continued fraction converges. Continued fractions have also proved useful in the proof of certain properties of numbers such as e and (pi).

Starting the indexing of a regular continued fraction with ,

is the integer part of , where is the floor function. If is not an integer,

is the integer part of the reciprocal of . If this reciprocal is not an integer,

is the integer part of the reciprocal of the remainder, etc. Writing the complete quotients according to the recurrence relation

where and , gives the concise formula

The algorithm stops when is an integer, giving a finite regular continued fraction exactly when is a rational number. The quantities are called partial quotients, and the quantity obtained by including the first terms of the continued fraction for

is called the th convergent. For , . Here, and are the numerator and denominator of in lowest terms, with .

For an irrational number , the absolute error of its th convergent satisfies

where is the first neglected partial quotient (Gosper 1972, p. 38).

For example, consider the computation of the continued fraction of , given by .

Let the infinite regular continued fraction for be written . For almost every real number with respect to Lebesgue measure, the geometric mean of the partial quotients approaches Khinchin's constant

(OEIS A002210; Khintchine 1935, p. 376).

Similarly, taking the th root of the denominator of the th convergent as gives, for almost every real number with respect to Lebesgue measure, the Lévy constant

(OEIS A086702; Lévy 1936, p. 289).

For real numbers and , the logarithm can be computed by defining a nonnegative integer and such that

If , continue with

and so on, where , , ... are positive integers. Then

If a newly defined equals 1, stop and use the finite regular continued fraction obtained so far.

A geometric interpretation for a reduced fraction consists of a string through a lattice of points with ends at and (Klein 1896, 1932; Gardner 1984, pp. 210-211; Ball and Coxeter 1987, pp. 86-87; Davenport 1992; Steinhaus 1999, p. 40). 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.

Gosper (1972, pp. 39-41) described 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. 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 .