Continued Fractions

Introduction to Continued Fractions#

Recall how we previously applied the Euclidean algorithm to the numbers $403$ and $286$:

$$\begin{align*} 403 &= 1 \times 286 + 117, \\ 286 &= 2 \times 117 + 52, \\ 117 &= 2 \times 52 + 13, \\ 52 &= 4 \times 13 + 0. \end{align*}$$

Suppose we divide each equation through by its original divisor;

$$\begin{align*} \frac{403}{286} &= 1 + \frac{117}{286}, \\ \frac{286}{117} &= 2 + \frac{52}{117}, \\ \frac{117}{52} &= 2 + \frac{13}{52}, \\ \frac{52}{13} &= 4. \end{align*}$$

Notice how the fraction on the left of each line is the reciprocal of the "remainder" fraction on the line before it; $\frac{286}{117}$ is $\frac{117}{286}$ flipped upside down, and so on. This means we can keep substituting each equation into the one above it:

$$\frac{403}{286} = 1 + \cfrac{1}{\frac{286}{117}} = 1 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{4}}}.$$

This nested expression is called a continued fraction.

Basically, we peel off the integer part $q_0$ of our number, leaving something between $0$ and $1$; flipping that leftover upside down gives a number bigger than $1$, so we can peel off its integer part $q_1$, and repeat forever (or until nothing is left over). The entries $q_i$ are called the partial quotients. Using this notation, the working above becomes

$$\frac{403}{286} = [1; 2, 2, 4].$$

It is important to remember that only $q_0$ is allowed to be zero or negative; every entry after the semicolon must be a positive integer.

