Continued fractions

The history of continued fractions can be traced back to an algorithm of Euclid. Let us recall this algorithm. Suppose we would like to find the greatest common divisor of numbers 75 and 33.

\begin{displaymath}\begin{array}{ll}\vspace{1ex}\vspace{2ex}75=2\cdot 33+9\qq......+\displaystyle\frac{1}{1+\displaystyle\frac{1}{2}}}\end{array}\end{displaymath}

The last non-zero remainder, 3 in our case, is the greatest common divisor of 75 and 33.

There is no evidence though that Greeks knew about the connection between the left column and the right column above. The first continued fraction was used in 1572 by Bombelli to approximate $\sqrt{13}$. The first infinite continued fraction appears in 1659 in the work of Lord Brouncker to expand $4/\pi$. It is Euler’s systematic development of the theory starting in 1737 that showed the value of the notion for both number theory and analysis. A torrent of results followed. In 18th and 19th centuries everybody who was anybody in mathematics contributed.

If the number is rational the continued fraction terminates like for $75/33$. If the number is irrational the continued fraction goes on forever. For example, for the irrational number $\sqrt{2}$ we can execute the Euclidean algorithm, in essence looking for the greatest common divisor of $\sqrt{2}$ and $1$. The algorithm will never terminate since the two numbers are incommensurate.

\begin{displaymath}\sqrt{2}=1+0.41421356\ldots=1+\frac{1}{2.41421356\ldots}=\end{displaymath}

\begin{displaymath}1+\frac{1}{2+0.41421356\ldots}=1+\frac{1}{2+\displaystyle\frac{1}{2+0.41421356\ldots}}\end{displaymath}

\begin{displaymath}=1+\frac{1}{2+\displaystyle\frac{1}{2+\displaystyle\frac{1}{2+0.41421356\ldots}}}=\ldots\vspace{2ex}\end{displaymath}

concluding

\begin{displaymath}\sqrt{2}=1+\frac{1}{2+\displaystyle\frac{1}{2+\displaystyle\frac{1}{2+\displaystyle\frac{1}{\displaystyle\ddots}}}}\end{displaymath}

The esthetic beauty of continued fractions may go some ways towards justifying the significance of some numbers from algebra or geometry. The continued fraction expansion

\begin{displaymath}\tau=1+\frac{1}{1+\displaystyle\frac{1}{1+\displaystyle\frac{1}{1+\displaystyle\frac{1}{\displaystyle\ddots}}}}\end{displaymath}

would suggest that the number $\tau=(1+\sqrt{5})/2$ has some significance. In fact, this number is none other than the “golden ratio”.

If we terminate the infinite continued fraction for the irrational number $\alpha $ at the $n$th step we will obtain a rational approximation $\alpha _n$ to $\alpha $. The rational number $\alpha _n$ is called the $n$th convergent for $\alpha $. For example, the first 4 convergents to numbers $\sqrt{2}$ and $\pi$ are

\begin{displaymath}\begin{array}{ll}\vspace{1ex}\vspace{2ex}\alpha =\sqrt{2}=......splaystyle\frac{1}{1+\displaystyle\frac{1}{292}}}}\end{array}\end{displaymath}

The name convergent comes from the fact that convergents do converge to the number. For example,

\begin{displaymath}\alpha -\alpha _4\approx 4.2\;10^{-4} \qquad \pi-\pi_4\approx 5.8\;10^{-10}\end{displaymath}

Here is the graph for $\sqrt{2}$.

\includegraphics {plot1.ps}We see that convergents alternately lie above and below the exact value of $\sqrt{2}$.

Here is the graph for $\pi$.

\includegraphics {plotpi1.ps}We see the same alternating pattern of approximation. In fact, this is true in general for any number.

The speed of convergence of continued fractions to a number they represent varies from number to number (but it is always very very fast). Here is a comparison between the convergence errors for $\sqrt{2}$ (blue) and $\pi$ (red).

\includegraphics {error.ps}The continued fraction expansions have many remarkable properties. We will be interested mainly in its approximating power relevant for the design of a good calendar system. It turns out that the convergents$\alpha _n$ for the irrational number $\alpha $ have superior approximating properties. The following definition makes it precise what we mean by a good approximation.

Definition 1   The fraction$p/q$ is called a good approximation for $\alpha $ if for any $q'<q$ and any integer $p'$ we have $\vert q\alpha -p\vert<\vert q'\alpha -p'\vert$.

\includegraphics {plot2.ps}The good approximations occur when q=2, 5, 12 and 29. The next good approximation occurs when q=70.

\includegraphics {plotpi.ps}The good approximations occur at q=7, 106 and 113. The next good approximation does not occur before q=33,102.

Observe that the numbers $q$ are exactly the denominators in the convergents for $\sqrt{2}$ and $\pi$ respectively. This is not an accident and holds in general for all convergents and for all numbers $\alpha $. We state it precisely and unambiguously in the form of a Theorem.

THEOREM 1   Every convergent $\alpha _n$ is a good approximation (in the sense of Definition 1) for$\alpha $ and conversely, every good approximation to $\alpha $ is one of the numbers $\alpha _n$ for some $n\ge 1$. In fact $q_n$ is the smallest integer $q>q_{n-1}$ such that $\vert q\alpha -p\vert<\vert q_{n-1}\alpha -p_{n-1}\vert$ for some integer $p$. We also have the inequalities

\begin{displaymath}\mbox{${\displaystyle\frac{1}{2q_{n+1}}}$}<\vert q_n\alpha -p_n\vert\le\mbox{${\displaystyle\frac{1}{q_{n+1}}}$}.\end{displaymath}The proof of the theorem is given in the book of Serge Lang. It is not very difficult to follow Lang’s proof but quite tricky to discover it on your own. Christian Huygens was the first to describe the sense in which coninued fractions give the best approximations of real numbers.

Now that you know that continued fractions are very good at approximating numbers rational and irrational, it is not surprising to find them in many unusual (at first glance) places. Looking deeper at continued fractions you would discover many amazing properties of these objects. We can say that there is music in continued fractions. But also there are continued fractions in music. Armed with continued fractions we return to the calendar and discover how continued fractions can explain more or less any calendar system ever proposed or implemented.

Next: Calendar and continued fractions        Previous: Very brief history

Yury Grabovsky 2000-03-03