# Periodic continued fraction

Last updated

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

## Contents

${\displaystyle x=a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {\ddots }{\quad \ddots \quad a_{k}+{\cfrac {1}{a_{k+1}+{\cfrac {\ddots }{\quad \ddots \quad a_{k+m-1}+{\cfrac {1}{a_{k+m}+{\cfrac {1}{a_{k+1}+{\cfrac {1}{a_{k+2}+{\ddots }}}}}}}}}}}}}}}}}}$

where the initial block of k + 1 partial denominators is followed by a block [ak+1, ak+2,...ak+m] of partial denominators that repeats over and over again, ad infinitum. For example, ${\displaystyle {\sqrt {2}}}$ can be expanded to a periodic continued fraction, namely as [1,2,2,2,...].

The partial denominators {ai} can in general be any real or complex numbers. That general case is treated in the article convergence problem. The remainder of this article is devoted to the subject of simple continued fractions that are also periodic. In other words, the remainder of this article assumes that all the partial denominators ai (i  1) are positive integers.

## 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

{\displaystyle {\begin{aligned}x&=[a_{0};a_{1},a_{2},\dots ,a_{k},a_{k+1},a_{k+2},\dots ,a_{k+m},a_{k+1},a_{k+2},\dots ,a_{k+m},\dots ]\\&=[a_{0};a_{1},a_{2},\dots ,a_{k},{\overline {a_{k+1},a_{k+2},\dots ,a_{k+m}}}]\end{aligned}}}

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

{\displaystyle {\begin{aligned}x&=[a_{0};a_{1},a_{2},\dots ,a_{k},{\dot {a}}_{k+1},a_{k+2},\dots ,{\dot {a}}_{k+m}]\end{aligned}}}

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

If the initial non-repeating block is not present that is, if k = -1, a0 = am and

${\displaystyle x=[{\overline {a_{0};a_{1},a_{2},\dots ,a_{m-1}}}],}$

the regular continued fraction x is said to be purely periodic. For example, the regular continued fraction for the golden ratio φ given by [1; 1, 1, 1, ...] is purely periodic, while the regular continued fraction for the square root of two [1; 2, 2, 2, ...] is periodic, but not purely periodic.

## As unimodular matrices

Such periodic 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

${\displaystyle x=[{\overline {0;a_{1},a_{2},\dots ,a_{m}}}],}$

This can, in fact, be written as

${\displaystyle x={\frac {\alpha x+\beta }{\gamma x+\delta }}}$

with the ${\displaystyle \alpha ,\beta ,\gamma ,\delta }$ being integers, and satisfying ${\displaystyle \alpha \delta -\beta \gamma =1.}$ Explicit values can be obtained by writing

${\displaystyle S={\begin{pmatrix}1&0\\1&1\end{pmatrix}}}$

which is termed a "shift", so that

${\displaystyle S^{n}={\begin{pmatrix}1&0\\n&1\end{pmatrix}}}$

and similarly a reflection, given by

${\displaystyle T\mapsto {\begin{pmatrix}-1&1\\0&1\end{pmatrix}}}$

so that ${\displaystyle T^{2}=I}$. Both of these matrices are unimodular, arbitrary products remain unimodular. Then, given ${\displaystyle x}$ as above, the corresponding matrix is of the form [3]

${\displaystyle S^{a_{1}}TS^{a_{2}}T\cdots TS^{a_{m}}={\begin{pmatrix}\alpha &\beta \\\gamma &\delta \end{pmatrix}}}$

and one has

