Continued fractions and the golden ratio
Tonight's idea
A way of writing numbers built for finding their best fractions. Take \(415/93\). It is \(4\) and a bit: \(415 = 4 \times 93 + 43\). Flip the leftover: \(93/43 = 2 + 7/43\). Flip again: \(43/7 = 6 + 1/7\). Flip once more: \(7\). Done:
\[\frac{415}{93} = 4 + \cfrac{1}{2 + \cfrac{1}{6 + \cfrac{1}{7}}} = [4; 2, 6, 7].\]
That is a continued fraction. The steps are Euclid's algorithm, so it always finishes for a fraction. For an irrational number it never finishes:
\(\sqrt2 = [1; 2, 2, 2, \ldots]\), \(\quad \varphi = [1; 1, 1, 1, \ldots]\), \(\quad \pi = [3; 7, 15, 1, 292, \ldots]\).
Stop after the first one, two, three, … terms and simplify the fraction you have: those are the convergents. Each convergent \(p/q\) is closer to the number than any fraction with a smaller denominator: the champion approximations.
Why \(355/113\) is so good: the convergents of \(\pi\) are \(3, \tfrac{22}{7}, \tfrac{333}{106}, \tfrac{355}{113}\). If the next term is \(a\), the error is less than \(1/(a q^2)\): a big term coming up means the convergent before it is unusually good. After \(355/113\) comes \(292\), so it matches \(\pi\) to six decimals. The golden ratio's terms are all 1s, the smallest possible: it is the number fractions approach most reluctantly.
Watch one: the continued fraction of \(\sqrt2\)
\(\sqrt2 = 1.414\ldots\), so the first term is \(1\) and the leftover is \(\sqrt2 - 1\). Flip it, multiplying top and bottom by \(\sqrt2 + 1\):
\[\frac{1}{\sqrt2 - 1} = \frac{\sqrt2 + 1}{2 - 1} = \sqrt2 + 1 = 2.414\ldots\]
Next term \(2\), leftover \(\sqrt2 - 1\) again, forever: \(\sqrt2 = [1; 2, 2, 2, \ldots]\). Convergents come from a rule: new top = term × previous top + the top before that, and the same for bottoms. The first two convergents are \(1\) and \(1 + \tfrac12 = \tfrac32\), so start with tops \(1, 3\) and bottoms \(1, 2\). Every later term is \(2\): tops \(2 \times 3 + 1 = 7\), \(2 \times 7 + 3 = 17\), then \(41\); bottoms \(2 \times 2 + 1 = 5\), \(2 \times 5 + 2 = 12\), then \(29\). And \(\tfrac{41}{29} = 1.41379\), against \(\sqrt2 = 1.41421\).
Your turn
- Find the continued fraction of \(649/200\) and write out its convergents. (Four terms; the last convergent is the fraction itself.)
- Use the rule with the terms of \(\pi\), \([3; 7, 15, 1, 292]\), to produce the convergents \(3, \tfrac{22}{7}, \tfrac{333}{106}, \tfrac{355}{113}\). How far is \(\tfrac{22}{7}\) from \(\pi = 3.14159265\)? And \(\tfrac{355}{113}\)?
- Prove that \([1; 1, 1, 1, \ldots] = \varphi\). Call it \(x\), explain why \(x = 1 + \tfrac1x\), and solve. Then do \([2; 2, 2, \ldots]\) the same way.
- A year is \(365.2422\) days. Write \(0.2422\) as a continued fraction (four terms) and find its convergents. Which one is the Julian rule of one leap day every 4 years? Which convergent would be a better rule?
Stretch: why convergents are champions
Write the \(n\)-th convergent as \(p_n/q_n\). Check that \(p_{n+1}q_n - p_nq_{n+1} = \pm 1\) for \(\tfrac32, \tfrac75\) and for \(\tfrac{22}{7}, \tfrac{333}{106}\). The number \(x\) lies between consecutive convergents. Deduce \(\left|x - \tfrac{p_n}{q_n}\right| \lt \dfrac{1}{q_n q_{n+1}} \lt \dfrac{1}{q_n^2}\).
Answers
- \(649 = 3 \times 200 + 49\); \(200 = 4 \times 49 + 4\); \(49 = 12 \times 4 + 1\); \(4 = 4 \times 1\). So \([3; 4, 12, 4]\), convergents \(\tfrac31, \tfrac{13}{4}, \tfrac{159}{49}, \tfrac{649}{200}\).
- Tops \(3, 22, 333, 355\); bottoms \(1, 7, 106, 113\). \(\tfrac{22}{7} = 3.142857\), off by \(0.00126\). \(\tfrac{355}{113} = 3.14159292\), off by \(0.00000027\): nearly 5000 times better for a denominator 16 times bigger, because the next term is 292.
- Everything after the first \(1 +\) is the whole fraction again, so \(x = 1 + 1/x\), \(x^2 - x - 1 = 0\), \(x = \tfrac{1 + \sqrt5}{2}\). For \([2; 2, 2, \ldots]\): \(y = 2 + 1/y\), \(y^2 - 2y - 1 = 0\), \(y = 1 + \sqrt2\).
- \(0.2422 = \tfrac{1211}{5000} = [0; 4, 7, 1, 3, \ldots]\), convergents \(\tfrac14, \tfrac{7}{29}, \tfrac{8}{33}, \tfrac{31}{128}\). \(\tfrac14\) is the Julian rule (too many leap days: it drifts a day every 128 years). \(\tfrac{8}{33}\), 8 leap years in every 33, is more accurate than the Gregorian 97 in 400, and was proposed by Omar Khayyam's calendar committee in 1079.
Stretch. \(7 \times 2 - 3 \times 5 = -1\); \(333 \times 7 - 22 \times 106 = -1\). Since \(x\) lies between the two convergents, its distance to \(\tfrac{p_n}{q_n}\) is less than the gap between them, which is \(\left|\tfrac{p_{n+1}}{q_{n+1}} - \tfrac{p_n}{q_n}\right| = \dfrac{1}{q_n q_{n+1}}\), and \(q_{n+1} \gt q_n\). A random fraction with denominator \(q\) is only guaranteed to be within \(1/(2q)\).