TOPICS
Search

Regular Continued Fraction


A regular continued fraction is a simple continued fraction

x=b_0+1/(b_1+1/(b_2+1/(b_3+...)))
(1)
=K_(k=1)^(infty)1/(b_k)
(2)
=[b_0;b_1,b_2,...],
(3)

where b_0 is an integer and b_k is a positive integer for k>0 (Rockett and Szüsz 1992, p. 3).

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

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

Regular continued fractions are also useful for finding near commensurabilities between events with different periods. For example, the Metonic cycle used for calendrical purposes by the Greeks consists of 235 lunar months which very nearly equal 19 solar years, and 235/19 is the sixth convergent of the ratio of the lunar phase (synodic) period and solar period (365.2425/29.53059). Regular continued fractions can also be used to calculate gear ratios, and were used for this purpose by the ancient Greeks (Guy 1990).

The error in approximating a number by a given convergent is roughly the multiplicative inverse of the square of the denominator of the first neglected term.

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

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

Starting the indexing of a regular continued fraction with b_0,

 b_0=|_x_|
(4)

is the integer part of x, where |_x_| is the floor function,

 b_1=|_1/(x-b_0)_|
(5)

is the integral part of the reciprocal of x-b_0,

 b_2=|_1/(1/(x-b_0)-b_1)_|
(6)

is the integral part of the reciprocal of the remainder, etc. Writing the remainders according to the recurrence relation

r_0=x
(7)
r_n=1/(r_(n-1)-b_(n-1))
(8)

gives the concise formula

 b_n=|_r_n_|.
(9)

The quantities b_n are called partial quotients, and the quantity obtained by including n terms of the continued fraction

c_n=(A_n)/(B_n)
(10)
=[b_0;b_1,...,b_n]
(11)
=b_0+1/(b_1+1/(b_2+1/(...+1/(b_n))))
(12)

is called the nth convergent.

For example, consider the computation of the continued fraction of pi, given by pi=[3;7,15,1,292,1,1,...].

termvaluePQsconvergentvalue
b_0|_pi_|=3[3]33.00000
b_1|_1/(pi-3)_|=7[3;7](22)/73.14286
b_2|_1/(1/(pi-3)-7)_|=15[3;7,15](333)/(106)3.14151

Let the simple continued fraction for x be written [b_0;b_1,...,b_n]. Then the limiting value is almost always Khinchin's constant

 K=lim_(n->infty)(b_1b_2...b_n)^(1/n)=2.68545...
(13)

(OEIS A002210).

Similarly, taking the nth root of the denominator B_n of the nth convergent as n->infty almost always gives the Lévy constant

 lim_(n->infty)B_n^(1/n)=e^(pi^2/(12ln2))=3.275823...
(14)

(OEIS A086702).

Logarithms log_(b_1)b_0 can be computed by defining b_2, ... and the positive integer n_1, ... such that

 b_1^(n_1)<b_0<b_1^(n_1+1)    b_2=(b_0)/(b_1^(n_1))
(15)
 b_2^(n_2)<b_1<b_2^(n_2+1)    b_3=(b_1)/(b_2^(n_2))
(16)

and so on. Then

 log_(b_1)b_0=[n_1,n_2,n_3,...].
(17)
ContinuedFractionLattice

A geometric interpretation for a reduced fraction y/x consists of a string through a lattice of points with ends at (1,0) and (x,y) (Klein 1896, 1932; Steinhaus 1999, p. 40; Gardner 1984, pp. 210-211, Ball and Coxeter 1987, pp. 86-87; Davenport 1992). This interpretation is closely related to a similar one for the greatest common divisor. The pegs it presses against (x_i,y_i) give alternate convergents y_i/x_i, while the other convergents are obtained from the pegs it presses against with the initial end at (0,1). The above plot is for e-2, which has convergents 0, 1, 2/3, 3/4, 5/7, ....

Continued fractions can be used to express the positive roots of any polynomial equation. Continued fractions can also be used to solve linear Diophantine equations and the Pell equation.

Gosper has invented an algorithm for performing analytic addition, subtraction, multiplication, and division using continued fractions. It requires keeping track of eight integers which are conceptually arranged at the polyhedron vertices of a cube. Although this algorithm has not appeared in print, similar algorithms have been constructed by Vuillemin (1987) and Liardet and Stambul (1998).