${\displaystyle x=[{\overline {0;a_{1},a_{2},\dots ,a_{m}}}]={\frac {\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 ${\displaystyle SL(2,\mathbb {Z} ).}$

## Relation to quadratic irrationals

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

${\displaystyle ax^{2}+bx+c=0}$

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

${\displaystyle \zeta ={\frac {P+{\sqrt {D}}}{Q}}}$

where P, D, and Q are integers, D > 0 is not a perfect square (but not necessarily square-free), and Q divides the quantity P2  D (for example (6+8)/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)/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. [4] 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

The quadratic surd ${\displaystyle \zeta ={\frac {P+{\sqrt {D}}}{Q}}}$ is said to be reduced if ${\displaystyle \zeta >1}$ and its conjugate ${\displaystyle \eta ={\frac {P-{\sqrt {D}}}{Q}}}$ satisfies the inequalities ${\displaystyle -1<\eta <0}$. For instance, the golden ratio ${\displaystyle \phi =(1+{\sqrt {5}})/2=1.618033...}$ is a reduced surd because it is greater than one and its conjugate ${\displaystyle (1-{\sqrt {5}})/2=-0.618033...}$ is greater than 1 and less than zero. On the other hand, the square root of two ${\displaystyle {\sqrt {2}}=(0+{\sqrt {8}})/2}$ is greater than one but is not a reduced surd because its conjugate ${\displaystyle -{\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

{\displaystyle {\begin{aligned}\zeta &=[{\overline {a_{0};a_{1},a_{2},\dots ,a_{m-1}}}]\\[3pt]{\frac {-1}{\eta }}&=[{\overline {a_{m-1};a_{m-2},a_{m-3},\dots ,a_{0}}}]\,\end{aligned}}}

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

${\displaystyle {\sqrt {r}}=[a_{0};{\overline {a_{1},a_{2},\dots ,a_{2},a_{1},2a_{0}}}].}$

In particular, if n is any non-square positive integer, the regular continued fraction expansion of n 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

${\displaystyle {\frac {P_{n}+{\sqrt {D}}}{Q_{n}}}}$

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

More recently, sharper arguments [5] [6] based on the divisor function have shown that L(D), the length of the repeating block for a quadratic surd of discriminant D, is given by

${\displaystyle L(D)={\mathcal {O}}({\sqrt {D}}\ln {D})}$

where the big O means "on the order of", or "asymptotically proportional to" (see big O notation).

### Canonical form and repetend

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

${\displaystyle m_{0}=0\,\!}$
${\displaystyle d_{0}=1\,\!}$
${\displaystyle a_{0}=\left\lfloor {\sqrt {S}}\right\rfloor \,\!}$
${\displaystyle m_{n+1}=d_{n}a_{n}-m_{n}\,\!}$
${\displaystyle d_{n+1}={\frac {S-m_{n+1}^{2}}{d_{n}}}\,\!}$
${\displaystyle a_{n+1}=\left\lfloor {\frac {{\sqrt {S}}+m_{n+1}}{d_{n+1}}}\right\rfloor =\left\lfloor {\frac {a_{0}+m_{n+1}}{d_{n+1}}}\right\rfloor \!.}$

Notice that mn, dn, and an are always integers. The algorithm terminates when this triplet is the same as one encountered before. The algorithm can also terminate on ai when ai = 2 a0, [8] which is easier to implement.

The expansion will repeat from then on. The sequence [a0; a1, a2, a3, ...] is the continued fraction expansion:

${\displaystyle {\sqrt {S}}=a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+\,\ddots }}}}}}}$

#### Example

To obtain 114 as a continued fraction, begin with m0 = 0; d0 = 1; and a0 = 10 (102 = 100 and 112 = 121 > 114 so 10 chosen).

{\displaystyle {\begin{aligned}{\sqrt {114}}&={\frac {{\sqrt {114}}+0}{1}}=10+{\frac {{\sqrt {114}}-10}{1}}=10+{\frac {({\sqrt {114}}-10)({\sqrt {114}}+10)}{{\sqrt {114}}+10}}\\&=10+{\frac {114-100}{{\sqrt {114}}+10}}=10+{\frac {1}{\frac {{\sqrt {114}}+10}{14}}}.\end{aligned}}}
${\displaystyle m_{1}=d_{0}\cdot a_{0}-m_{0}=1\cdot 10-0=10\,.}$
${\displaystyle d_{1}={\frac {S-m_{1}^{2}}{d_{0}}}={\frac {114-10^{2}}{1}}=14\,.}$
${\displaystyle a_{1}=\left\lfloor {\frac {a_{0}+m_{1}}{d_{1}}}\right\rfloor =\left\lfloor {\frac {10+10}{14}}\right\rfloor =\left\lfloor {\frac {20}{14}}\right\rfloor =1\,.}$

So, m1 = 10; d1 = 14; and a1 = 1.

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

Next, m2 = 4; d2 = 7; and a2 = 2.

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

Now, loop back to the second equation above.

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

${\displaystyle {\sqrt {114}}=[10;{\overline {1,2,10,2,1,20}}].\,}$(sequence in the OEIS )

114 is approximately 10.67707 82520. After one expansion of the repetend, the continued fraction yields the rational fraction ${\displaystyle {\frac {21194}{1985}}}$ whose decimal value is approx. 10.67707 80856, a relative error of 0.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:

${\displaystyle {\sqrt {z}}={\sqrt {x^{2}+y}}=x+{\cfrac {y}{2x+{\cfrac {y}{2x+{\cfrac {y}{2x+\ddots }}}}}}=x+{\cfrac {2x\cdot y}{2(2z-y)-y-{\cfrac {y^{2}}{2(2z-y)-{\cfrac {y^{2}}{2(2z-y)-\ddots }}}}}}}$

and the fact that 114 is 2/3 of the way between 102=100 and 112=121 results in

${\displaystyle {\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 }}}}}},}$

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

${\displaystyle {\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 }}}}}},}$

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

## Notes

1. Pettofrezzo & Byrkit (1970 , p. 158)
2. Long (1972 , p. 187)
3. Khinchin, A. Ya. (1964) [Originally published in Russian, 1935]. . University of Chicago Press. ISBN   0-486-69630-8.This is now available as a reprint from Dover Publications.
4. Davenport, H. (1982). The Higher Arithmetic. Cambridge University Press. p. 104. ISBN   0-521-28678-6.
5. Hickerson, Dean R. (1973). "Length of period of simple continued fraction expansion of √d". Pacific J. Math. 46: 429–432. doi:.
6. Podsypanin, E.V. (1982). "Length of the period of a quadratic irrational". Journal of Soviet Mathematics. 18 (6): 919–923. doi:10.1007/BF01763963.
7. Beceanu, Marius. "Period of the Continued Fraction of sqrt(n)" (PDF). Theorem 2.3. Archived from the original (PDF) on 21 December 2015. Retrieved 21 December 2015.
8. Gliga, Alexandra Ioana (March 17, 2006). On continued fractions of the square root of prime numbers (PDF). Corollary 3.3.

