Plus Advent Calendar Door #10: Continued fractions

The fraction $22/7$ is a good approximation to the irrational number $\pi$: so much so that it is celebrated in Pi Approximation Day on 22 July. But have you ever wondered how to calculate rational approximations to irrational numbers?

The answer comes from continued fractions: these are a nested series of fractions that can reveal hidden properties of numbers. Any number can be written as a continued fraction. Rational numbers (including integers) can be written as finite continued fractions: for example $$ 3 = 3 $$ (which is admittedly not very interesting!) $$ \frac{22}{7} = 3+\frac{1}{7} $$ and $$ \frac{333}{106} = 3+\frac{1}{7+\frac{1}{15}}=3+\frac{15}{106}. $$ Irrational numbers have infinite continued fractions, and cutting these off after a finite number of levels gives you fractions that are close to the value of the irrational number. The fractions above are the first few such approximations to $\pi$, calculated from cutting off its infinite continued fraction: $$ \pi = 3+\frac{1}{7+\frac{1}{15+\frac{1}{1+\frac{1}{292+\ldots}}}}. $$ A fraction $p/q$ is a good approximation of an irrational number $x$ if there isn't a fraction that is closer to $x$ with a smaller denominator $q$. And the continued fraction expansion of an irrational number gives the best series of approximations in this sense, for an irrational number.

The first few approximations of $\pi$ produced in this way: $$ 3, 22/7, 333/106, 355/113 \mbox{ and } 103993/33102 $$ very quickly get close to the true value of $\pi$. Their differences from $\pi$ are approximately: $$ 0.141, 0.001, 0.0008, 0.0000003 \mbox{ and } 0.0000000006. $$

If you count the curves of seeds spiralling in a sunflower you'll find pairs (counting spirals curving left and curving right) that are (almost always) neighbours in the Fibonacci series, all approximations of $\phi$.

But not all approximations work so well for irrational numbers. For example, the approximations from the continued fraction of $\phi = 1.618...$ (the limit of the ratio of successive Fibonacci numbers – you can read more here) are: $$ \frac{1}{1}, \frac{2}{1}, \frac{3}{2}, \frac{5}{3}, \frac{8}{5},\ldots $$ These approximations, although the best there are, approach the true value for $\phi$ very slowly, with differences of around $0.618, 0.381, 0.118, 0.048$ and $0.018$ for those listed above. Irrational numbers with such useless approximations are called badly approximable. You can tell something is badly approximable if the numbers in its continued fraction are bounded (they don't ever exceed some fixed number) and this is a measure of how irrational they are. In fact, $\phi$ is the most irrational number, with the numbers in its continued fraction never exceeding 1: $$ \phi = 1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\ldots}}}}}}. $$ The continued fraction for $\phi$ reveals a beautiful pattern, despite the fact that it (and all irrational numbers) having messy infinite decimal expansions that do not tail off into any repeating patterns. The continued fractions of other irrational numbers, such as $\sqrt 2$, also reveal hidden patterns: $$ \sqrt 2 = 1+\frac{1}{2+\frac{1}{2+\frac{1}{2+\ldots}}}. $$ These patterns are beautiful, but result in these numbers being badly approximable. But $\pi$, with its excellent rational approximations, holds no such pattern in its continued fraction.

You can read more about continued fractions in John D Barrow's article, Chaos in Numberland: The secret life of continued fractions.

Return to the Plus advent calendar 2016.

This article comes from our Maths in a minute library.