Periodic continued fraction explained

In mathematics, an infinite periodic continued fraction is a continued fraction that can be placed in the form

x = a _{0} + \cfrac{ 1 }{a _{1} + \cfrac{ 1 }{a _{2} + \cfrac{ 1 }{ \ddots a _{k} + \cfrac{ 1 }{a _{k+1} + \cfrac{\ddots}{ \ddots a _{k+m-1} + \cfrac{ 1 }{a _{k+m} + \cfrac{ 1 }{a _{k+1} + \cfrac{ 1 }{a _{k+2} + {\ddots}}}}}}}}}

where the initial block [''a''_''0'', ''a''₁,...''a''_''k''] of k+1 partial denominators is followed by a block [''a''_''k''+1, ''a''_''k''+2,...''a''_''k''+''m''] of m partial denominators that repeats ad infinitum. For example,

\sqrt 2 can be expanded to the periodic continued fraction [1,2,2,2,...].

This article considers only the case of periodic regular continued fractions. In other words, the remainder of this article assumes that all the partial denominators a_i (i ≥ 1) are positive integers. The general case, where the partial denominators a_i are arbitrary real or complex numbers, is treated in the article convergence problem.

Purely periodic and periodic fractions

Since all the partial numerators in a regular continued fraction are equal to unity we can adopt a shorthand notation in which the continued fraction shown above is written as

\begin{align} x& = [a _{0;a} _{1,a} _{2,...,a} _{k,a} _{k+1} ,a _{k+2} , ... ,a _{k+m} ,a _{k+1} ,a _{k+2} , ... ,a _{k+m} , ... ]\\ & = [a _{0;a} _{1,a} _{2,...,a} _{k,\overline{a} _{k+1} ,a _{k+2} , ... ,a _{k+m} }]\end

where, in the second line, a vinculum marks the repeating block. Some textbooks use the notation

\begin{align} x& = [a _{0;a} _{1,a} _{2,...,a} ^{• k, a} _{k+1} ,a _{k+2} , ... , • a _{k+m} ] \end{align}

where the repeating block is indicated by dots over its first and last terms.

If the initial non-repeating block is not present  - that is, if k = -1, a₀ = a_m and

x = [\overline{a _{0;a} _{1,a} _{2,...,a} _{m-1} }],

the regular continued fraction x is said to be purely periodic. For example, the regular continued fraction [1; 1, 1, 1, ...] of the golden ratio φ is purely periodic, while the regular continued fraction [1; 2, 2, 2, ...] of

\sqrt 2 is periodic, but not purely periodic.

As unimodular matrices

Periodic continued fractions are in one-to-one correspondence with the real quadratic irrationals. The correspondence is explicitly provided by Minkowski's question-mark function. That article also reviews tools that make it easy to work with such continued fractions. Consider first the purely periodic part

x = [ 0 ;\overline{a _{1,a} _{2,...,a} _{m}],} This can, in fact, be written asx = (\alpha x + \beta)/(\gamma x + \delta) with the \alpha,\beta,\gamma,\delta being integers, and satisfying \alpha \delta - \beta \gamma =1 . Explicit values can be obtained by writing S = \begin{pmatrix} 1 & 0 \ 1 & 1 \end{pmatrix} which is termed a "shift", so that S ^{n} = \begin{pmatrix} 1 & 0 \ n & 1 \end{pmatrix} and similarly a reflection, given byT\mapsto \begin{pmatrix} -1 & 1 \ 0 & 1 \end{pmatrix} so that T ^{2=I} . Both of these matrices are unimodular, arbitrary products remain unimodular. Then, given x as above, the corresponding matrix is of the form S ^{a _{1}} TS ^{a _{2}} T … TS ^{a _{m}} = \begin{pmatrix} \alpha & \beta\ \gamma & \delta\end{pmatrix} and one hasx = [ 0 ;\overline{a _{1,a} _{2,...,a} _{m}]} = (\alpha x + \beta)/(\gamma x + \delta) as the explicit form. As all of the matrix entries are integers, this matrix belongs to the modular group SL( 2 , Z ).

Relation to quadratic irrationals

