Continued fraction

A simple continued fraction recursively expands a real number by taking integer parts and reciprocals. Its convergents are exceptionally good rational approximations.

Given consecutive continued fraction convergents $p_{k-1}/q_{k-1}$ and $p_k/q_k$, the intermediate fractions $(t{p}_k+p_{k-1})/(t{q}_k+q_{k-1})$ for $1\le t\le a_{k+1}$ are semiconvergents, where $a_{k+1}$ is the next partial quotient. The endpoint is the next convergent. These fractions matter in best rational approximation when a denominator bound cuts between consecutive convergents.

For a quadratic irrational $\sqrt{D}$, write its complete quotient as $(\sqrt{D}+m_j)/d_j$. The recurrence $m_{j+1}=d_j{a}_j-m_j$, $d_{j+1}=(D-m_{j+1}^2)/d_j$, $a_{j+1}=\lfloor (\sqrt{D}+m_{j+1})/d_{j+1}\rfloor$ computes its continued fraction. For $D=19$, the successive pairs after the initial quotient are $(4,3),(2,5),(3,2),(3,5),(2,3),(4,1)$, and then the cycle repeats. They give the displayed period of length six.

The finite negative continued fraction isFor $a_i\ge 2$, it describes a negative-framed chain of unknots: the diagonal framings are $-a_i$ and adjacent linking numbers are one. Repeated slam-dunk moves give rational surgery coefficient $-[a_1,\dots ,a_r{]}^{-}$. The corresponding chain matrix is negative definite. To check this, the successive determinants of its negative have recurrence $d_j=a_j{d}_{j-1}-d_{j-2}$, starting with $d_0=1$, $d_1=a_1$; they are positive and increasing, so Sylvester's criterion applies.

A continued fraction $[a_0;a_1,a_2,\dots ]$ with integer $a_0$ and positive integer $a_j$ for $j\ge 1$. Its partial numerators are all one. The continued fraction convergents have the standard two-term numerator and denominator recurrences.

The map $T(x)=1/x-\lfloor 1/x\rfloor$ on $(0,1]$, with $T(0)=0$. Its digit $N(x)=\lfloor 1/x\rfloor$ gives the successive partial quotients $N(T^{j}x)$ of a continued fraction. This is distinct from the geometric Gauss map assigning surface normals.

On each branch with digit $a=\lfloor 1/x\rfloor$, the displayed extension of the Gauss continued-fraction map is invertible almost everywhere: $x=(a+x^{\prime }{)}^{-1}$ and $y=(y^{\prime }{)}^{-1}-a$, with $a=\lfloor 1/y^{\prime }\rfloor$. Its invariant joint probability density function is $[(\log 2)(1+xy{)}^2{]}^{-1}$. The branch Jacobian determinant is $[x^2(a+y{)}^2{]}^{-1}$, which cancels the transformation of $1+xy$. Integrating out $y$ gives the Gauss measure density.

The inverse branch of the $n$th iterate of the Gauss continued-fraction map on a fixed digit cylinder has the displayed form, with continued fraction convergents $p_j/q_j$. Its derivative has absolute value $(q_n+q_{n-1}y{)}^{-2}$. Since $q_{n-1}\le q_n$, the maximum-to-minimum derivative ratio is at most four. The density of the Gauss measure changes this ratio by at most a further factor two. The cylinders shrink to irrational points, so this uniform distortion bound and the Lebesgue density theorem prove ergodicity of the map.

The invariant measure for the Gauss continued-fraction map with density $1/[(\log 2)(1+x)]$ on $[0,1]$. Inverse branches $x=1/(n+y)$ give transformed density $(\log 2{)}^{-1}{\sum }_{n\ge 1}[(n+y{)}^{-1}-(n+y+1{)}^{-1}]$, which telescopes to the same density.

For a simple continued fraction, the complete quotients satisfy ${\theta }_0=x$, $a_n=\lfloor {\theta }_n\rfloor$ and ${\theta }_{n+1}=1/({\theta }_n-a_n)$ whenever the denominator is nonzero. Thus ${\theta }_n=[a_n;a_{n+1},\dots ]$.