Just like with base representations, we classify continued fractions by how their expansions end (or don't).

The $q_n \neq 1$ rule might look arbitrary, but without it every terminating continued fraction would have two different forms, since a final entry of $1$ can always be absorbed into the entry before it.

Example. Show that $[2;3,1]$ and $[2;4]$ represent the same number.

$$\begin{align*} [2;3,1] &= 2 + \cfrac{1}{3 + \cfrac{1}{1}} \\ &= 2 + \frac{1}{4} \\ &= \frac{9}{4}, \end{align*}$$

and clearly $[2;4] = 2 + \frac{1}{4} = \frac{9}{4}$ as well. Therefore the two expansions agree, and the convention $q_n \neq 1$ tells us that $[2;4]$ is the correct (canonical) way to write $\frac{9}{4}$.

The Three Characterisation Theorems#

These three theorems are what make continued fractions such a strong representation; they can often store more information about a number in less space than any base $b$ expansion can.

Compare this with base representations, where some numbers get two expansions (recall $0.\overline{9} = 1$ in base $10$). For continued fractions, the $q_n \neq 1$ convention removes the only source of ambiguity, so every real number gets exactly one expansion.

This makes sense because the continued fraction expansion of a rational number is just the Euclidean algorithm in disguise (we will see this explicitly below), and the Euclidean algorithm always terminates.

Quadratic irrationals are numbers of the form $a + b\sqrt{d}$ with $a,b$ rational and $d$ a non-square positive integer; things like $\sqrt{2}$, $\sqrt{6}-2$ or $\frac{1+\sqrt{5}}{2}$. Notice the pattern shift compared to base expansions:

• In base $b$: terminating or periodic $\iff$ rational.
• Continued fractions: terminating $\iff$ rational, and periodic $\iff$ quadratic irrational.

So continued fractions climb one level higher; the "repeating" behaviour now captures a whole class of irrational numbers. A number like $\pi$, which is neither rational nor a quadratic irrational, must therefore have an expansion that never terminates and never repeats.

The algorithms in the rest of this note (continued fraction $\to$ number, and number $\to$ continued fraction) are well-defined in both directions, which is what justifies these theorems.

Converting Continued Fractions to Simple Fractions#

Terminating Continued Fractions#

To convert a terminating continued fraction to a simple fraction (an ordinary numerator over an integer denominator), we just write out the nested fraction and evaluate it from the bottom up.

Example. Write $[1;2,3,4]$ as a simple fraction.

$$\begin{align*} [1;2,3,4] &= 1 + \cfrac{1}{2 + \cfrac{1}{3 + \cfrac{1}{4}}} \\ &= 1 + \cfrac{1}{2 + \cfrac{1}{\frac{13}{4}}} \\ &= 1 + \cfrac{1}{2 + \frac{4}{13}} \\ &= 1 + \cfrac{1}{\frac{30}{13}} \\ &= 1 + \frac{13}{30} \\ &= \frac{43}{30}. \end{align*}$$

Therefore, $[1;2,3,4] = \frac{43}{30}$; a terminating expansion gave us a rational number, as the theorem promised.

Periodic Continued Fractions#

For a periodic continued fraction we cannot evaluate from the bottom up, because there is no bottom. Instead, we exploit the self-similarity of the repeating part:

• Set $x$ to be the periodic part of the continued fraction.
• Expand out the continued fraction representation of $x$ until another instance of $x$ appears further down the fractional chain.
• Replace that new instance with the variable $x$ again.
• Simplify the equation to produce a quadratic equation in $x$.
• Solve the quadratic (it will have up to two solutions) and choose the solution that matches $x$ (i.e. the one with the correct sign/size).
• Once the periodic part is known, resolve any non-periodic entries by simply evaluating the continued fraction.

Example. Write $[0;\overline{2,4}]$ as a simple fraction.
Let $x = [0;\overline{2,4}]$. Expanding the chain, the part after the $4$ is another copy of $x$;

$$x = \cfrac{1}{2 + \cfrac{1}{4 + x}}.$$

Now we simplify to a quadratic:

$$\begin{align*} x &= \cfrac{1}{\frac{2(4+x)+1}{4+x}} \\ x &= \frac{4+x}{2x+9} \\ x(2x+9) &= 4+x \\ 2x^2 + 9x &= 4 + x \\ 2x^2 + 8x - 4 &= 0 \\ x^2 + 4x - 2 &= 0 \\ x &= \frac{-4 \pm \sqrt{16+8}}{2} \\ x &= -2 \pm \sqrt{6}. \end{align*}$$

Since $x = 0 + \frac{1}{2 + (\text{something positive})}$, we know that $0 < x < \frac{1}{2}$, so we must choose the positive root. Therefore,

$$[0;\overline{2,4}] = \sqrt{6} - 2.$$

Note that this is still a "simple fraction" in the sense that it is a real numerator over an integer denominator, namely $\frac{\sqrt{6}-2}{1}$. It is also a quadratic irrational (a root of $x^2+4x-2$), exactly as the periodicity theorem predicts.

Example. Write $[1;3,\overline{2,4}]$ as a simple fraction.
This time the periodic part does not start immediately. Set $x = [\overline{2;4}]$, i.e. the repeating tail on its own;

$$x = 2 + \cfrac{1}{4 + \cfrac{1}{x}}.$$

Simplifying,

$$\begin{align*} x &= 2 + \cfrac{1}{\frac{4x+1}{x}} \\ x &= 2 + \frac{x}{4x+1} \\ x(4x+1) &= 2(4x+1) + x \\ 4x^2 + x &= 8x + 2 + x \\ 4x^2 - 8x - 2 &= 0 \\ 2x^2 - 4x - 1 &= 0 \\ x &= \frac{4 \pm \sqrt{16+8}}{4} \\ x &= 1 \pm \frac{\sqrt{6}}{2}. \end{align*}$$

Here $x$ starts with the partial quotient $2$, so $x > 2$ and we take the positive root; $x = 1 + \frac{\sqrt{6}}{2} = \frac{2+\sqrt{6}}{2}$.
Now we resolve the non-periodic entries by evaluating the rest of the chain, rationalising denominators as we go:

$$\begin{align*} [1;3,\overline{2,4}] &= 1 + \cfrac{1}{3 + \cfrac{1}{x}} \\ &= 1 + \cfrac{1}{3 + \frac{2}{2+\sqrt{6}}} \\ &= 1 + \cfrac{1}{3 + \frac{2(\sqrt{6}-2)}{(\sqrt{6}+2)(\sqrt{6}-2)}} \\ &= 1 + \cfrac{1}{3 + \frac{2(\sqrt{6}-2)}{2}} \\ &= 1 + \cfrac{1}{3 + \sqrt{6} - 2} \\ &= 1 + \frac{1}{1+\sqrt{6}} \\ &= 1 + \frac{\sqrt{6}-1}{(\sqrt{6}+1)(\sqrt{6}-1)} \\ &= 1 + \frac{\sqrt{6}-1}{5} \\ &= \frac{4+\sqrt{6}}{5}. \end{align*}$$

Therefore, $[1;3,\overline{2,4}] = \frac{4+\sqrt{6}}{5} \approx 1.28990$; again a quadratic irrational.

The Continued Fraction Algorithm#

To go the other way — converting any real number $\alpha$ into its continued fraction — we formalise the "peel off the integer part, then flip the leftover" idea. First find the integer part $q_0 = \lfloor \alpha \rfloor$ and the fractional part $r_0 = \{\alpha\} = \alpha - \lfloor \alpha \rfloor$, then iteratively do the same to the reciprocal of each fractional part:

$$\begin{aligned} \alpha &= q_0 + r_0 && \text{where } q_0 = \lfloor \alpha \rfloor \text{ and } r_0 = \{\alpha\}, \\ \frac{1}{r_0} &= q_1 + r_1 && \text{where } q_1 = \left\lfloor \frac{1}{r_0} \right\rfloor \text{ and } r_1 = \left\{ \frac{1}{r_0} \right\}, \\ \frac{1}{r_1} &= q_2 + r_2 && \text{where } q_2 = \left\lfloor \frac{1}{r_1} \right\rfloor \text{ and } r_2 = \left\{ \frac{1}{r_1} \right\}, \\ &\;\;\vdots && \;\;\vdots \\ \frac{1}{r_{n-1}} &= q_n + r_n && \text{where } q_n = \left\lfloor \frac{1}{r_{n-1}} \right\rfloor \text{ and } r_n = \left\{ \frac{1}{r_{n-1}} \right\}. \end{aligned}$$

The stopping conditions match the characterisation theorems:

• If $\alpha$ is rational, the process terminates at the $n$th step when $r_n = 0$, giving the terminating expansion $\alpha = [q_0; q_1, q_2, \dots, q_n]$.
• If $\alpha$ is a quadratic irrational, the process stops at the $n$th step when the fractional part $r_n$ has appeared earlier in the sequence, say $r_n = r_k$ for some $k < n$; from that point everything must repeat, giving the periodic expansion $\alpha = [q_0; q_1, \dots, q_k, \overline{q_{k+1}, \dots, q_n}]$.

Basically, the $r_i$ values are the "state" of the algorithm; if the state hits $0$ you are done, and if the state ever repeats then so will everything after it.

Rational Inputs#

Example. Write $\frac{151}{115}$ as a continued fraction.

$$\begin{aligned} \frac{151}{115} &= 1 + \frac{36}{115} && \text{where } q_0 = 1 \text{ and } r_0 = \tfrac{36}{115}, \\ \frac{1}{r_0} = \frac{115}{36} &= 3 + \frac{7}{36} && \text{where } q_1 = 3 \text{ and } r_1 = \tfrac{7}{36}, \\ \frac{1}{r_1} = \frac{36}{7} &= 5 + \frac{1}{7} && \text{where } q_2 = 5 \text{ and } r_2 = \tfrac{1}{7}, \\ \frac{1}{r_2} = \frac{7}{1} &= 7 + 0 && \text{where } q_3 = 7 \text{ and } r_3 = 0. \end{aligned}$$

Since $r_3 = 0$, the algorithm terminates. Therefore,

$$\frac{151}{115} = [1;3,5,7].$$

Notice that the partial quotients $1, 3, 5, 7$ are precisely the quotients from the Euclidean algorithm applied to $151$ and $115$;

$$\begin{align*} 151 &= 1 \times 115 + 36, \\ 115 &= 3 \times 36 + 7, \\ 36 &= 5 \times 7 + 1, \\ 7 &= 7 \times 1 + 0. \end{align*}$$

So for rational numbers you never actually need the fractional-part bookkeeping; just run the Euclidean algorithm on the numerator and denominator and read off the quotients.

Example. Write $-\frac{37}{11}$ as a continued fraction.
Here $-\frac{37}{11} \approx -3.36$, and the floor function always rounds down, so for a negative number $q_0$ becomes more negative — $q_0 = -4$, not $-3$. This keeps the fractional part positive, which is exactly what the definition requires.

$$\begin{aligned} -\frac{37}{11} &= -4 + \frac{7}{11} && \text{where } q_0 = -4 \text{ and } r_0 = \tfrac{7}{11}, \\ \frac{1}{r_0} = \frac{11}{7} &= 1 + \frac{4}{7} && \text{where } q_1 = 1 \text{ and } r_1 = \tfrac{4}{7}, \\ \frac{1}{r_1} = \frac{7}{4} &= 1 + \frac{3}{4} && \text{where } q_2 = 1 \text{ and } r_2 = \tfrac{3}{4}, \\ \frac{1}{r_2} = \frac{4}{3} &= 1 + \frac{1}{3} && \text{where } q_3 = 1 \text{ and } r_3 = \tfrac{1}{3}, \\ \frac{1}{r_3} = \frac{3}{1} &= 3 + 0 && \text{where } q_4 = 3 \text{ and } r_4 = 0. \end{aligned}$$

Therefore, $-\frac{37}{11} = [-4;1,1,1,3]$. Only the leading entry carries the minus sign; all the later partial quotients are still positive.

Irrational Inputs#

For irrational inputs we run the exact same algorithm, but we must work with exact surds and rationalise denominators at every step. Never round the surds to decimals midway through the algorithm; rounding errors quickly corrupt the later partial quotients. Decimal estimates are only used on the side, to decide what each floor is.

Example. Find the continued fraction expansion for $\sqrt{7}$.
Since $4 < 7 < 9$, we have $2 < \sqrt{7} < 3$, so $q_0 = 2$. From there, each step is: flip the fractional part, rationalise, and take the floor.

$$\begin{aligned} \sqrt{7} &= 2 + \left(\sqrt{7}-2\right) && q_0 = 2,\ r_0 = \sqrt{7}-2, \\ \frac{1}{r_0} = \frac{1}{\sqrt{7}-2} = \frac{\sqrt{7}+2}{3} &= 1 + \frac{\sqrt{7}-1}{3} && q_1 = 1,\ r_1 = \frac{\sqrt{7}-1}{3}, \\ \frac{1}{r_1} = \frac{3}{\sqrt{7}-1} = \frac{\sqrt{7}+1}{2} &= 1 + \frac{\sqrt{7}-1}{2} && q_2 = 1,\ r_2 = \frac{\sqrt{7}-1}{2}, \\ \frac{1}{r_2} = \frac{2}{\sqrt{7}-1} = \frac{\sqrt{7}+1}{3} &= 1 + \frac{\sqrt{7}-2}{3} && q_3 = 1,\ r_3 = \frac{\sqrt{7}-2}{3}, \\ \frac{1}{r_3} = \frac{3}{\sqrt{7}-2} = \sqrt{7}+2 &= 4 + \left(\sqrt{7}-2\right) && q_4 = 4,\ r_4 = \sqrt{7}-2. \end{aligned}$$

For instance, in the second line, $\frac{1}{\sqrt{7}-2} = \frac{\sqrt{7}+2}{(\sqrt{7}-2)(\sqrt{7}+2)} = \frac{\sqrt{7}+2}{3}$, and since $2 < \sqrt{7} < 3$ this lies between $\frac{4}{3}$ and $\frac{5}{3}$, so its floor is $1$; the other floors are decided the same way. Now $r_4 = \sqrt{7}-2 = r_0$, so the state has repeated and everything from $q_1$ onwards cycles. Therefore,

$$\sqrt{7} = [2;\overline{1,1,1,4}].$$

A periodic expansion, as expected, since $\sqrt{7}$ is a quadratic irrational.

Example. Find the continued fraction expansion for $\sqrt{2}$.
Since $1 < 2 < 4$, we have $1 < \sqrt{2} < 2$, so $q_0 = 1$.

$$\begin{aligned} \sqrt{2} &= 1 + \left(\sqrt{2}-1\right) && q_0 = 1,\ r_0 = \sqrt{2}-1, \\ \frac{1}{r_0} = \frac{1}{\sqrt{2}-1} = \sqrt{2}+1 &= 2 + \left(\sqrt{2}-1\right) && q_1 = 2,\ r_1 = \sqrt{2}-1. \end{aligned}$$

Already $r_1 = r_0$, so the expansion repeats immediately;

$$\boxed{\sqrt{2} = [1;\overline{2}] = [1;2,2,2,\dots].}$$

This is the shortest possible period, and it is worth memorising as the classic example of a periodic continued fraction.

Convergents#

Basically, a convergent is what you get by chopping off the expansion after the $n$th partial quotient and evaluating what remains; $c_0$ is just the integer part, and each further convergent uses one more entry, giving better and better rational snapshots of $\alpha$.

Example. Find the convergents of $\frac{151}{115} = [1;3,5,7]$.

$$\begin{align*} c_0 &= [1] = 1, \\ c_1 &= [1;3] = 1 + \frac{1}{3} = \frac{4}{3}, \\ c_2 &= [1;3,5] = 1 + \cfrac{1}{3 + \cfrac{1}{5}} = 1 + \frac{5}{16} = \frac{21}{16}, \\ c_3 &= [1;3,5,7] = \frac{151}{115}. \end{align*}$$

The last convergent of a rational number is just the number itself, so there is nothing to compute there.

Example. Find the first four convergents of $\sqrt{7} = [2;\overline{1,1,1,4}]$.

$$\begin{align*} c_0 &= [2] = 2, \\ c_1 &= [2;1] = 2 + \frac{1}{1} = 3, \\ c_2 &= [2;1,1] = 2 + \cfrac{1}{1 + \cfrac{1}{1}} = 2 + \frac{1}{2} = \frac{5}{2}, \\ c_3 &= [2;1,1,1] = 2 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{1}}} = 2 + \frac{2}{3} = \frac{8}{3}. \end{align*}$$