A quadratic irrational number is an irrational real root of the quadratic equation

ax ^{2} + bx + c = 0

where the coefficients a, b, and c are integers, and the discriminant, b² - 4ac, is greater than zero. By the quadratic formula, every quadratic irrational can be written in the form

\zeta = (P + \sqrt{D)/() }

where P, D, and Q are integers, D > 0 is not a perfect square (but not necessarily square-free), and Q divides the quantity P² - D (for example (6+)/4). Such a quadratic irrational may also be written in another form with a square-root of a square-free number (for example (3+)/2) as explained for quadratic irrationals.

By considering the complete quotients of periodic continued fractions, Euler was able to prove that if x is a regular periodic continued fraction, then x is a quadratic irrational number. The proof is straightforward. From the fraction itself, one can construct the quadratic equation with integral coefficients that x must satisfy.

Lagrange proved the converse of Euler's theorem: if x is a quadratic irrational, then the regular continued fraction expansion of x is periodic. Given a quadratic irrational x one can construct m different quadratic equations, each with the same discriminant, that relate the successive complete quotients of the regular continued fraction expansion of x to one another. Since there are only finitely many of these equations (the coefficients are bounded), the complete quotients (and also the partial denominators) in the regular continued fraction that represents x must eventually repeat.

Reduced surds

\zeta = (P + \sqrt{D)/() } is said to be reduced if \zeta > 1 and its conjugate η = (P - \sqrt{D)/() }satisfies the inequalities -1 < η < 0 . For instance, the golden ratio \phi = ( 1 + \sqrt{ 5 })/ 2 = 1 . 618033 ... is a reduced surd because it is greater than one and its conjugate ( 1 - \sqrt{ 5 })/ 2 = -0 . 618033 ... is greater than -1 and less than zero. On the other hand, the square root of two \sqrt{ 2 } = ( 0 + \sqrt{ 8 })/ 2 is greater than one but is not a reduced surd because its conjugate - \sqrt{ 2 } = ( 0 - \sqrt{ 8 })/ 2 is less than -1.

Galois proved that the regular continued fraction which represents a quadratic surd ζ is purely periodic if and only if ζ is a reduced surd. In fact, Galois showed more than this. He also proved that if ζ is a reduced quadratic surd and η is its conjugate, then the continued fractions for ζ and for (-1/η) are both purely periodic, and the repeating block in one of those continued fractions is the mirror image of the repeating block in the other. In symbols we have

\begin{align} \zeta& = [\overline{a _{0;a} _{1,a} _{2,...,a} _{m-1} }]\\[3pt]\frac& = [\overline{a_{m-1};a_{m-2},a_{m-3},\dots,a_0}]\,\end

where ζ is any reduced quadratic surd, and η is its conjugate.

From these two theorems of Galois a result already known to Lagrange can be deduced. If r > 1 is a rational number that is not a perfect square, then

\sqrt{r} = [a _{0;\overline{a} _{1,a} _{2,...,a} _{2,a} _{1,2a} _{0}].}

In particular, if n is any non-square positive integer, the regular continued fraction expansion of contains a repeating block of length m, in which the first m - 1 partial denominators form a palindromic string.

Length of the repeating block

By analyzing the sequence of combinations

(P _{n} + \sqrt{D)/() }

that can possibly arise when ζ = (P +)/Q is expanded as a regular continued fraction, Lagrange showed that the largest partial denominator a_i in the expansion is less than 2, and that the length of the repeating block is less than 2D.

l{O}(\sqrt{D}ln{D}).

Canonical form and repetend

The following iterative algorithm can be used to obtain the continued fraction expansion in canonical form (S is any natural number that is not a perfect square):

m _{0=0} d _{0=1} a _{0=\left\lfloor\sqrt{S}\right\rfloor} m _{n+1} = d _{na} _{n-m} _{n} d _{n+1} = (S - m ^{2} _{n +1})/(d _{n}) a _{n+1} = \left\lfloor (\sqrt{S)/(+ m) _{n+1} }\right\rfloor =\left\lfloor\frac\right\rfloor\!.

