Other related concepts were once packaged under that name, but the modern term refers almost exclusively to the following type of expressions (called simple and/or regular) which may be illustrated using the most popular transcendental number of them all, p, the ratio of the circumference of a circle to its diameter:

p   =   3 +	1
	7 +	1
		15 +	1
			1 +	1
				292 +	1
					1 +	1
						1 + ...

The ellipsis (...) indicates that the expression is to be continued indefinitely. In the case of an irrational number like p, there is an infinite sequence of so-called partial quotients: 3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, ...A001203.  With the possible exception of the first one, all of these are always positive integers.

The sequence of partial quotients is easy to obtain: At the top level, the number (here p) is seen to be the sum of its first partial quotient and some expression which is clearly less than one, so the first partial quotient is simply the number's integral part (easy). Subtract that from the number and you get a (nonnegative) fractional part less than one.  Whenever it's not zero that fractional part has a reciprocal which is a number greater than one. Apply the same procedure to this new number; the integral part is the second partial quotient, and the reciprocal of the remainder is the next number on which to iterate the process When this remainder [or any of the susequent ones] turns out to be zero, the process terminates and the expression on the right hand side is finite.  This happens when the original number is rational, otherwise the procedure goes on forever...

The compact notation used for the continued fraction expansion of a number is examplified by the following.  Note the semicolon after the first quotient [a reminder that it may not be positive] and the ellipsis to indicate incompleteness.

p = [3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, 1, 84, 2, 1, 1 ...]

If the above procedure is used with a rational number, the expansion is finite and the last partial quotient cannot be unity (or else we should have added one unit to the previous quotient). However, finite expansions ending with 1 are routinely obtained from the truncation of a larger (possibly infinite) expansion. For example, [3; 7, 15, 1, 292, 1] is a truncation of the above, which is equal to the proper continued fraction [3; 7, 15, 1, 293], or 104348/33215.

The rational value whose [finite] continued fraction expansion is a truncation of the continued fraction expansion of a given number is called a convergent of that number.  (As stated above, proper truncation of a continued fraction entails adding the last two terms whenever the last one is unity.)

Although a given convergent may be worked out "from the bottom" in an obvious way, it is usually better to generate the sequence of convergents "from the top", computing each convergent in the form P_n/Q_n, starting with P₀=a₀, Q₀=1, P₁=a₀a₁+1, Q₁=a₁. The following recurrence relation (due to Euler) may be shown to hold. For programming and other purposes, it may be convenient to start the process at n=0, rather than n=2, by introducing the conventional values P_-1=1, Q_-1=0, P_-2=0, Q_-2=1 :

Pn		an Pn-1  +  Pn-2
Qn		an Qn-1 +  Qn-2

We jumped the gun... It would have been more proper to write the above as two relations; formally equating the numerators and the denominators separately. This pair of equalities could then be used to establish the following relations. [To do so, multiply the numerators by Q_n-1 and subtract from each the matching denominator multiplied by P_n-1. This gives the first relation below, which turns out to be a recurrence relation that may be used to prove the second equality.]

Among other things, this shows that P_n and Q_n are always relatively prime. Therefore, the above recursive method gives directly the irreducible representation of the sequence of convergents. With this in mind, P_n and Q_n are both perfectly well defined from the sole knowledge of their ratio. The "practical" (sloppy) way we used to give Euler's recurrence relations turns out to be unambiguous, after all... It can be interpreted as a method to obtain the next convergent from the irreducible representations of two consecutive convergents and the value of the next partial quotient.

Our last identity also shows that the difference of two successive convergents is a unit [or Egyptian] fraction (a fraction whose numerator is unity) and that the n-th convergent P_n/Q_n is within 1/Q_nQ_n+1 of the entire continued fraction x.  Since a famous result, due to Lévy, states that for almost all numbers x, in the sense discussed below, the limit of  Q_n^1/n  is  exp(p² / (12 ln(2)) ),  we have:

lim   | x - P_n/Q_n | ^1/n   =   exp(-p² / (6 ln(2)) )       [for almost all x]

The successive convergents of a number happen to be the best possible rational approximations to that number in the following sense: Among all the fractions whose denominators are below some given quantity, the one fraction which is closest to your number is always one of its convergents. The successive convergents are alternately approximations from below (the crudest of which is the integral part) and approximations from above. For example the successive convergents of p are:

The bold ones are popular approximations which are especially interesting because they correspond to truncation before a fairly large partial quotient (namely 15 or 292). This is the analog of a decimal expansion rounded just before a 9 or a 0 (or even a string of 9s or 0s). The value 22/7 was found to be an upper bound of p by Archimedes (c.287 BC - 212 BC). Because 292 is unusually large as a partial quotient, 355/113 is an excellent approximation (7 correct digits and a relative error of only +85 ppb).  It was discovered by the Chinese mathematician Zu Chongzhi (429-500) but remained unknown in the West until the 16th century.  Conversely, 333/106 is a fairly lousy record breaker (considering that 106 is not much smaller than 113) because it corresponds to the worst kind of truncation (that which preceeds a "1" in the expansion); it's about 312 times less precise than 355/113 and, therefore, remains unused as a rational approximation to p  (333/106 was first shown to be a lower bound of p by Adriaan Anthoniszoon, around 1583).

In 1766, Johann Heinrich Lambert (1728-1777) proved that p is an irrational number:  By expanding tg(h) as a continued fraction, he established that the tangent of a rational number is always irrational, so p/4 can't possibly be rational because its tangent is the rational number 1.  Lambert gave a list of the first 27 convergents of p.  The first 25 of these are correct, but the last two are not.  Unfortunately, the mistake has been overlooked by modern authors who reproduced Lambert's list without properly warning their readers [Lambert's uncorrected list appears on page 171 of Beckmann's popular "History of PI" (1971)].  For the record, here is an erratum for the convergents given by Lambert (who listed their reciprocals):

Lambert used an erroneous list of partial quotients: [... 84, 2, 1, 1, 37, 3 ...]. The correct expansion reads [... 84, 2, 1, 1, 15, 3, 13, 1, 4, 2, 6, 6, 99, ...].