Unlike the rational case, this list never ends; we can keep taking convergents forever.

Convergents from the EEA#

Evaluating each convergent from scratch gets painful quickly; every new convergent means re-evaluating a whole nested fraction. The fix is that the convergents of any real number $\alpha$ appear amongst the entries of its extended Euclidean algorithm table. Since $\alpha$ might not be rational, we can no longer record the remainder row $r_i$, but we keep the $q_i$ row (which now holds the partial quotients) and generate the $x_i$ and $y_i$ rows exactly as before, seeded by the columns $(x,y) = (1,0)$ and $(0,1)$:

$$x_i = x_{i-2} - q_i \, x_{i-1}, \qquad y_i = y_{i-2} - q_i \, y_{i-1}.$$

Having done so, the $n$th convergent is given by

$$\boxed{c_n = -\frac{y_n}{x_n},}$$

where the $0$th convergent $c_0$ comes from the column containing the partial quotient $q_0$, and so on.

Example. Find the convergents of $\frac{151}{115} = [1;3,5,7]$ using the EEA.

For instance, $x_2 = x_0 - q_2 x_1 = 1 - 5(-3) = 16$ and $y_2 = y_0 - q_2 y_1 = -1 - 5(4) = -21$, so $c_2 = -\frac{-21}{16} = \frac{21}{16}$; these match the convergents we found by hand. Notice how the signs of $x_i$ and $y_i$ alternate down the rows, and the final column recovers $\pm(151, 115)$, i.e. the number itself.

