Other related concepts were once sharing that name,but the modern term refers almost exclusively to the following type of expressions(calledsimple and/orregular)which we illustrate with the most popular transcendental number: , theratio of the circumference of a circle to its diameter:
= 3 +
1
7 +
1
15 +
1
1 +
1
292 +
1
1 +
1
1 + ...
The ellipsis (...) indicates that the expression is to becontinued indefinitely.In the case of an irrational number like ,there is aninfinite sequence of so-calledpartial 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 positive integers.
The sequence of partial quotients is easy to obtain:At the top level, the number (here ) is seen to be the sum ofits firstpartial quotient and some expression which is clearly less than one,so thefirst partial quotient is simply the number's integral part (easy).Subtractthat from the number and you get a(nonnegative) fractional part less than one. Whenever it's not zero that fractional part has areciprocal which is a number greaterthan one. Apply the same procedure to this new number;the integral part is thesecond partial quotient,and the reciprocal of the remainder is the next numberon which to iterate the processWhen this remainder [or any of the susequent ones]turns out to be zero, the process terminatesand 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 fractionexpansion of a number isexamplified 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 andthelast 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 fromthetruncation 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 best rational approximations to a given real number.
The rational value whose [finite] continued fraction expansion is a truncation of thecontinued fraction expansion of a given number is called aconvergentof that number. (As stated above,proper truncation of a continued fraction entailsadding the last two terms whenever the last one is unity.)
Although agiven convergent may be worked out "from the bottom" in an obvious way,it is usually better to generate thesequence of convergents "from the top",computing each convergent in the form Pn/Qn, starting with:
P0 = a0, Q0 = 1 and P1 = a0 a1 + 1, Q1 = a1.
The following recurrence relation (due toEuler)may be shown to hold:
Pn
an Pn-1 + Pn-2
Qn
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 and 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 [: 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)
=
-(-1)n
Among other things, this shows that Pn and Qn arecoprime. So, Pn and Qn are fully determinedby 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 irreduciblerepresentations of two consecutive convergents and the value of the nextpartial quotient.
Our last identity also shows that the difference of two successive convergentsis a unit fraction (i.e., a fraction whose numerator is unity,also called an Egyptian fraction) and that the n-th convergentPn/Qn is within1/QnQn+1 of the entire continued fraction x.
Afamous result (1936)of Paul Lévy(1886-1971;X1904) is that,for almost all numbers x (in the sense discussedbelow) the limit of Qn1/n is equal to exp (2 / (12 ln 2) ). Therefore, for almost all x:
lim | x - Pn/Qn | 1/n = exp (2 / (6 ln 2) ) =
The successiveconvergents of a number happen to be the best possible rational approximations to that number in the following sense: Among all the fractions whose denominatorsare below some given quantity, the one fraction which is closest to yournumber isalways 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 are: (A002485 / A002486)
The bold ones are popular approximations which are especially interesting because they correspond to truncation beforea fairly large partial quotient (namely 15 or 292). This is the analog of a decimal expansionrounded 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 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.
On the other hand, 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 lessprecise than 355/113 and was thus never used as a rationalapproximation to . 333/106 was first shown to be a lower bound of around 1583, by Adriaan Anthoniszoon (1527-1607).
In 1766, Johann Heinrich Lambert (1728-1777) proved that is an irrational number: Byexpanding tg(h) as a continued fraction,he established that the tangent of a rational number is always irrational,so /4 can't possibly be rational because its tangent isthe rational number 1. Lambert gave a list of the first 27 convergents of . The first 25 of these are correct, but the last two are not. Unfortunately, the mistake has been overlooked by modern authors whoreproduced Lambert's list without properly warning their readers[Lambert's uncorrected list appears on page 171 ofBeckmann's popular "History of PI" (1971)]. For the record, here is an erratum for the convergents given by Lambert(who listed their reciprocals):
1.
3
/
1
2.
22
/
7
3.
333
/
106
4.
355
/
113
... ...
25.
8958937768937
/
2851718461558
26.
139755218526789
/
44485467702853
27.
428224593349304
/
136308121570117
Lambert used an erroneous list of partial quotients: [... 84, 2, 1, 1,37, 3 ...]. The correctexpansion 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 earlypartial quotient, which will suggest a very precise approximation.For example,Ramanujangave (2143/22)1/4 as an extremely close approximation to (it's about 265 times better than theexcellent 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 of4 , which is begging to be truncatedat its fifth term:
For some obscure reason, Ramanujan liked to give the above result in forms that may havesuggested some deeper reason for the approximation.Thesilliest of these is probably the followingdecimal pattern,using only the digits 0,1 and 2:
(102 - 2222/222 )1/22
Another example with the Euler-Mascheroni number (Euler's constant):
The number known to recreational mathematicians asChampernowne Constanthas a decimal expansion consisting of the successive digits of all the integers:0.123456789101112131415161718192021... It has aweird continued fractionexpansion, which is fairlydelicateto obtain:
is a 166-digit integer! Champernowne Constantis thus "almost" equal to 60499999499 / 490050000000. The two decimal expansions match for 186 digits after the decimal point. The first 185 decimals are:
0.1234567891011121314...899091929394959697
After that point, the fraction goes on ...99000102030405...whereasChampernowne 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 thesuccessive digits of all the primes (A033308,A030168). It's one of the few numbers that has been proven tobe decimal normal, which means that all strings of n digitsare equally likely in its decimal expansion (Copeland&Erdös, 1946).
The continued fraction expansion isn't known to benormal 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-knownthat almost all real numbers have those two properties!
(2001-11-19)
There is an attractive flavor of universality about continued fractions: Every number hasone and only one representation as a continued fraction(if we rule out unity as the last element ofa finite continued fraction of two or more elements). Therefore, people have looked for patterns in the continued fraction representationsof their favoriteconstants. No such pattern emerges for or ,but the continued fractions for some well-known numbers are worth noting...
The first entry in the table below (known as theGolden Number) isthe continued fraction with the slowest convergence (the lower the partial quotients,the slower the convergence). In this context, is seen as eitherthe "simplest" continued fraction,or as one of the "most irrational" numbers (the so-callednoble numbers).
Rational numbers correspond tofinite continued fractions.Continued fractions for which the sequence of partial quotients is ultimately periodicare calledperiodic continued fractions and they correspond toquadraticirrationals [also calledalgebraic 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 sequenceA003285 in theOnlineEncyclopedia of Integer Sequences for the lengths of the periods of the square rootsof the successive integers (by convention, a finite CFE has zero "period").
(2001-11-19)
For almost all numbers, there's no simple pattern to the sequence ofpartial quotients: The continued fraction representation creates a bijective relation between irrationalnumbers from 0 to 1 and infinite sequences of positive integers.The usual probability measure (Lebesgue measure) for sets of numbers between 0 and 1thus translates into statistical properties for their partial quotients, which wereinvestigated by the Russian mathematicianA.Ya. Khinchin (1894-1959).
For example, it may be shown that the set of all numbers whose partial quotients arebounded is of zero measure. In other words, foralmost all numbers, thesequence of partial quotients doesnot have an upper bound.In 1935, Khinchin published a remarkableresult stating, essentially, that a given integer k appears in the expansion ofalmost all real numbers with the following frequency:
In this, lg(x) is thebinary 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 ofthe probability that a partial quotient is equal to kor more, namely:
P(ak) = lg[1+1/k] = lg(k+1) - lg(k)
The problem is, of course, that there is usually no guarantee that a given numberis "typical". The numberappears to be "typical"(it probably is).However,all of the otherspecial numbers tabulatedabove are definitelynot.
The above probability distribution makes thearithmetic mean of partialquotients infinite. Thegeometric mean, however, is finite and was firstcomputed by Khinchin (who published only the firsttwo digits).It became known asKhinchin's Constant(also spelledKhintchine's Constant) :
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 ofgeometricaveraging. 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-exponentHölder mean,which is obtained by taking thearithmetic average of p-th powers and raising the result to the power of 1/p.The ordinaryarithmetic mean corresponds to p=1, thegeometric mean isthe (limiting) case p=0, theharmonic mean isp=-1, thequadratic 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, theharmonic 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 thatalmost all of them aretypical, in thesense that they seem to comply withKhinchin's Law. For example, theDelian constant is:
We once heard thatKhinchin's Law does not apply toall suchcubic irrationals and that some explicit counterexamples had been constructed... This may be anurban legend, pleasetell usif you know better...
Help from our readers (so far):
On 2002-10-23, "Giuseppe" told us about the real root(36001/30)of the polynomial x3 3600 x2 +120 x 2 (without asserting anything about it):
x =
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 ofHans Havermann,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 clarificationfrom a renowned expert:
There is no cubic irrational (nor any other algebraic number) whose continued fraction expansion can be proved to benormal[i.e.,actually obeyingKhinchin's Law].
On the other hand, I'd beextremely surprised if anyexperimental investigation of algebraic numbers of degree 3 (or more)ever revealed anything other than atypical behavior[an expansion whichappears to be normal in the long run,in spite of possible initial irregularities]. No "explicit counterexample" is known.
In particular, we don't believethat 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 y3 8y 10 (y = 3.3186282177501856591096801533...) :
(2001-11-19) 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 andexpand the result formally as a continued fraction... Keep in mind that all integers involved in the expansion must bepositiveintegers (with the possible exception of the leading one)so that a lot ofcase splitting is to be expected. Also, we'll see that something likeinfinite precision may be required tocompute the expansion of something as simple as the sum of two numbers given bytheir continued fraction expansions(in the form of algorithms that provide partial quotients on demand),so it can't be doneeffectively...
Simple Unary Operations
The simplest operations consist of taking theopposite (-x) or thereciprocal(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 theopposite 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 into8 distinct cases, which we won't spell out... For example:
Comparing two continued fractionsa andb 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 anand bn differ. Say an > bn :
If n iseven, thena >b.
If n isodd, thena <b.
When afinite continued fraction is involved, the above rule applies if wemake the convention that the "next" partial quotient on a terminated fractionwould actually be .
Note, however, that the case wherea andb are equalleads 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 nogeneral algorithmto compute something as simple asthe sum (or the product) of two continued fractions[technically, analgorithm is a procedure whichalways terminates]. That's because there are cases where the "next"partial quotientof a sum (or a product) of two continued fractions cannot be determinedwithout knowingall the partial quotients of both operands. This happens, in particular, when the sum (or the product) is rationalbut 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 resultbeyond a certain point.)
This theoretical obstacle does not prevent the design of usefulpracticalprocedures, 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 thecontinued fraction equivalents ofthe 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...
(2014-09-10) (René Baire ) The set of all infinite sequences of positive integers, endowed with theTychonoff topology.
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 homeomorphism (i.e., itself and its inverse are continuous functions) between thetwo relevants sets, endowed with their respective most natural topologies.
The interval [0,1] is a metric space with respect to the ordinary Euclidean distance. The irrational points simply form a subspace of that.
On the other hand, the Baire space is a cartesian productof 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 theTychonoff topology (which differ from the naive so-called box topology when there are infinitely many cartesian components).
Proof : A bijectionis an homeomorphism iff it transforms some particular topological basis of one spaceinto a topological basis of the other. In the case at hand, consider (open) sets of the following types:
In the Baire space, the sequences whosefirst 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 formsa topological basis of its own space, which is left as an exercise for the reader.
(2001-11-19) May a function be expanded as a continued fraction?
At least thespirit of continued fractions may be used to find rationalapproximations [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 thatnotall functions may be expanded in this way.Even among analytic functions, it may be required to raise the variableh to some power [other than unity] at some, or all, of its occurrences on theright-hand side of the above identity.This happens whenever there is a corresponding gap [zero coefficient(s)] at thesame 'stage' in theTaylor expansion of the function.(In particular, iff is aneven function,h always appears raised to someeven power.)
It's straightforward to obtain the sequence of coefficients (an ):
an =fn(0), wherefn isrecursively defined as follows:
f0(h) =f(h)
fn+1(h) =hk /[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 matchthat of the truncated rational expression up to --and including-- theorder mof the last coefficient a which is retained.In practice, to compute the above coefficients up toa,we may replace an analytic functionf(h)by its partial Taylor expansion up to --and including--the term or orderh.
Here are a few "nice" sequences of coefficients corresponding to such Padé expansions. The general formulas given may not apply to the first coefficients (in which case, these areunderscored ):
f(h)
a0
a1
a2
a3
a4
a5
a6
a7
a8
a9
a2n
a2n+1
exp(h)
1
1
-2
-3
2
5
-2
-7
2
9
2(-1)n
(2n+1)(-1)n
ln(1+h)
0
1
2
3
1
5
2/3
7
1/2
9
4/(2n)
2n+1
[1+(1+4h/a2)]a/2
a
a
a
a
a
a
a
a
a
a
a
a
h / th(h)
1
3
5
7
9
11
13
15
17
19
4n+1
4n+3
h / tg(h)
1
-3
5
-7
9
-11
13
-15
17
-19
4n+1
-(4n+3)
The contrived form of the last two tabulated entries is meant to squeeze the "natural"expansion of functions with odd parity(liketh=tanh ortg=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 givethe "natural" expansions of such functions in a formsimilar to the following expression forArctg=arctan:
Arctg(h) =
h
1 +
h2
-3 +
h2
-5/9 +
h2
-63/4 +
h2
-4/25 +
h2
-2475/64 + ...
For an odd functionf like this one,we may use an indexing consistentwith the numbering of the "regular" expansion ofh /f(h), so that we have:
Recall that, for a positive integer k, the double-factorial notation k!! is used todenote the product of all positive integersofthe same parity as k which are less than or equal to it.Therefore, (2n+1)!! is (2n+1)!/(2n)!!, whereas (2n)!! is 2nn!.
References
Milton Abramowitz, Irene A. Stegun "Handbook of Mathematical Functions" (originally NBS #55, 1964) Republished (1965-1972) Dover Publications ISBN 0-486-61272-4
Aleksandr YakovlevichKhinchin(1894-1959) [also spelledKhintchine] "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) A unique nondecreasing sequence of positive integers.
A positive number x can be uniquely associated with a nondecreasingsequence of positive integer (ai ) as follows.
x =
1
1 +
1
1 +
1
1 +
1
...
a1
a2
a3
a4
This is known as an Engel expansion (or Engel series ) in honor ofFriedrich Engel(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 outthe sequence consisting of infinitely many "1", which maybe 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 a-1. If such finite expansions are accepted, we must rule out Engel expansions that areultimately constant. 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:
There is a very simple algorithm which yields the Engel expansion of a positivenumber x. It may be expressed by the following recurrence (which halts, for rational numbers, when xn vanishes).
x1 = x an = ceiling ( 1/xn) xn+1 = an xn 1
In this, ceiling (y) is the smallest integer greater than or equal to y.
(2008-04-23) A unique (strictly) increasing sequence of positive integers.
x =
1
1
1
1
1
1
1
...
a1
a2
a3
a4
This is known as a Pierce expansion (or Pierce series ) because of the ground-breakingthree-page articleon the subject, which was published in December 1929 by T.A. Pierce.
A Few Remarkable Pierce Expansions (= sets of positive integers)
There is a very simple algorithm which yields the Pierce expansion of anumber 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 = 1an xn
In this, floor (y) is the largest integer less than or equal to y. For example, we may obtain the Pierce expansion of 1/ (A006283) namely:
1
=
1
1
1
1
1
1
1
...
3
22
118
383
As with ordinary continued fractions, it seems that the Pierce expansionsof 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 betweenthe 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 samecardinality; the power of the continuum :
C =
0
Also, Pierce expansions provide a straight one-to-one correspondence betweenthe rational numbers between 0 and 1 and theset of finite sets of positive integers (thereby establishing that the latter set is countable).
(2018-12-01) The algorithm of Asmus L. Schmidt is based on Gaussian integers.