Occasionally, a continued fraction expansion (CFE) may show a very large early partial quotient, which will suggest a very precise approximation. For example, Ramanujan gave (2143/22)^1/4 as an extremely close approximation to p (it's about 265 times better than the excellent 355/113, with an accuracy better than one third of a ppb). The astonishing precision of such a simple formula is made obvious by the CFE of p⁴ , which is begging to be truncated at its fifth term:

p⁴   =   [97; 2, 2, 3, 1, 16539, 1, 6, 7, 6, 8, 6, 3, 9, 1, 1, 1, 18, 1 ...]

For some obscure reason, Ramanujan liked to give the above result in forms that may have suggested some deeper reason for the approximation. The silliest of these is probably the following decimal pattern, using only the digits 0,1 and 2:

p   »   (102 - 2222/22² )^1/22

A similar example involves Euler's constant, the Euler-Mascheroni number (g):

( 1 - g ) ²   =   [0; 5, 1, 1, 2, 6, 1, 8, 372792, 35, 52, 8, 1, 4, 1, 2, 9, 1 ...]

Thus,   1 - Ö(320/1835)   »   g   =   0.57721566490153286060651209...

The number known to recreational mathematicians as Champernowne Constant has a decimal expansion consisting of the successive digits of all the integers: 0.123456789101112131415161718192021...  It has a weird continued fraction expansion, which is fairly delicate to obtain:

[0; 8, 9, 1, 149083, 1, 1, 1, 4, 1, 1, 1, 3, 4, 1, 1, 1, 15, A18, 6, 1, 1, 21, 1 ...]

A18 is a 166 digit integer!  Champernowne Constant is thus "almost" equal to 60499999499 / 490050000000:  The two decimal expansions match for the part corresponding to the integers 0 to 97, (0.123456...899091929394959697) after which point the fraction goes on 99000102030405... whereas Champernowne Constant reads, of course, 9899100101102103...

There is an attractive flavor of universality about continued fractions:  Every number has one and only one representation as a continued fraction (if we rule out unity as the last element of a finite continued fraction of two or more elements). Therefore, people have looked for patterns in the continued fraction representations of their favorite constants. No such pattern emerges for p or g, but the continued fractions for some well-known numbers are worth noting...

The first entry in the table below (the so-called Golden Number) is the continued fraction with the slowest convergence (the lower the partial quotients, the slower the convergence).  In this context, f is seen as either the "simplest" continued fraction, or as one of the "most irrational" numbers (the so-called noble numbers).

Rational numbers correspond to finite continued fractions. Continued fractions for which the sequence of partial quotients is ultimately periodic are called periodic continued fractions and they correspond to quadratic irrationals [also called algebraic numbers of degree 2, these are irrational roots of polynomials of degree 2 with integral coefficients]. The first few entries in the above table are examples of periodic continued fractions. See sequence A003285 in the Online Encyclopedia of Integer Sequences for the lengths of the periods of the square roots of the successive integers (by convention, a finite CFE has zero "period").

For almost all numbers, there's no simple pattern to the sequence of partial quotients:  The continued fraction representation creates a bijective relation between irrational numbers from 0 to 1 and infinite sequences of positive integers. The usual probability measure (Lebesgue measure) for sets of numbers between 0 and 1 thus translates into statistical properties for their partial quotients, which were investigated by the Russian mathematician A.Ya. Khinchin (1894-1959).

For example, it may be shown that the set of all numbers whose partial quotients are bounded is of zero measure. In other words, for almost all numbers, the sequence of partial quotients does not have an upper bound. In 1935, Khinchin published a remarkable result stating, essentially, that a given integer k appears in the expansion of almost all real numbers with the following frequency:

P(a=k)   =   lg[1+1/(k² + 2k)]   =   -lg(k) + 2 lg(k+1) - lg(k+2)

In this, lg(x) is the binary logarithm  ln(x)/ln(2). Numerically, this means that, in the expansion of a "typical" number, the partial quotient will be "1" about 41.5% of the time, "2" 17%, "3" 9.31%, "4" 5.89%, "5" 4.064%, etc. Khinchin's law may also be stated by giving the (simpler) expression of the probability that a partial quotient is equal to k or more, namely:

P(a≥k)   =   lg[1+1/k]   =   lg(k+1) - lg(k)

The problem is, of course, that there is usually no guarantee that a given number is "typical". The number p appears to be "typical" (it probably is). However, all of the other special numbers tabulated above are definitely not.

The above probability distribution makes the arithmetic mean of partial quotients infinite. The geometric mean, however, is finite and was first computed by Khinchin (who published only the first two digits). It became known as Khinchin's Constant (also spelled Khintchine's Constant) :

¥ Õ k = 1

ì î

1 +

1 k(k+2)

ülg (k) þ

=   2.68545200106530644531-

As Khinchin himself was quick to point out, any other choice of convergent method could be used instead of geometric averaging. So, in the larger scheme of things, there is nothing really special about the above "average" partial quotient. Indeed, we may consider the so-called p-exponent Hölder mean, which is obtained by taking the arithmetic average of p-th powers and raising the result to the power of 1/p. The ordinary arithmetic mean corresponds to p=1, the geometric mean is the (limiting) case p=0, the harmonic mean is p=-1, the quadratic mean is p=2, etc. In the case of partial quotients under the Khinchin law, we may thus obtain as "average" any value greater than 1, by adjusting our choice of the exponent p accordingly (disallowing values of p greater than or equal to 1, which give infinite results). For example, the harmonic mean of typical partial quotients is:

1.74540566240734686349+

Whereas quadratic irrationals (algebraic numbers of degree 2) have a periodic CFE, algebraic numbers of degree 3 or more are entirely different and it appears that almost all of them are typical, in the sense that they seem to comply with Khinchin's Law.  For example:

2^1/3  =   [ 1; 3, 1, 5, 1, 1, 4, 1, 1, 8, 1, 14, 1, 10, 2, 1, 4, 12, 2, 3, 2, 1, 3, 4, 1, 1, 2, 14, 3, 12, 1, 15, 3, 1, 4, 534, 1, 1, 5, 1, 1, 121, 1, 2, 2, 4, 10, 3, 2, 2, 41, 1, 1, 1, 3, 7, 2, 2, 9, 4, 1, 3, 7, 6, 1, 1, 2, 2, 9, 3, 1, 1, 69, 4, 4, 5, 12, 1, 1, 5, 15, 1, 4, 1, 1, 1, 1, 1, 89, 1, 22, 186, 6, 2, 3, 1, 3, 2, 1, 1, 5, 1 ...]   A002945