Starting from $x_0=x>0$, definewhenever $x_n$ is not an integer. This produces $x=[a_0;a_1,a_2,\dots ]$.

A simple continued fraction terminates exactly when its value is rational. For a reduced rational $p/q$, each reciprocal step is one step of the Euclidean algorithm and replaces the denominator by a strictly smaller nonnegative remainder.

Truncating a simple continued fraction gives a convergent; sufficiently accurate rational approximations with bounded denominator occur among these convergents.

Between consecutive continued fraction convergents, intermediate convergents have the form $(t{p}_{k-1}+p_{k-2})/(t{q}_{k-1}+q_{k-2})$ for $1\le t\le a_k$. The final value $t=a_k$ is the next convergent.

For nonsquare $N>1$, write the complete quotients after the initial term as $(\sqrt{N}+m)/d$. They exceed one, while their algebraic conjugates lie between minus one and zero. Thus $d<\sqrt{N}+m<2\sqrt{N}$. Comparing coefficients in $\sqrt{N}=(p_k{\alpha }_{k+1}+p_{k-1})/(q_k{\alpha }_{k+1}+q_{k-1})$ gives $p_k^2-N{q}_k^2=d_{k+1}(p_k{q}_{k-1}-q_k{p}_{k-1})$, and the last determinant has absolute value one. These small residues are useful candidates for smooth numbers in congruence-of-squares factorization.

A rational $p/q$ is a best approximation of the second kind to $\alpha$ when $|q\alpha -p|$ is no larger than $|b\alpha -a|$ for every competing rational $a/b$ with $0<b\le q$. Every simple continued-fraction convergent has this property.

With $M(a)=\left(\begin{array}{cc}a& 1\\ 1& 0\end{array}\right)$,

If $p_n/q_n=[a_0,\dots ,a_n]$, then appending a positive tail $x$ gives

Because each matrix $M(a)=\left(\begin{array}{cc}a& 1\\ 1& 0\end{array}\right)$ is symmetric, reversing the partial quotients transposes their product. If the convergents of $[a_0,\dots ,a_n]$ are $p_j/q_j$, then the last two convergents of $[a_n,\dots ,a_0]$ are

For positive $a_j,b_j$, define $p_0=a_0$, $p_{-1}=1$, $q_0=1$, $q_{-1}=0$ andThenand $p_n/q_n$ is the corresponding finite generalized continued fraction.

When $b_j=1$ and $a_j$ are positive integers, adjacent convergents satisfyEven and odd convergents are monotone from opposite sides, their separation is $1/(q_n{q}_{n+1})$, and $q_n\to \infty$. They therefore have a common limit $x$, with

If every $a_j=b_j=1$, then $p_n=F_{n+2}$ and $q_n=F_{n+1}$. Binet's formulashows that the convergents tend to $\varphi$ and gives sharp scaled errors through $F_{n+1}-\varphi F_n={\psi }^n$.

The Lagrange theorem says that a real number has an eventually periodic simple continued fraction exactly when it is a quadratic irrational.

The simple continued fraction of a quadratic irrational is eventually periodic. For a nonsquare positive integer $D$, the continued fraction of $\sqrt{D}$ is periodic after its integer part.

A continued fraction is purely periodic when its repeating block begins at its first partial quotient:

Let $\theta =[\overline{a_0,\dots ,a_n}]$, and let ${\theta }^{\prime }$ be its algebraic conjugate, the other fixed point of the Möbius transformation represented by $M(a_0)\cdots M(a_n)$. ThenThe identity follows by transposing the continued-fraction matrix and substituting $X=-1/Y$ in its fixed-point equation.

Successive complete quotients repeat after two steps:

Rationalizing successive complete quotients gives

If $p_n/q_n$ are the convergents of $\sqrt{11}$, then

For the even convergents of $\sqrt{11}$,Since the second factor has norm one, every such convergent satisfies $p_{2m}^2-11q_{2m}^2=-2$.