Notice that m_n, d_n, and a_n are always integers.The algorithm terminates when this triplet is the same as one encountered before.The algorithm can also terminate on a_i when a_i = 2 a₀, which is easier to implement.

The expansion will repeat from then on. The sequence [''a''₀; ''a''₁, ''a''₂, ''a''₃, ...] is the continued fraction expansion:

\sqrt{S} = a _{0} + \cfrac{ 1 }{a _{1} + \cfrac{ 1 }{a _{2} + \cfrac{ 1 }{a _{3+\ddots}}}}

Example

To obtain as a continued fraction, begin with m₀ = 0; d₀ = 1; and a₀ = 10 (10² = 100 and 11² = 121 > 114 so 10 chosen).

\begin{align} \sqrt{ 114 } & = (\sqrt{ 114)/(+0 }{ 1 }) =10+ (\sqrt{ 114)/(-10 }{ 1 }) =10+ ((\sqrt{ 114)/(-10 )(\sqrt{ 114 } +10 )}{\sqrt{ 114 } +10 }) \\ & =10+ (114-100)/(\sqrt{ 114) +10 } =10+ (1)/((\sqrt{ 114)/(+10)) { 14 }}. \end{align} m _{1} = d _{0} ⋅ a _{0} - m _{0} = 1 ⋅ 10 - 0 = 10 . d _{1} = (S - m ^{2} _{1})/(d _{0}) = (114-10 ^{2})/(1) = 14 . a _{1} = \left\lfloor (a _{0+m} _{1})/(d _{1}) \right\rfloor = \left\lfloor (10+10)/(14) \right\rfloor = \left\lfloor (20)/(14) \right\rfloor = 1 .

So, m₁ = 10; d₁ = 14; and a₁ = 1.

(\sqrt{ 114)/(+10 }{ 14 }) =1+ (\sqrt{ 114)/(-4 }{ 14 }) =1+ (114-16)/(14 (\sqrt{ 114) +4 )} =1+ (1)/((\sqrt{ 114)/(+4)) { 7 }}.

Next, m₂ = 4; d₂ = 7; and a₂ = 2.

(\sqrt{ 114)/(+4 }{ 7 }) =2+ (\sqrt{ 114)/(-10 }{ 7 }) =2+ (14)/(7 (\sqrt{ 114) +10 )} =2+ (1)/((\sqrt{ 114)/(+10)) { 2 }}. (\sqrt{ 114)/(+10 }{ 2 } =10+ (\sqrt{ 114)/(-10 }{ 2 } =10+ (14)/(2 (\sqrt{ 114))) +10 )} =10+ (1)/((\sqrt{ 114)/(+10)) { 7 }}. (\sqrt{ 114)/(+10 }{ 7 } =2+ (\sqrt{ 114)/(-4 }{ 7 } =2+ (98)/(7 (\sqrt{ 114))) +4 )} =2+ (1)/((\sqrt{ 114)/(+4)) { 14 }}. (\sqrt{ 114)/(+4 }{ 14 } =1+ (\sqrt{ 114)/(-10 }{ 14 } =1+ (14)/(14 (\sqrt{ 114))) +10 )} =1+ (1)/((\sqrt{ 114)/(+10)) { 1 }}. (\sqrt{ 114)/(+10 }{ 1 } =20+ (\sqrt{ 114)/(-10 }{ 1 } =20+ (14)/(\sqrt{ 114))) +10 } =20+ (1)/((\sqrt{ 114)/(+10)) { 14 }}.

Now, loop back to the second equation above.

Consequently, the simple continued fraction for the square root of 114 is

\sqrt{ 114 } = [ 10 ;\overline{ 1 , 2 , 10 , 2 , 1 , 20 }].

is approximately 10.67707 82520. After one expansion of the repetend, the continued fraction yields the rational fraction

(21194)/(1985) whose decimal value is approx. 10.67707 80856, a relative error of0.0000016% or 1.6 parts in 100,000,000.

Generalized continued fraction

A more rapid method is to evaluate its generalized continued fraction. From the formula derived there:

