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

${\displaystyle x=a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{\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 [a₀, 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, ${\displaystyle {\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

${\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, a₀ = a_m 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 [1; 1, 1, 1, ...] of the golden ratio φ is purely periodic, while the regular continued fraction [1; 2, 2, 2, ...] of ${\displaystyle {\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

${\displaystyle x=[0;{\overline {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=[0;{\overline {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, b² − 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 P² − 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 a_i in the expansion is less than 2√D, and that the length of the repeating block is less than 2D.

More recently, sharper arguments ^[5][6][7] based on the divisor function have shown that the length of the repeating block for a quadratic surd of discriminant D is on the order of ${\displaystyle {\mathcal {O))({\sqrt {D))\ln {D}).}$

Canonical form and repetend

The following iterative algorithm ^[8] 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 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₀,^[9] which is easier to implement.

The expansion will repeat from then on. The sequence [a₀; a₁, a₂, a₃, ...] 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 m₀ = 0; d₀ = 1; and a₀ = 10 (10² = 100 and 11² = 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, m₁ = 10; d₁ = 14; and a₁ = 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, m₂ = 4; d₂ = 7; and a₂ = 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 A010179 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 {\begin{aligned}{\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 ))))))\end{aligned))}$

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

${\displaystyle {\begin{aligned}{\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{aligned))}$

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 {\begin{aligned}{\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{aligned))}$

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