Example. Find the first seven convergents of $\sqrt{7} = [2;\overline{1,1,1,4}]$.
The partial quotient row just keeps cycling through $1,1,1,4$ after the initial $2$:

So $c_7 = \frac{127}{48}$, and the whole list took a fraction of the effort of evaluating eight nested fractions.

This gives us a fairly efficient procedure for finding convergents of any real number $\alpha$:

• Find the first few (or all) entries in the continued fraction expansion of $\alpha$.
• Use these entries as the partial quotient row in a modified EEA table, and fill out the $x_i$ and $y_i$ rows.
• Read off the $n$th convergent as $c_n = -\frac{y_n}{x_n}$.

As a rule of thumb: if you only need one small convergent, bottom-up evaluation is fine; if you need several convergents (or high-index ones), always build the table. Also, if you ignore the alternating signs, the numerators and denominators of the convergents each satisfy the recurrence $a_n = q_n a_{n-1} + a_{n-2}$; you can see this in the table above, e.g. the denominators satisfy $14 = 4 \times 3 + 2$ and $48 = 1 \times 31 + 17$.

Convergents as Approximations#

As implied by their name, the convergents of a real number $\alpha$ are increasingly good approximations of $\alpha$. For $\sqrt{7} \approx 2.64575$, the convergents from the table above evaluate to

