home | index | units | counting | geometry | algebra | trigonometry & functions | calculus
analysis | sets & logic | number theory | recreational | misc | nomenclature & history | physics

Final Answers
© 2000-2014   Gérard P. Michon, Ph.D.

Continued Fractions


 border
 border  border
 border
 border
 border
 border

On this site, see also :

Related Links (Outside this Site)

An Introduction to Continued Fractions by Ron Knott (University of Surrey)
Continued Fractions by Adam Van Tuyl of Lakehead University.
Secret Life of Continued Fractions by John D. Barrow of Cambridge University.
Pianos and Continued Fractions by Edward G. Dunne (AMS)
Generalized Continued Fractions by Domingo Gómez Morín.
Continued Fractions by Alexander Bogomolny at cut-the-knot.com.
Families of Continued Fractions by Justin T. Miller of the University of Arizona.
Contfrac calculator (WIMS, University of Nice)  |  Les-Mathématiques.net
 
border
border

Numbers and Functions as Continued Fractions


(2001-11-19)   What is a continued fraction?

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:  p,  the ratio of the circumference of a circle to its diameter:

   p   =   3 +  1
Vinculum
7 +  1
pi Vinculum
15 +  1
Vinculum
1 +  1
Vinculum
292 +  1
Vinculum
1 +  1
Vinculum
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  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.


(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       and       P1 = a0 a1 + 1,   Q1 = a1.

The following recurrence relation (due to Euler) may be shown to hold:

 Leonhard Euler
Pn
=
aPn-1  +  Pn-2
vinculum vinculum
Qn
=
aQn-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  [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 )
  =  -(-1)n

Among other things, this shows that  Pn  and  Qn  are coprime.  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 partial quotient.

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:

lim   | x - Pn/Qn | 1/n   =   exp (-p2 / (6 ln 2) )   =   0.093187822953575873362328...

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)

3,22 / 7,333 / 106,355 / 113, 103993 / 33102,104348 / 33215,etc.
p   =   + 1 / 7 - 1 / 742 + 1 / 11978  - 1 / 3740526 + 1 / 1099482930 etc.

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

1.3  /  1
2.22  /  7
3.333  /  106
4.355  /  113
... ...
25.8958937768937  /   2851718461558   [correctly given by Lambert]
26.139755218526789  /   44485467702853
27.  428224593349304  /   136308121570117

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, ...].