Gosper's algorithm for computing the continued fraction for (ax+b)/(cx+d) from the continued fraction for x is described by Gosper (1972), Knuth (1998, Exercise 4.5.3.15, pp. 360 and 601), and Fowler (1999). (In line 9 of Knuth's solution, X_k<-|_A/C_| should be replaced by X_k<-min(|_A/C_|,|_(A+B)/(C+D)_|).) Gosper (1972) and Knuth (1981) also mention the bivariate case (axy+bx+cy+d)/(Axy+Bx+Cy+D).


See also

Continued Fraction, Convergent, Generalized Continued Fraction, Khinchin's Constant, Lagrange's Continued Fraction Theorem, Lévy Constant, Lochs' Theorem, Partial Denominator, Periodic Continued Fraction, Simple Continued Fraction

Explore with Wolfram|Alpha

References

Abramowitz, M. and Stegun, I. A. (Eds.). Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th printing. New York: Dover, p. 19, 1972.Acton, F. S. "Power Series, Continued Fractions, and Rational Approximations." Ch. 11 in Numerical Methods That Work, 2nd printing. Washington, DC: Math. Assoc. Amer., 1990.Adamchik, V. "Limits of Continued Fractions and Nested Radicals." Mathematica J. 2, 54-57, 1992.Bach, E. and Shallit, J. Algorithmic Number Theory, Vol. 1: Efficient Algorithms. Cambridge, MA: MIT Press, pp. 343-344, 1996.Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 54-57 and 86-87, 1987.Berndt, B. C. and Gesztesy, F. (Eds.). Continued Fractions: From Analytic Number Theory to Constructive Approximation, A Volume in Honor of L. J. Lange. Providence, RI: Amer. Math. Soc., 1999.Beskin, N. M. Fascinating Fractions. Moscow: Mir Publishers, 1980.Brezinski, C. History of Continued Fractions and Padé Approximants. New York: Springer-Verlag, 1980.Conway, J. H. and Guy, R. K. "Continued Fractions." In The Book of Numbers. New York: Springer-Verlag, pp. 176-179, 1996.Courant, R. and Robbins, H. "Continued Fractions. Diophantine Equations." §2.4 in Supplement to Ch. 1 in What Is Mathematics?: An Elementary Approach to Ideas and Methods, 2nd ed. Oxford, England: Oxford University Press, pp. 49-51, 1996.Cuyt, A.; Petersen, A. B.; Verdonk, B.; Waadeland, H.; and Jones, W. B. Handbook of Continued Fractions for Special Functions. New York: Springer, 2008.Davenport, H. §IV.12 in The Higher Arithmetic: An Introduction to the Theory of Numbers, 6th ed. New York: Cambridge University Press, 1992.Dunne, E. and McConnell, M. "Pianos and Continued Fractions." Math. Mag. 72, 104-115, 1999.Euler, L. "On the Formulation of Continued Fractions." Delivered to the St. Petersburg Academy, Sept. 4, 1775. Published as Euler, L. "De formatione fractionum continuarum." Acta Academiae Scientarum Imperialis Petropolitinae 3, 3-29, 1782. Republished in Euler, L. Opera Omnia, Ser. 1: Opera mathematica, Vol. 15. Basel, Switzerland: Birkhäuser, 1992. http://arxiv.org/abs/math.HO/0508227.Euler, L. Introduction to Analysis of the Infinite, Book I. New York: Springer-Verlag, 1980.Fowler, D. H. The Mathematics of Plato's Academy: A New Reconstruction, 2nd ed. Oxford, England: Oxford University Press, 1999.Fowler, D. "Wallis and Number Columns by David Fowler." http://mathforum.org/epigone/math-history-list/sterbloirerm.Gardner, M. The Sixth Book of Mathematical Games from Scientific American. Chicago, IL: University of Chicago Press, pp. 210-211, 1984.Gosper, R. W. "Continued fractions query." math-fun@cs.arizona.edu posting, Dec. 27, 1996.Gosper, R. W. Item 101a in Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, pp. 37-39, Feb. 1972. http://www.inwap.com/pdp10/hbaker/hakmem/cf.html#item101a.Gosper, R. W. Item 101b in Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, pp. 39-44, Feb. 1972. http://www.inwap.com/pdp10/hbaker/hakmem/cf.html#item101b.Graham, R. L.; Knuth, D. E.; and Patashnik, O. "Continuants." §6.7 in Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, pp. 301-309, 1994.Guy, R. K. "Continued Fractions" §F20 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, p. 259, 1994.Havil, J. Gamma: Exploring Euler's Constant. Princeton, NJ: Princeton University Press, 2003.Jacobson, M. J. Jr.; Lukes, R. F.; and Williams, H. C. "An Investigation of Bounds for the Regulator of Quadratic Fields." Experiment. Math. 4, 211-225, 1995.Khinchin, A. Ya. Continued Fractions. New York: Dover, 1997.Kimberling, C. "Continued Fractions." http://faculty.evansville.edu/ck6/integer/contfr.html.Klein, F. Ausgewählte Kapitel der Zahlentheorie I. Göttingen, Germany: n.p., 1896.Klein, F. Elementary Number Theory. New York, p. 44, 1932.Kline, M. Mathematical Thought from Ancient to Modern Times. Oxford, England: Oxford University Press, 1990.Knuth, D. E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 3rd ed. Reading, MA: Addison-Wesley, p. 316, 1998.Liardet, P. and Stambul, P. "Algebraic Computation with Continued Fractions." J. Number Th. 73, 92-121, 1998.Liberman, H. Simple Continued Fractions: An Elementary to Research Level Approach. SMD Stock Analysts, 2003.Lorentzen, L. and Waadeland, H. Continued Fractions with Applications. Amsterdam, Netherlands: North-Holland, 1992.Lorentzen, L. and Waadeland, H. Continued Fractions, 2nd ed., Vol. 1: Convergence Theory. Amsterdam, Netherlands/Paris: Atlantis Press/World Scientific, 2008.Moore, C. D. An Introduction to Continued Fractions. Washington, DC: National Council of Teachers of Mathematics, 1964.Olds, C. D. Continued Fractions. New York: Random House, 1963.Perron, O. Die Lehre von den Kettenbrüchen, 3. verb. und erweiterte Aufl. Stuttgart, Germany: Teubner, 1954-57.Pettofrezzo, A. J. and Bykrit, D. R. Elements of Number Theory. Englewood Cliffs, NJ: Prentice-Hall, 1970.Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. "Evaluation of Continued Fractions." §5.2 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 163-167, 1992.Riesel, H. "Continued Fractions." Appendix 8 in Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, pp. 327-342, 1994.Rockett, A. M. and Szüsz, P. Continued Fractions. New York: World Scientific, 1992.Rose, H. E. A Course in Number Theory, 2nd ed. Oxford, England: Oxford University Press, 1994.Rosen, K. H. Elementary Number Theory and Its Applications. New York: Addison-Wesley, 1980.Schur, I. "Ein Beitrag zur additiven Zahlentheorie und zur Theorie der Kettenbrüche." Sitzungsber. Preuss. Akad. Wiss. Phys.-Math. Klasse, pp. 302-321, 1917.Sloane, N. J. A. Sequences A000037/M0613, A013943, A052119, A111129, and A113011 in "The On-Line Encyclopedia of Integer Sequences."Steinhaus, H. Mathematical Snapshots, 3rd ed. New York: Dover, pp. 39-42, 1999.Van Tuyl, A. L. "Continued Fractions." http://archives.math.utk.edu/articles/atuyl/confrac/.Vuillemin, J. "Exact Real Computer Arithmetic with Continued Fractions." INRIA Report 760. Le Chesnay, France: INRIA, Nov. 1987. http://www.inria.fr/RRRT/RR-0760.html.Wagon, S. "Continued Fractions." §8.5 in Mathematica in Action. New York: W. H. Freeman, pp. 263-271, 1991.Wall, H. S. Analytic Theory of Continued Fractions. New York: Chelsea, 1948.Wallis, J. Arithmetica Infinitorum. Oxford, England, 1656.Weisstein, E. W. "Books about Continued Fractions." http://www.ericweisstein.com/encyclopedias/books/ContinuedFractions.html.Williams, H. C. "A Numerical Investigation into the Length of the Period of the Continued Fraction Expansion of sqrt(D)." Math. Comput. 36, 593-601, 1981.

Cite this as:

Weisstein, Eric W. "Regular Continued Fraction." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/RegularContinuedFraction.html

Subject classifications