$$\begin{align*} c_0 &= 2, \\ c_1 &= 3, \\ c_2 &= \tfrac{5}{2} = 2.5, \\ c_3 &= \tfrac{8}{3} \approx 2.66667, \\ c_4 &= \tfrac{37}{14} \approx 2.64286, \\ c_5 &= \tfrac{45}{17} \approx 2.64706, \\ c_6 &= \tfrac{82}{31} \approx 2.64516, \\ c_7 &= \tfrac{127}{48} \approx 2.64583. \end{align*}$$

Notice how the convergents alternate around the target; the even-indexed ones sit below $\sqrt{7}$ and the odd-indexed ones sit above it,

$$c_0 < c_2 < c_4 < c_6 < \sqrt{7} < c_7 < c_5 < c_3 < c_1.$$

This is not a coincidence. Truncating the expansion throws away a positive tail, and that tail sits underneath some number of reciprocals; each extra reciprocal flips the direction of the error. So $c_0$ (a floor) always undershoots, $c_1$ overshoots, and so on, meaning $\alpha$ is always squeezed between any two consecutive convergents. This is a useful sanity check in exams: if your convergents do not alternate above and below the target, you have made an arithmetic mistake somewhere.

How good are these approximations? There is a precise answer.

Two things to take away from this bound. First, the error shrinks like $\frac{1}{x_n^2}$ — the square of the denominator — which is far better than truncating a decimal expansion (a decimal cut after denominator $10^k$ only guarantees an error of about $\frac{1}{10^k}$). Second, the $q_{n+1}$ out the front means that stopping just before a huge partial quotient gives an unusually good approximation; basically, a big entry says the tail contributes almost nothing, so the truncation was nearly free.

