Continued fraction

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

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.

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.

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$.