\begin{align} \sqrt{z} = \sqrt{x ^{2+y}} & = x + \cfrac{y} { 2 x + \cfrac{y} { 2 x + \cfrac{y} { 2 x + \ddots}}} \\ & = x + \cfrac{ 2 x ⋅ y}{ 2 ( 2 z - y) - y - \cfrac{y ^{2}} { 2 ( 2 z - y) - \cfrac{y ^{2}} { 2 ( 2 z - y) - \ddots}}} \end{align}

and the fact that 114 is 2/3 of the way between 10²=100 and 11²=121 results in

\begin{align} \sqrt{ 114 } = \cfrac{\sqrt{ 1026 }}{ 3 } = \cfrac{\sqrt{ 32 ^{2+2}}{3}} & = \cfrac{ 32 }{ 3 } + \cfrac{ 2 / 3 } { 64+ \cfrac{ 2 } { 64+ \cfrac{ 2 } { 64+ \cfrac{ 2 } { 64+ \ddots}}}} \\ & = \cfrac{ 32 }{ 3 } + \cfrac{ 2 } { 192+ \cfrac{ 18 } { 192+ \cfrac{ 18 } { 192+ \ddots}}}, \end{align}

which is simply the aforementioned [10;1,2, 10,2,1, 20,1,2] evaluated at every third term. Combining pairs of fractions produces

\begin{align} \sqrt{ 114 } = \cfrac{\sqrt{ 32 ^{2+2}}{3}} & = \cfrac{ 32 }{ 3 } + \cfrac{ 64 / 3 } { 2050-1- \cfrac{ 1 } { 2050- \cfrac{ 1 } { 2050- \ddots}}} \\ & = \cfrac{ 32 }{ 3 } + \cfrac{ 64 }{ 6150-3- \cfrac{ 9 } { 6150- \cfrac{ 9 } { 6150- \ddots}}}, \end{align}

which is now

[ 10 ; 1 , 2 , \overline{ 10 , 2 , 1 , 20 , 1 , 2 }] evaluated at the third term and every six terms thereafter.

References

• Web site: Beceanu. Marius. 5 February 2003. Period of the Continued Fraction of sqrt(n). Theorem 2.3. 3 May 2022. https://web.archive.org/web/20151221205104/http://web.math.princeton.edu/mathlab/jr02fall/Periodicity/mariusjp.pdf. 21 December 2015.
• Cohn. J. H. E.. 1977. The length of the period of the simple continued fraction expansion of d^1/2. Pacific J. Math.. 71. 21–32. 10.2140/pjm.1977.71.21. free.
• Book: Davenport , H. . December 1982. The Higher Arithmetic. Cambridge University Press. 0-521-28678-6.
• Book: Gliga , Alexandra Ioana . 17 March 2006. On continued fractions of the square root of prime numbers. Corollary 3.3. 3 May 2022.
• Hickerson. Dean R.. 1973. Length of period of simple continued fraction expansion of vd. Pacific J. Math.. 46. 429–432. 10.2140/pjm.1973.46.429. free.
• Book: Khinchin , A. Ya. . Aleksandr Khinchin. 1964. Continued Fractions. registration. Originally published in Russian, 1935. University of Chicago Press. 0-486-69630-8. (This is now available as a reprint from Dover Publications.)
• Book: Long , Calvin T. . 1972. Elementary Introduction to Number Theory. 3 Sub. Waveland Pr Inc. 77-171950.
• Book: Pettofrezzo. Anthony Joseph. Byrkit. Donald R.. 1970. Elements of Number Theory. Prentice Hall. Englewood Cliffs. 11. 9780132683005. 77-81766.
• Podsypanin. E.V.. 1982. Length of the period of a quadratic irrational. Journal of Soviet Mathematics. 18. 6. 919–923. 10.1007/BF01763963. 119567810.
• Book: Rockett. Andrew M.. Szüsz. Peter. Peter Szüsz. 1992. CONTINUED FRACTIONS. registration. World Scientific Publishing Company. 9789810210526.

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Periodic continued fraction".

Except where otherwise indicated, Everything.Explained.Today is © Copyright 2009-2024, A B Cryer, All Rights Reserved. Cookie policy.