Other related concepts were once sharing that name,
but the modern term refers almost exclusively to the following type of expressions
(called simple and/or regular)
which we illustrate with the most popular transcendental number:
ratio of the circumference of a circle to its diameter:
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, ...
With the possible exception of the first one,
all of these are 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.
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.
(2001-11-19) The Convergents of a Real Number
The best rational approximations to a given real number.
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 Pn/Qn, starting with:
P0 = a0, Q0 = 1
P1 = a0 a1 + 1, Q1 = a1.
The following recurrence relation (due to Euler)
may be shown to hold:
an Pn-1 + Pn-2
an Qn-1 + Qn-2
For programming and other purposes, the above recurrence is best started at
n = 0 (rather than
n = 2) by introducing the following conventions:
P-2 = 0, Q-2 = 1
P-1 = 1, Q-1 = 0
Well, we jumped the gun...
It would have been more proper to write the above recurrence as two distinct relations,
formally equating the numerators and the denominators separately.
This pair of equalities could then be used to establish the following relations
[HINT: Multiply the numerators by Qn-1
and subtract from each the matching denominator multiplied by Pn-1
to obtain the first equation below,
which is a recurrence relation that may be used to prove the second equality.]
PnQn-1 - QnPn-1
-(Pn-1Qn-2 - Qn-1Pn-2 )
Among other things, this shows that Pn and Qn
So, Pn and Qn are fully determined
by their ratio.
Thus, Euler's recurrence does give directly the
irreducible representation of the sequence of convergents.
It is unambiguous, after all...
It can be viewed as a method to obtain the next convergent from the irreducible
representations of two consecutive convergents and the value of the next
Our last identity also shows that the difference of two successive convergents
is a unit fraction (i.e., a fraction whose numerator is unity,
also called an Egyptian fraction)
and that the n-th convergent Pn/Qn is within
1/QnQn+1 of the entire continued fraction x.
A famous result (1936)
of Paul Lévy
(1886-1971; X1904) is that,
for almost all numbers x
(in the sense discussed below)
the limit of Qn1/n is equal to
exp (p2 / (12 ln 2) ).
Therefore, 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:
(A002485 / A002486)
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 was thus never used 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):
2851718461558 [correctly given by Lambert]
Lambert used an erroneous list of partial quotients:
[... 84, 2, 1, 1, 37, 3 ...].
expansion reads [... 84, 2, 1, 1, 15, 3, 13, 1, 4, 2, 6, 6, 99, ...].
(2001-11-19) Precise Approximations from Some Continued Fractions
Occasionally, a continued fraction expansion (CFE) may show a very large early
partial quotient, which will suggest a very precise approximation.
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
p4 , which is begging to be truncated
at its fifth term:
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:
1 - Ö(320/1835)
» g =
The number known to recreational mathematicians as Champernowne Constant
has a decimal expansion consisting of the successive digits of all the integers:
It has a weird continued fraction
expansion, which is fairly
A18 is a 166-digit integer!
is thus "almost" equal to 60499999499 / 490050000000.
The two decimal expansions match for 186 digits after the decimal point.
The first 185 decimals are:
After that point, the fraction goes on ...99000102030405...
whereas Champernowne Constant reads, of course, ...9899100101102103...
At the other end of the spectrum, so to speak, is the related
Copeland-Erdös constant, whose decimal expansion consists of the
successive digits of all the primes
It's one of the few numbers that has been proven to
be decimal normal, which means that all strings of n digits
are equally likely in its decimal expansion (Copeland & Erdös, 1946).
The continued fraction expansion isn't known to be normal but it probably is.
To the best of my knowledge, not a single number has yet be shown to have
both a normal decimal expansion and
a normal continued fraction expansion (although it's well-known
that almost all real numbers have those two properties!
(2001-11-19) Regular Patterns for Some Irrational Numbers
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 (known as the
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
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
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").
(2001-11-19) The Normal Distribution of Partial Quotients
For almost all numbers, there's no simple pattern to the sequence of
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:
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
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:
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, the Delian constant is:
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
if you know better...
Help from our readers (so far):
On 2002-10-23, "Giuseppe" told us about the real root
of the polynomial
x3 -3600 x2 +120 x -2 (without asserting anything about it):
In spite of the initial weirdness of its CFE,
this cubic irrational doesn't look like a proper counterexample
(according to a 2003-02-06 email of
the geometric mean of the 1000000 terms following 3599 is about 2.6850).
The problem is still wide open.
We've also received the following clarification
from a renowned expert:
There is no cubic irrational (nor any other algebraic number) whose
continued fraction expansion can be proved to be normal
[i.e., actually obeying Khinchin's Law].
On the other hand, I'd be extremely surprised if any
experimental investigation of algebraic numbers of degree 3 (or more)
ever revealed anything other than a typical behavior
[an expansion which appears to be normal in the long run,
in spite of possible initial irregularities].
No "explicit counterexample" is known.
In particular, we don't believe
that such a counterexample could be the number x Giuseppe quotes,
which is one of those discussed by Stark
and tested in my paper with Brent and te Riele,
along with the real zero of
- 8y - 10
(y = 3.31862821775...) :
Robert M. Corless:
Fractions and Chaos", American Mathematical Monthly 99 (1992),
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:
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.
MR 98c:11144 Enrico Bombieri, Alfred J. van der Poorten:
"Continued Fractions of Algebraic Numbers"
How are arithmetic operations performed on continued fractions?
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.
Either a1 is 1 or isn't:
For negative numbers, we take the reciprocal of the opposite
[which is positive]
and obtain the result as the opposite of that.
This translates into
8 distinct cases, which we won't spell out... For example:
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 an
and bn differ. Say an > bn :
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 +¥.
Note, however, that the case where a and b are equal
leads to a nonterminating procedure:
If both numbers are given, as they may,
via general algorithms that give partial quotients on demand,
then you'd have to keep querying both algorithms forever
(because of the possibility that they may end up giving different results).
A similar remark applies to other binary operations,
with far-reaching theoretical consequences...
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...
The preferred convention is to define the Baire space as consisting of
sequences of nonnegative integers.
The other convention, used here, is only convenient in the context of continued fractions.
The continued fraction expansion of any irrational
number in [0,1] is an element of the Baire Space.
We already know that this relation is bijective.
What may be more suprising is that our bijection is an
(i.e., itself and its inverse are continuous functions) between the
two relevants sets, endowed with their respective most natural topologies.
On the other hand, the Baire space is a cartesian product
of a countable infinity of copies of the set of positive integers
(one such copy for each index in the sequence).
The natural topology on a cartesian product is the
(which differ from the naive so-called box topology
when there are infinitely many cartesian components).
Proof : A bijection
is an homeomorphism iff it transforms some particular
topological basis of one space
into a topological basis of the other.
In the case at hand, consider (open) sets of the following types:
In the Baire space, the sequences whose
first n terms are prescribed.
The set of irrationals whose first n partial quotients are prescribed.
Clearly, our bijection transforms a set of one type into a set of the other type.
So, we only have to check that each family forms
a topological basis of its own space, which is left as an exercise for the reader.
May a function be expanded as a continued fraction?
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:
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 (an ):
an = fn(0), where fn is
recursively defined as follows:
f0(h) = f(h)
[ fn(h) - an ]
( hk appears in the result at that stage)
k is whatever value makes fn+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
we may replace an analytic function f(h)
by its partial Taylor expansion up to --and including--
the term or order hm.
Such rational approximations
(i.e., consisting of the ratio of two polynomials) are called
Padé approximants, especially in the
popular case when the degree of the denominator is equal to the degree
of the numerator (or doesn't exceed it by more than one unit).
Curiously, Padé approximants are often better approximation to the
original function than the truncated Taylor expansions on which they are based.
The above sequence of Padé approximants may even converge
quite rapidly when the Taylor series itself diverges!
Here are a few "nice" sequences of coefficients corresponding to such
The general formulas given may not apply to the first coefficients
(in which case, these are underscored ):
Öh / th(Öh)
Öh / tg(Öh)
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:
-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:
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 2nn!.
Milton Abramowitz, Irene A. Stegun
"Handbook of Mathematical Functions" (originally NBS #55, 1964)
Republished (1965-1972) Dover Publications ISBN 0-486-61272-4
(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
(2008-04-19) Engel expansion of a positive number (1913)
A unique nondecreasing sequence of positive integers.
A positive number x can be uniquely associated with a nondecreasing
sequence of positive integer (ai ) as follows.
This is known as an Engel expansion (or
Engel series ) in honor of
(1861-1941) who first investigated this in 1913.
The correspondence so defined between positive numbers and
nondecreasing sequences of positive integers
is a bijective one, if we rule out
the sequence consisting of infinitely many "1", which may
be conventionally associated with ¥.
For a constant Engel series,
x = (1/a) (1+x). This yields x = 1/(a-1).
More generally, an Engel series which is ultimately constant
(i.e., ending with infinitely many terms equal to a > 1 )
can be replaced by a finite expansion ending with
If such finite expansions are accepted, we must rule out Engel expansions that are
Alternately, we may simply rule out finite expansions.
Either approach preserves unicity.
This special case (finite and/or ultimately constant, according to taste)
correspond clearly to rational numbers.
Conversely, the expansion of any rational number is of this type.
(This can be proved by studying the algorithm given below.)
An Engel expansion is often denoted by a sequence between curly brackets:
(2008-04-23) Pierce expansion of a positive number below 1 (1929)
A unique (strictly) increasing sequence of positive integers.
This is known as a Pierce expansion (or
Pierce series )
because of the ground-breaking three-page article
on the subject, which was published in December 1929
by T.A. Pierce.
Dr. T.A. Pierce was appointed instructor at the University of Nebraska in 1917.
He was promoted assistant professor in 1920 and associate professor in 1926.
Pierce became a full professor of mathematics at the University of Nebraska in 1929
and eventually achieved emeritus status there. He died on
August 18, 1945.
A Few Remarkable Pierce Expansions (= sets of positive integers)
There is a very simple algorithm which yields the Pierce expansion of a
number x between 0 and 1.
It may be expressed by the following recurrence
(which halts, for rational numbers, when xn vanishes).
x1 = x
an = floor ( 1/xn )
xn+1 = 1 - an xn
In this, floor (y) is the largest integer
less than or equal to y.
For example, we may obtain the Pierce expansion of
As with ordinary continued fractions, it seems that the Pierce expansions
of algebraic numbers of degree 3 or more
(between 0 and 1) are not "special" in any statistical way...
Here's the Pierce expansion of the cube root of ½ :
Incidentally, Pierce expansions provide a straight one-to-one correspondence between
the continuum of the real numbers between 0 and 1 and the
powerset of the positive integers
(i.e., all sets of positive integers).
This is one direct way to show that those two have the same
the power of the continuum :
C = 2
Also, Pierce expansions provide a straight one-to-one correspondence between
the rational numbers between 0 and 1 and the
set of finite sets of positive integers
(thereby establishing that the latter set is countable).