(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. 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:

p4   =   [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

Another example with the Euler-Mascheroni number  g  (Euler's constant):

( 1 - g ) 2   =   [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 186 digits after the decimal point.  The first 185 decimals are:

0.1234567891011121314...899091929394959697

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  (A033308, A030168).  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).

0.2357111317192329313741434753596167717379838997101103107109...
[ 0;4,4,8,16,18,5,1,1,1,1,7,1,1,6,2,9,58,1,3,4,2,2,1,1,2,1,4,39,4,4,5,2,1,1,87... ]

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

f = ½ (1+Ö5) [1; 1, 1, 1, 1, 1, 1, 1, 1, ...
½ [k+Ö(k2+4)] [k; k, k, k, k, k, k, k, k, ...
Ö2 [1; 2, 2, 2, 2, 2, 2, 2, 2, ...
Ö3 [1; 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, ...
Ö5 [2; 4, 4, 4, 4, 4, 4, 4, 4, ...
Ö7 [2; 1, 1, 1, 4, 1, 1, 1, 4, 1, 1, 1, 4, 1, 1, 1, 4, ...
Ö41 [6; 2, 2, 12, 2, 2, 12, 2, 2, 12, 2, 2, 12, ...
e = exp(1) [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, 1, ... 2n+2, 1, 1, ...
Öe = exp(1/2) [1; 1, 1, 1, 5, 1, 1, 9, 1, 1, 13, 1, 1, 17, 1, 1, ... 4n+1, 1, 1, ...
exp(1/3) [1; 2, 1, 1, 8, 1, 1, 14, 1, 1, 20, 1, 1, 26, 1, 1, ... 6n+2, 1, 1 ...
exp(1/k) [1; k-1, 1, 1, 3k-1, 1, 1, 5k-1, 1, 1, 7k-1, ... (2n+1)k-1, 1, 1 ...
e 2 = exp(2) [7; 2, 1, 1, 3, 18, 5, 1, 1, 6, ... 12n+6, 3n+2, 1, 1, 3n+3 ...
exp(2/3) [1; 1, 18, 7, 1, 1, 10, ... 36n+18, 9n+7, 1, 1, 9n+10 ...
exp(2/5) [1; 2, 30, 12, 1, 1, 17, ... 60n+30, 15n+12, 1, 1, 15n+17 ...
exp(2/7) [1; 3, 42, 17, 1, 1, 24, ... 84n+42, 21n+17, 1, 1, 21n+24 ...
exp(2/(2k+1)) [1; k, ... (24k+12)n+12k+6,  (6k+3)n+5k+2,  1,  1,  (6k+3)n+7k+3 ...
th(1) = (e2-1)/(e2+1) [0; 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, ... (2n+1) ...
th(1/k) [0; k, 3k, 5k, 7k, 9k, 11k, 13k, 15k, 17k, 19k, ... (2n+1)k ...
tg(1) = tan(1) [1; 1, 1, 3, 1, 5, 1, 7, 1, 9, 1, 11, 1, 13, 1, 15, 1, ... 2n+1, 1, ...
tg(1/2) = tan(1/2) [0; 1, 1, 4, 1, 8, 1, 12, 1, 16, 1, 20, 1, 24, 1, 28, 1, ... 4n, 1, ...
tg(1/k) = tan(1/k) [0; k-1, 1, 3k-2, 1, 5k-2, 1, 7k-2, 1, ... (2n+1)k-2,1, ...
I1 (2) / I0 (2) [0; 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 ... n ...     Explanation
I1 (2/k) / I0 (2/k) [0; k, 2k, 3k, 4k, 5k, 6k, 7k, 8k, 9k, 10k, 11k, 12k, ... nk ...

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


(2001-11-19)   The Normal Distribution of Partial Quotients

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/(k2 + 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(ak)   =   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
Vinculum
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, the Delian constant is:

21/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   x3 -3600 x2 +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 ...]

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 Hans 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 clarification from a renowned expert:

On 2003-02-11, Alf van der Poorten wrote:       [edited summary]
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  y3 - 8y - 10   (y = 3.31862821775...) :
 
y   =   [3; 3, 7, 4, 2, 30, 1, 8, 3, 1, 1, 1, 9, 2, 2, 1, 3, 22986, 2, 1, 32, 8, 2, 1, 8, 55, 1, 5, 2, 28, 1, 5, 1, 1501790, 1, 2, 1, 7, 6, 1, 1, 5, 2, 1, 6, 2, 2, 1, 2, 1, 1, 3, 1, 3, 1, 2, 4, 3, 1, 35657, 1, 17, 2, 15, 1, 1, 2, 1, 1, 5, 3, 2, 1, 1, 7, 2, 1, 7, 1, 3, 25, 49405, 1, 1, 3, 1, 1, 4, 1, 2, ...]
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.  (PostScriptMR 98c:11144  
Enrico Bombieri, Alfred J. van der Poorten: "Continued Fractions of Algebraic Numbers"   (pdf)

(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 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:

  • - [a0;  1, a2, a3, a4, ...]   =   [(-a0-1); (a2+1), a3, a4, ...]
  • - [a0; a1, a2, a3, a4, ...]   =   [(-a0-1); 1, (a1-1), a2, a3, a4, ...]     if a1¹1.

Computing the reciprocal of a CFE is easy for  positive  numbers:

  • 1 / [0;  a1, a2, a3, a4, ...]   =   [a1; a2, a3, a4, ...]
  • 1 / [a0; a1, a2, a3, a4, ...]   =   [0; a0; a1, a2, a3, a4, ...]     if a0>0.

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:

  • 1 / [-1; 1, a2, 1, a4, a5, a6, ...]   =   [(-a2-2); (a4+1), a5, a6, ...]

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 an and bn differ. Say an > b:

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

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


(2014-09-10)   The Baire Space   ( René Baire )
The set of all infinite sequences of  positive  integers,
endowed with the Tychonoff topology.

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  homeomorphism  (i.e., itself and its inverse are continuous functions)  between the two 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 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 Tychonoff topology  (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.   QED

The Baire space and the set of the irrationals are both  totally disconnected.

Baire space is homeomorphic to the irrationals  by  Martin Sleziak   (2014-04-28).

border
border
 
border
border

Expansion of Functions


(2001-11-19)
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:

 f(h)   =   a0 +  h
Vinculum
 a1 h
Vinculum
 a2 h
Vinculum
 a3 h
Vinculum
 a4 h
Vinculum
 a5 h
Vinculum
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):

  • an = fn(0), where fn is recursively 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 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 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  Padé expansions.  The general formulas given may not apply to the first coefficients  (in which case, these are underscored ):

f (h) a0 a1 a2 a3 a4 a5 a6 a7 a8 a9 a2n a2n+1
exp(h) 1 1-2-325 -2-729 2(-1)n (2n+1)(-1)n
ln(1+h) 0 12315 2/371/29 4/(2n) 2n+1
[1+Ö(1+4h/a2)]a/2 aaaaa aaaaa a a
Öh / th(Öh) 13579 1113151719 4n+1 4n+3
Öh / tg(Öh) 1-35-79 -1113-1517-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 (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
Vinculum
 1 +  h2
Vinculum
 -3 +  h2
Vinculum
 -5/9 +  h2
Vinculum
 -63/4 +  h2
Vinculum
 -4/25 +  h2
Vinculum
-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:

a0 = 1,   a1 = -3,   a2 = -5/9,   a3 = -64/4,   a4 = -4/25,   a5 = -2475/64,   ...
a2n = -(4n+1) / (2n un),     a2n+1 = -(4n+3) un
where   un =  
2n+1
Vinculum
22n
ì
î
2n
n
ü
þ
  =   
(2n+1)!!
Vinculum
(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 2nn!.


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  (1924-1993)
    "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  (1913-2000)
    "Tomorrow's Math : Unsolved Problems for the Amateur" ©1962-72
    Oxford University Press (Second Edition, 1972), New York.
border
border
 
border
border

Engel Series  &  Pierce Series


(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  (a)  as follows.

x   =      1    1  +   1   1  +   1   1  +   1   (   ...   ))))
vinculum vinculum vinculum vinculum
a1 a2 a3 a4

This is known as an  Engel expansion  (or  Engel series )  in honor of Friedrich 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 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  a-1.  If such finite expansions are accepted, we must rule out Engel expansions that are ultimately 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:

p   =   { 1, 1, 1, 8, 8, 17, 19, 300, 1991, 2492, 7236, 10586, 34588, 63403, 70637, 1236467, 5417668, 5515697, 5633167, 7458122, 9637848, 9805775, 41840855, 58408380, 213130873, 424342175, 2366457522, 4109464489, 21846713216, 27803071890, 31804388758, 32651669133, 40718029364, 47492518161, 68981480654, 199887242694, 423715742607, 1946488958454 ... }   A006784
 
Ö2   =   { 1, 3, 5, 5, 16, 18, 78, 102, 120, 144, 251, 363, 1402, 31169, 88630, 184655, 259252, 298770, 4196070, 38538874, 616984563, 1975413035, 5345718057, 27843871197, 54516286513, 334398528974, 445879679626, 495957494386, 2450869042061, 2629541150529, 4088114099885, 13941883241047, 19419852314686, 37050390695365, 699870848645368, 1402880565195416, 2085612785432685, 2336321317262184 ... }   A028254

A Few Remarkable Engel Expansions
1 / (k-1) { k, k, k, k, k, k, k, k, k, ...
exp (1/k) - 1 { k, 2k, 3k, 4k, 5k, 6k, 7k, 8k, 9k, 10k, 11k, 12k, ... nk ...
3 exp (-1) - 1 { 10, 28, 54, 88, 130, 180, 238, 304, 378, 460, ... 2n (2n+3) ...
k sinh (1/k) - 1 { 6 k2, 20 k2, 42 k2, 72 k2, 110 k2, 156 k2, ... 2n (2n+1) k2 ...
cosh (1/k) - 1 { 2 k2, 12 k2, 30 k2, 56 k2, 90 k2, 132 k2, ... 2n (2n-1) k2 ...

There is a very simple algorithm which yields the Engel expansion of a positive number  x.  It may be expressed by the following recurrence  (which halts, for rational numbers, when  x 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.

Wikipedia   |   Mathworld


(2008-04-23)   Pierce expansion of a positive number below 1   (1929)
A unique  (strictly)  increasing  sequence of positive integers.

x   =      1    1  -   1   1  -   1   1  -   1   (   ...   ))))
vinculum vinculum vinculum vinculum
a1 a2 a3 a4

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)
0   Æ   (the empty set)
1   1.
½   { 2 }   or   { 1, 2 }   (the only number with  two  expansions)
1 - e -1   N*   (all the positive integers)   A000027
1 - exp (-1/k)   k, 2k, 3k, 4k, 5k, 6k, 7k, 8k, 9k, 10k, 11k, 12k, ... nk ...
1 - k sin (1/k)   6 k2, 20 k2, 42 k2, 72 k2, 110 k2, 156 k2, ... 2n (2n+1) k2 ...
1 - cos (1/k)   2 k2, 12 k2, 30 k2, 56 k2, 90 k2, 132 k2, ... 2n (2n-1) k2 ...
1/f = (Ö5-1)/2   1, 2, 4, 17, 19, 5777, 5779, 192900153617, ...   A118242
Ö2 / 2   1, 3, 8, 33, 35, 39201, 39203, 60245508192801, ...   A091831
Ö3 / 2   1, 7, 16, 193, 195, 7300801, 7300803, ...
Ö3 / 3   1, 2, 6, 13, 15, 2701, 2703, 19726764301, 19726764303, ...
0.362306222...   2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43 , ...   A000040

The last entry shows the  set of all primes  encoded into one number!

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  x 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  1/p  (A006283)  namely:

1     =      1    1  -   1   1  -   1   1  -   1   (   ...   ))))
vinculum vinculum vinculum vinculum vinculum
p322118383

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  ½ :

1, 4, 5, 7, 8, 18, 384, 7958, 14304, 16623, 18610, 20685, 72923, 883177, 1516692, 2493788, 2504069, 22881179, 110219466, 2241255405, 34982468090, 64356019489, 110512265214, 1142808349967, 3550630472116, 5238523454726, 7129035664265, 8830497667455, 73077905092939, 214546637412471, 488848508730773, 10201865448706686, 15132832933748616, 33739918162365100, 35804846593818133, 346958191630052089, 669921148437431078, 3959601655250244537, 13642351619526186556,  ...   A140076

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 cardinalitythe power of the continuum :

  C   =   2 À0

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

Paul Erdös  &  Jeffrey O. Shallit   |   Mathworld

border
border
visits since November 19, 2001
 (c) Copyright 2000-2014, Gerard P. Michon, Ph.D.