Example. Find the error bound for the $7$th convergent $c_7$ of $\sqrt{7}$.
From the table, $c_7 = \frac{127}{48}$, so $x_7 = 48$. The expansion is $[2;\overline{1,1,1,4}]$, so the partial quotient after $q_7$ is $q_8 = 4$. Therefore,

$$\begin{align*} \left|\sqrt{7} - \frac{127}{48}\right| &< \frac{1}{q_8 \, x_7^2} \\ &= \frac{1}{4 \times 48^2} \\ &= \frac{1}{9216}. \end{align*}$$

Therefore, $c_7$ is guaranteed to be within $\frac{1}{9216} \approx 0.000109$ of $\sqrt{7}$; the actual error is $\left|2.6457513\ldots - 2.6458\overline{3}\right| \approx 0.000082$, which indeed fits inside the bound.

Example. Find the first five convergents of $\sqrt{2} = [1;\overline{2}]$ and verify the error bound for $c_3$.
Since we want several convergents, we build the EEA table:

For $c_3 = \frac{17}{12}$ we have $x_3 = 12$ and $q_4 = 2$, so

$$\begin{align*} \left|\sqrt{2} - \frac{17}{12}\right| &< \frac{1}{q_4 \, x_3^2} \\ &= \frac{1}{2 \times 12^2} \\ &= \frac{1}{288}. \end{align*}$$