We once heard that Khinchin's Law does not apply to all such cubic irrationals and that some explicit counterexamples had been constructed...  This may be an urban legend, please tell us if you know better...

Help from our readers (so far):

On 2002-10-23, "Giuseppe" told us about the real root (»3600-1/30) of the polynomial   x³ -3600 x² +120 x -2  (without asserting anything about it):

x   =   [3599; 1, 28, 1, 7198, 1, 29, 388787400, 23, 1, 8998, 1, 13, 1, 10284, 1, 2, 25400776804, 1, 1, 3, 4, 93, 3, 1, 2, 11, 1, 9, 1, 99, 1, 3, 1, 3, 9, 1, 603118914 ...]

Robert M. Corless: "Continued Fractions and Chaos", American Mathematical Monthly 99 (1992), pages 203-215.  MR 94g:58135  
Harold M. Stark: "An explanation of some exotic continued fractions found by Brillhart", in A.O.L. Atkin & B.J. Birch (ed.), Computers in Number Theory (Proc. Science Research Council Atlas Symposium #2, Oxford), pages 21-35. Academic Press, 1971.  MR 49 #2570  
R.P. Brent, Alfred J. van der Poorten, Herman J.J. te Riele: "A Comparative Study of Algorithms for Computing Continued Fractions of Algebraic Numbers"   Algorithmic number theory (Talence, 1996), pages 35-47, Lecture Notes in Computer Science, 1122, Springer, Berlin, 1996.  (PostScript)  MR 98c:11144

Well, it's not so easy. Basically, you perform the operations formally on the values of the continued fractions and expand the result formally as a continued fraction...  Keep in mind that all integers involved in the expansion must be positive integers (with the possible exception of the leading one) so that a lot of case splitting is to be expected.  Also, we'll see that something like infinite precision may be required to compute the expansion of something as simple as the sum of two numbers given by their continued fraction expansions (in the form of algorithms that provide partial quotients on demand), so it can't be done effectively...

Because Khinchin's Law applies to the continued fraction expansion (CFE) of almost all numbers, it's interesting to remark that the output of these things will obey Khinchin's Law if the input does (the most trivial way this can happen is when almost all partial quotients of the output are straight copies from an input sequence).

Simple Unary Operations

The simplest operations consist of taking the opposite (-x) or the reciprocal (1/x) of a number x. With continued fractions, the latter would be simpler than the former (in fact, it would be trivial) if we did not have to contend with negative numbers... So, let's deal with the opposite of x first. There are just two cases; either a₁ is 1 (A) or it's not (B):

1. - [a₀;  1, a₂, a₃, a₄, ...] = [(-a₀-1); (a₂+1), a₃, a₄, ...]
2. - [a₀; a₁, a₂, a₃, a₄, ...] = [(-a₀-1); 1, (a₁-1), a₂, a₃, a₄, ...]   If a₁¹1.

Computing the reciprocal of a CFE is easy for positive numbers (cases A or B below). For negative numbers, we take the reciprocal of the opposite [which is easily dealt with, since it's positive] and obtain the result as the opposite of that (this would translate into 8 other separate cases, if we had to spell them out).

1. 1 / [0;  a₁, a₂, a₃, a₄, ...] = [a₁; a₂, a₃, a₄, ...]
2. 1 / [a₀; a₁, a₂, a₃, a₄, ...] = [0; a₀; a₁, a₂, a₃, a₄, ...]   If a₀>0.

Binary Operations

Comparing two continued fractions a and b is always easy: If all corresponding partial quotients are equal, the numbers are equal. Otherwise, just consider the first rank n for which the partial quotients a_n and b_n differ. Say a_n > b_n :

• If n is even, then a > b.
• If n is odd,  then a < b.

When a finite continued fraction is involved, the above rule applies if we make the convention that the "next" partial quotient on a terminated fraction would actually be +¥.

In particular, this shows that there's no general algorithm to compute something as simple as the sum (or the product) of two continued fractions [technically, an algorithm is a procedure which always terminates].  That's because there are cases where the "next" partial quotient of a sum (or a product) of two continued fractions cannot be determined without knowing all the partial quotients of both operands.  This happens, in particular, when the sum (or the product) is rational but neither operand is...  (If both operands are given as computer programs that give partial quotients upon request, it's possible that you'll have to keep querying such programs forever, without ever being able to determine the partial quotients of the result beyond a certain point.)

This theoretical obstacle does not prevent the design of useful practical procedures, but it simply means that they can't be foolproof and/or fully automated (just like automated floating-point arithmetic isn't foolproof).  For example, we may have to live with the continued fraction equivalents of the notorious rounding errors of limited-precision positional arithmetic, and occasionally accept that a "very large" partial quotient may stand for an infinite one (indicative of a rational result) without ever being sure...

HAKMEM on Continued Fraction Arithmetic and longer paper by Bill Gosper.

At least the spirit of continued fractions may be used to find rational approximations [quotients of polynomials] to analytic functions...
A simple starting point is an expression like this:

f(h)   =   a0 +	h
	a1 +	h
		a2 +	h
			a3 +	h
				a4 +	h
					a5 +	h
						a6 + ...

One complication, which does not exist in the case of real numbers, is that not all functions may be expanded in this way. Even among analytic functions, it may be required to raise the variable h to some power [other than unity] at some, or all, of its occurrences on the right-hand side of the above identity. This happens whenever there is a corresponding gap [zero coefficient(s)] at the same 'stage' in the Taylor expansion of the function. (In particular, if f is an even function, h always appears raised to some even power.)

It's straightforward to obtain the sequence of coefficients (a_n ):

• a_n = f_n(0), where f_n is recursively defined as follows:
• f₀(h) = f(h)
• f_n+1(h) = h^k / [ f_n(h) - a_n ]   ( h^k appears in the result at that stage)
  k is whatever value makes  f_n+1(0) finite and nonzero. Usually k=1.

With these coefficients, the Taylor expansion of  f will match that of the truncated rational expression up to --and including-- the order m of the last coefficient am which is retained. In practice, to compute the above coefficients up to am, we may replace an analytic function f(h) by its partial Taylor expansion up to --and including-- the term or order h^m.

Here are a few "nice" sequences of coefficients corresponding to such expansions. The general formulas given may not apply to the first coefficients (in which case, these are underscored ):

The contrived form of the last two tabulated entries is meant to squeeze the "natural" expansion of functions with odd parity (like th=tanh or tg=tan) into our restricted "regular" framework (where squares or higher powers of h don't appear). Were it not for the tabulation and/or the typography, it would have been better to give the "natural" expansions of such functions in a form similar to the following expression for Arctg=arctan:

Arctg(h)   =	h
	1 +	h2
		-3 +	h2
			-5/9 +	h2
				-63/4 +	h2
					-4/25 +	h2
						-2475/64 + ...

For an odd function f  like this one, we may use an indexing consistent with the numbering of the "regular" expansion of Öh / f(Öh), so that we have:

where   un =

2n+1 22n

ì2n î n

ü þ

=

(2n+1)!! (2n)!!

Recall that, for a positive integer k, the "double-factorial" notation k!! is used to denote the product of all positive integers of the same parity as k which are less than or equal to it. Therefore, (2n+1)!! is (2n+1)!/(2n)!!, whereas (2n)!! is 2ⁿn!.

References

1. Milton Abramowitz, Irene A. Stegun
   "Handbook of Mathematical Functions" (originally NBS #55, 1964)
   Republished (1965-1972) Dover Publications   ISBN 0-486-61272-4
2. Petr Beckmann
   "A History of PI"   (© 1971 by The Golem Press)
   Republished (1993) by Barnes & Nobles   ISBN 0-88029-418-3
3. Aleksandr Yakovlevich Khinchin (1894-1959) [also spelled Khintchine]
   "Continued Fractions" 1964 translation of 3rd Russian edition (1961)
   Monograph first published by Khinchin in 1935 (second edition in 1949). Republished (1997) by Dover Publications, Inc. ISBN 0-486-69630-8
4. C. Stanley Ogilvy
   "Tomorrow's Math : Unsolved Problems for the Amateur" ©1962-72
   Oxford University Press (Second Edition, 1972), New York.