Maths in a minute: 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. Incidentally, $\phi$ is the number known as the golden ratio. The continued fractions of other irrational numbers, such as $\sqrt2$ , also reveal hidden patterns:

$\sqrt2 = 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.

Comments

Continued fractions

Use a matrix to evaluate successive partial values of for phi:

[[0 1],[1 1]]

or root 2:

[[0 1],[1 2]]

or root N:

[[0 (N-(n'*n'))],[0 2n']] (where root n' is the nearest perfect square less than N)

Note that the first row vector of this matrix takes the second entry of the previous result and moves it up to the first entry of the new result (and scales it by a 'factor' measuring the difference from the nearest square in the case general square root). This gives a fraction a/b in the form of the output vector [a b] that, added to n' approximates a square root by an improper fraction, n' + (a/b)

This adapts the method of pure partial fractions. See wikipedia article https://en.wikipedia.org/wiki/Continued_fraction#Generalized_continued_… for the motivation.

Continued Phractions

I entered Rachel's continued fraction for Phi as 1+(1/(1+(1/(1+(1/(1+(1/(1+(1/(1+(1/(1+1)))))))))))) into Wolfram Alpha and got the fraction 34/21, two successive Fibonacci numbers, which I found very satisfying and exciting. Rachel's formulation had 13 "1"s, and 13 is the number before 21 in Fibonacci. The 13th "1" right at the bottom of Rachel's continued fraction pile has a plus sign and three dots after it, but to make my formulation suitable for Wolfram I put another "1" after that last plus sign instead, to seal it as it were rather than leave it open.

Anyway, I'm very interested in sequences similar to Fibonacci, especially for their potential to model natural structures and processes at least as well as Fibonacci's does, including those which differ minimally from the Fibonacci recurrence formula a(n) = a(n-1) + a(n-2). There's one known as Narayana's cows (OEIS A000930) whose recurrence has a "3" at the end instead of a "2", that is a(n) = a(n-1) + a(n-3) and has a ratio constant of roughly 1.4656, which I call the Bovine ratio, symbolised by the Greek(ish) letter Moo. Can anyone formulate the continued fraction for that ratio as Rachel did for Phi?