The actual error is $|1.414214\ldots - 1.41\overline{6}| \approx 0.00245$, comfortably inside the bound $\frac{1}{288} \approx 0.00347$. Also notice the alternation again: $1 < \frac{7}{5} < \frac{41}{29} < \sqrt{2} < \frac{17}{12} < \frac{3}{2}$.

Famous Approximations of Pi#

Example. Find the first few convergents of $\pi$.
$\pi$ is not a quadratic irrational, so its expansion never terminates or repeats and we must compute it numerically (with plenty of decimal places in reserve). Working with $\pi \approx 3.14159265359$:

$$\begin{aligned} \pi &= 3 + 0.14159265\ldots && q_0 = 3, \\ \frac{1}{r_0} &\approx 7.06251331 && q_1 = 7,\ r_1 \approx 0.06251331, \\ \frac{1}{r_1} &\approx 15.99659441 && q_2 = 15,\ r_2 \approx 0.99659441, \\ \frac{1}{r_2} &\approx 1.00341723 && q_3 = 1,\ r_3 \approx 0.00341723, \\ \frac{1}{r_3} &\approx 292.63459 && q_4 = 292. \end{aligned}$$

So $\pi = [3;7,15,1,292,\dots]$, and the convergents are

$$\begin{align*} c_0 &= 3, \\ c_1 &= [3;7] = 3 + \frac{1}{7} = \frac{22}{7}, \\ c_2 &= [3;7,15] = 3 + \cfrac{1}{7 + \cfrac{1}{15}} = 3 + \frac{15}{106} = \frac{333}{106}, \\ c_3 &= [3;7,15,1] = 3 + \cfrac{1}{7 + \cfrac{1}{16}} = 3 + \frac{16}{113} = \frac{355}{113}. \end{align*}$$

The convergent $c_1 = \frac{22}{7}$ is the primary-school approximation of $\pi$, with error bound

$$\left|\pi - \frac{22}{7}\right| < \frac{1}{q_2 \, x_1^2} = \frac{1}{15 \times 7^2} = \frac{1}{735}.$$

The convergent $c_3 = \frac{355}{113}$ is spectacular for its size, precisely because the next partial quotient is the enormous $q_4 = 292$;

$$\left|\pi - \frac{355}{113}\right| < \frac{1}{292 \times 113^2} = \frac{1}{3728548}.$$

Indeed, $\frac{355}{113} \approx 3.14159292$ while $\pi \approx 3.14159265$; seven correct significant figures from a three-digit denominator. Both $\frac{22}{7}$ and $\frac{355}{113}$ were known in ancient times, and no fraction with a smaller denominator beats $\frac{355}{113}$.

