NumberTheory`ContinuedFractions`
The decimal expansion is the most common way to represent a real number. This package supports two alternative representations as follows: (1) the continued fraction expansion of a real number and (2) the arbitrary base expansion of a rational number in terms of preperiodic and periodic parts.
The continued fraction expansion of a real number is a representation of the form
The integers are called the partial quotients. Rational numbers have a finite number of partial quotients, while irrational numbers have an infinite continued fraction expansion. Continued fractions also find application in the factorization of integers (see, for example, Chapter 10 in [Rosen]).
If the number has partial quotients , the rational number formed by considering the first partial quotients , is called the convergent of . The convergents of a number provide, in a certain sense, the best rational approximation with a small denominator to the given real number.
In Mathematica versions 4.0 and later, the kernel functions ContinuedFraction and RealDigits can be used to produce continued fraction and periodic representations of rational numbers. FromContinuedFraction and FromDigits are used to invert these operations. This package enhances these capabilities by providing functions for computing convergents and for nicely typesetting continued fractions and periodic forms.
Continued fractions.
This loads the package.
In[1]:= <<NumberTheory`ContinuedFractions`
The kernel function ContinuedFraction generates a list of the partial quotients of the continued fraction. Here are the first 10 terms of the expansion of pi.
In[2]:= cf = ContinuedFraction[Pi, 10]
Out[2]=
ContinuedFractionForm can be wrapped around the result of ContinuedFraction for a much clearer representation as a sum of nested fractions.
In[3]:= ContinuedFractionForm[cf]
Out[3]=
Quadratic irrational numbers are of the form , where , , and are integers; is positive and not a perfect square; and is nonzero and divides . Such numbers have a continued fraction expansion that is infinite but periodic. Thus they can be represented finitely in terms of the preperiodic part followed by the periodically repeating part.
This is the continued fraction expansion of the square root of 7, a quadratic irrational. Typesetting rules defined for ContinuedFractionForm put the repeating block in parenthesis, and add an ellipse to mark the repetition.
In[4]:= cf = ContinuedFractionForm[ ContinuedFraction[Sqrt[7]] ]
Out[4]=
A continued fraction can be turned back into a rational or quadratic irrational by application of Normal.
In[5]:= Normal[cf]
Out[5]=
Finding convergents and quadratic irrationals.
The golden ratio has all of its partial quotients equal to one.
In[6]:= cf = ContinuedFractionForm[ ContinuedFraction[GoldenRatio, 10] ]
Out[6]=
This gives a list of the convergents of the continued fraction. These convergents have the Fibonacci numbers for numerators and denominators.
In[7]:= Convergents[cf]
Out[7]=
The convergents of a number converge to it while alternating sides.
In[8]:= %  N[GoldenRatio]
Out[8]=
Another useful representation of certain types of numbers is the base expansion. Not all such expansions are finite. An infinite base expansion is periodic if there are positive integers and such that for . It is common to express the base expansion
as
The nonrepeating elements constitute the preperiodic part and the repeating elements constitute the periodic part.
Periodic expansions.
This rational number has a finite decimal expansion; the preperiodic part has length two and the periodic part has length zero.
In[9]:= PeriodicForm[RealDigits[ 1/20 ]]
Out[9]=
This rational number has an infinite decimal expansion; the preperiodic part has length zero and the periodic part has length 16. The periodic part is highlighted.
In[10]:= PeriodicForm[RealDigits[ 1/17 ]]
Out[10]=
The decimal number has an infinite binary expansion. This is the reason that cannot be stored in a binary digital computer without representation error.
In[11]:= PeriodicForm[RealDigits[ 1/10, 2 ], 2]
Out[11]=
This reconstructs the previous rational number from its binary digit expansion.
In[12]:= Normal[ % ]
Out[12]=
The periodic expansion can be found to any base. If the base is under 36, the letters of the alphabet are used for the digits.
In[13]:= PeriodicForm[RealDigits[573498753434/13, 16], 16]
Out[13]=
Here is a classical example with a lengthy periodic part involving pairs of digits in the decimal digit expansion (see [Glaisher]).
In[14]:= PeriodicForm[RealDigits[1/9801]]
Out[14]=
References
[Rosen] K. H. Rosen, Elementary Number Theory and Its Applications, Third edition, Addison Wesley, Reading, MA, 1993.
[Glaisher] J. W. L. Glaisher, Messenger of Math. 2, 41, 1873.