## Related Research Articles

In mathematics, an exponential function is a function of the form

In mathematics, a square root of a number x is a number y such that y2 = x; in other words, a number y whose square (the result of multiplying the number by itself, or y ⋅ y) is x. For example, 4 and −4 are square roots of 16, because 42 = (−4)2 = 16. Every nonnegative real number x has a unique nonnegative square root, called the principal square root, which is denoted by where the symbol is called the radical sign or radix. For example, the principal square root of 9 is 3, which is denoted by because 32 = 3 ⋅ 3 = 9 and 3 is nonnegative. The term (or number) whose square root is being considered is known as the radicand. The radicand is the number or expression underneath the radical sign, in this case 9.

In mathematics, an nth root of a number x is a number r which, when raised to the power n, yields x:

In mathematics, a quadratic irrational number is an irrational number that is the solution to some quadratic equation with rational coefficients which is irreducible over the rational numbers. Since fractions in the coefficients of a quadratic equation can be cleared by multiplying both sides by their common denominator, a quadratic irrational is an irrational root of some quadratic equation whose coefficients are integers. The quadratic irrational numbers, a subset of the complex numbers, are algebraic numbers of degree 2, and can therefore be expressed as

In number theory, Aleksandr Yakovlevich Khinchin proved that for almost all real numbers x, coefficients ai of the continued fraction expansion of x have a finite geometric mean that is independent of the value of x and is known as Khinchin's constant.

In complex analysis, a branch of mathematics, a generalized continued fraction is a generalization of regular continued fractions in canonical form, in which the partial numerators and partial denominators can assume arbitrary complex values.

In mathematics, two quantities are in the silver ratio if the ratio of the smaller of those two quantities to the larger quantity is the same as the ratio of the larger quantity to the sum of the smaller quantity and twice the larger quantity. This defines the silver ratio as an irrational mathematical constant, whose value of one plus the square root of 2 is approximately 2.4142135623. Its name is an allusion to the golden ratio; analogously to the way the golden ratio is the limiting ratio of consecutive Fibonacci numbers, the silver ratio is the limiting ratio of consecutive Pell numbers. The silver ratio is denoted by δS.

Methods of computing square roots are numerical analysis algorithms for finding the principal, or non-negative, square root of a real number. Arithmetically, it means given S, a procedure for finding a number which when multiplied by itself, yields S; algebraically, it means a procedure for finding the non-negative root of the equation x2 - S = 0; geometrically, it means given the area of a square, a procedure for constructing a side of the square.

In mathematics, a quadratic equation is a polynomial equation of the second degree. The general form is

In the analytic theory of continued fractions, the convergence problem is the determination of conditions on the partial numeratorsai and partial denominatorsbi that are sufficient to guarantee the convergence of the continued fraction

The square root of 3 is the positive real number that, when multiplied by itself, gives the number 3. It is denoted mathematically as 3. It is more precisely called the principal square root of 3, to distinguish it from the negative number with the same property. The square root of 3 is an irrational number. It is also known as Theodorus' constant, after Theodorus of Cyrene, who proved its irrationality.

In the metrical theory of regular continued fractions, the kth complete quotient ζk is obtained by ignoring the first k partial denominators ai. For example, if a regular continued fraction is given by

In mathematics, and more particularly in the analytic theory of regular continued fractions, an infinite regular continued fraction x is said to be restricted, or composed of restricted partial quotients, if the sequence of denominators of its partial quotients is bounded; that is

The square root of 5 is the positive real number that, when multiplied by itself, gives the prime number 5. It is more precisely called the principal square root of 5, to distinguish it from the negative number with the same property. This number appears in the fractional expression for the golden ratio. It can be denoted in surd form as:

The Rogers–Ramanujan continued fraction is a continued fraction discovered by Rogers (1894) and independently by Srinivasa Ramanujan, and closely related to the Rogers–Ramanujan identities. It can be evaluated explicitly for a broad class of values of its argument.

The decimal value of the natural logarithm of 2 is approximately

Hermite's problem is an open problem in mathematics posed by Charles Hermite in 1848. He asked for a way of expressing real numbers as sequences of natural numbers, such that the sequence is eventually periodic precisely when the original number is a cubic irrational.

In mathematics, infinite compositions of analytic functions (ICAF) offer alternative formulations of analytic continued fractions, series, products and other infinite expansions, and the theory evolving from such compositions may shed light on the convergence/divergence of these expansions. Some functions can actually be expanded directly as infinite compositions. In addition, it is possible to use ICAF to evaluate solutions of fixed point equations involving infinite expansions. Complex dynamics offers another venue for iteration of systems of functions rather than a single function. For infinite compositions of a single function see Iterated function. For compositions of a finite number of functions, useful in fractal theory, see Iterated function system.