An Application: Designing a Calendar#

Example. A tropical year is approximately $365.24219$ days. Use continued fractions to decide how many leap years a calendar should have.
The whole problem is about approximating the fractional part $0.24219$ by a fraction $\frac{\text{leap years}}{\text{cycle length}}$ with a manageable denominator, which is exactly what convergents are best at. Running the algorithm numerically,

$$\begin{aligned} 0.24219 &= 0 + 0.24219 && q_0 = 0, \\ \frac{1}{r_0} &\approx 4.12899 && q_1 = 4,\ r_1 \approx 0.12899, \\ \frac{1}{r_1} &\approx 7.75256 && q_2 = 7,\ r_2 \approx 0.75256, \\ \frac{1}{r_2} &\approx 1.32880 && q_3 = 1,\ r_3 \approx 0.32880, \\ \frac{1}{r_3} &\approx 3.04140 && q_4 = 3. \end{aligned}$$

So $0.24219 \approx [0;4,7,1,3,\dots]$, with convergents

$$\begin{align*} c_1 &= [0;4] = \frac{1}{4} = 0.25, \\ c_2 &= [0;4,7] = \cfrac{1}{4 + \cfrac{1}{7}} = \frac{7}{29} \approx 0.24138, \\ c_3 &= [0;4,7,1] = \cfrac{1}{4 + \cfrac{1}{8}} = \frac{8}{33} \approx 0.24242, \\ c_4 &= [0;4,7,1,3] = \cfrac{1}{4 + \cfrac{4}{31}} = \frac{31}{128} \approx 0.24219. \end{align*}$$

The convergent $c_1 = \frac{1}{4}$ is the Julian calendar: one leap year every $4$ years, which drifts by a full day roughly every $128$ years. The convergent $c_4 = \frac{31}{128}$ says a calendar with $31$ leap years every $128$ years would drift by only a day every $400{,}000$ years or so. Interestingly, the Gregorian calendar we actually use ($97$ leap years every $400$ years, i.e. $0.2425$) is not a convergent, and drifts a day every $\approx 3200$ years; the continued fraction answer $\frac{31}{128}$ is both more accurate and uses a smaller denominator. The lesson: when you need the best fraction subject to a denominator budget, compute convergents rather than guessing.

The Golden Ratio#

The golden ratio is the irrational number $\phi = \frac{1}{2}\left(1+\sqrt{5}\right) \approx 1.61803$.
(a) Find the continued fraction expansion and the first few convergents of $\phi$.
(b) Find a general formula for the $n$th convergent of $\phi$.
(c) What is the expected error bound for the $n$th convergent of $\phi$?

(a). We run the continued fraction algorithm. Since $2 < \sqrt{5} < 3$, we have $\frac{3}{2} < \phi < 2$, so $q_0 = 1$.

$$\begin{aligned} \phi &= 1 + \frac{\sqrt{5}-1}{2} && q_0 = 1,\ r_0 = \frac{\sqrt{5}-1}{2}, \\ \frac{1}{r_0} = \frac{2}{\sqrt{5}-1} = \frac{2\left(\sqrt{5}+1\right)}{4} = \frac{\sqrt{5}+1}{2} &= 1 + \frac{\sqrt{5}-1}{2} && q_1 = 1,\ r_1 = \frac{\sqrt{5}-1}{2}. \end{aligned}$$

Already $r_1 = r_0$, so the expansion repeats immediately;

$$\boxed{\phi = [1;\overline{1}] = [1;1,1,1,\dots].}$$

There is also a slicker way to see this: $\phi$ satisfies $\phi^2 = \phi + 1$, so dividing by $\phi$ gives $\phi = 1 + \frac{1}{\phi}$, and substituting this identity into itself over and over spins out the all-ones expansion directly.
The first few convergents come from the EEA table with every partial quotient equal to $1$: