Continued Fraction Explorer

A decimal is a clumsy way to hold a number. It goes on for ever for a third, and it hides the fact that 3.142857 is almost exactly 22/7. A continued fraction holds the same number in a different currency, and in that currency the good fractions are not hidden at all. They are the first things you see.

Divide, keep, flip, repeat

The recipe has one step, used over and over. Take the whole part of the number and write it down. If anything is left, turn the leftover upside down, which gives a number larger than one, and start again. The list of whole parts is the expansion, written with a semicolon after the first: 415/93 becomes [4; 2, 6, 7].

For a fraction this is the oldest procedure in the book. Euclid’s Elements, around 300 BCE, contains the algorithm for the greatest common divisor, and the quotients that appear along the way in its modern form are exactly these terms. The name is younger: John Wallis introduced the term “continued fraction” in 1695, and Leonhard Euler gave the first broad account of the theory in 1737.

Stop the expansion early and fold it back up, and you get an ordinary fraction called a convergent. The first few terms for pi are 3, 7, 15, 1 and 292. Folding up one, two, three and four of them gives 3, then 22/7, then 333/106, then 355/113. Each is a better fraction than the last, and each is in lowest terms without any cancelling.

Three facts about convergents make them worth the trouble. They take turns: the first is too small, the second too large, and so on, closing in from both sides. The gap between a convergent and the true value is less than one over the product of its own denominator and the next one. And two neighbours, cross-multiplied and subtracted, always give plus or minus one.

That middle fact is the useful one. A large term in the expansion means the next denominator is much bigger, so the convergent just before it is unusually accurate for its size. In pi the term after 3, 7, 15, 1 is 292. That is the whole secret of 355/113.

Why 355/113 is so hard to beat

Zu Chongzhi, a Chinese astronomer and mathematician born in 429, showed that pi lies between 3.1415926 and 3.1415927 and gave 355/113 as a fraction for it. The fraction is correct to six decimal places. In Chinese writing it is known as the close ratio, and it overshoots pi by less than 1/3,748,629.

How good is that for a three-digit denominator? No fraction with a denominator of four digits or fewer comes closer. Going up through the denominators one at a time, the next fraction that beats it is 52163/16604. A denominator about 150 times larger buys almost nothing, which is what a term of 292 looks like from the outside.

“Best” needs care, because there are two meanings in use and they give different lists. A fraction is a best approximation of the first kind if it is closer to the number than any other fraction with the same or a smaller denominator. It is best of the second kind if the denominator times the number, minus the numerator, is smaller than for any such rival. The second test is stricter.

Aleksandr Khinchin’s short book Continued Fractions, first published in 1936, is the reference usually cited for the two definitions and for what follows from them. Best approximations of the second kind are exactly the convergents. Those of the first kind include the convergents but also some in-between fractions, called semiconvergents, made by cutting the last term down.

The number e shows the difference. Its expansion follows a rule, 2; 1, 2, 1, 1, 4, 1, 1, 6 and so on, and its best approximations of the second kind start 3, 8/3, 11/4, 19/7, 87/32. The first kind adds 5/2, 49/18 and 68/25 to that list. Those extras are closer than anything smaller, but they are not convergents, and calling them so is a common slip.

The numbers that resist, and the numbers that repeat

If large terms make a number easy to approximate, small terms make it hard, and the smallest possible term is one. The golden ratio is [1; 1, 1, 1, …], all ones for ever. Its convergents are ratios of neighbouring Fibonacci numbers, and they creep toward it as slowly as any expansion can.

Hurwitz’s theorem makes this precise. Every irrational number has infinitely many fractions m/n within one over the square root of five times n squared. For the golden ratio that constant cannot be improved: ask for anything tighter and only finitely many fractions qualify. It is, in a measurable sense, the number furthest from the fractions.

Square roots behave differently again. The square root of 14 is [3; 1, 2, 1, 6, 1, 2, 1, 6, …], with the block 1, 2, 1, 6 repeating without end. Euler proved that any repeating expansion belongs to a root of a quadratic equation, and in 1770 Lagrange proved the converse: every such root repeats.

The repeating block of a square root has a shape. All of it but the last term reads the same forwards and backwards, and the last term is twice the whole part: 1, 2, 1 and then 6 for the root of 14. The result was known to Lagrange and follows from two theorems of Galois about mirror-image blocks. The lengths vary wildly, from one term for the root of 2 to eleven for the root of 61.

Because the terms of a square root come from a recurrence on whole numbers, they can be computed with no rounding at all. When the recurrence returns to a state it has been in before, the period is not merely observed. It is proved, since from that point the arithmetic can only retrace its steps.

A worked example, and a warning about digits

Type 3.14159 and treat it as the exact fraction it writes, 314159/100000. The expansion is [3; 7, 15, 1, 25, 1, 7, 4] and it ends, as every fraction’s does. The first four terms match pi. The fifth is 25, where pi has 292.

Nothing went wrong in the arithmetic. The number typed simply is not pi, and from the fifth term on the expansion describes the typed number’s own tail. The honest question is which terms the digits actually settle. Any number whose decimals begin 3.14159 lies in a narrow band, and expanding both edges of that band shows they agree on 3 and 7 and then part ways, one edge saying 15 and the other 16.

So five decimals of pi fix two terms, not seven. This is the main thing the method cannot do: it cannot conjure terms that the given precision does not contain, and rounded arithmetic adds a second trap. Divided in ordinary floating point, 2.9999999999999999999999 comes out as 3, the first term is wrong, and every later term is nonsense. Exact whole-number arithmetic avoids that trap. Only more digits fix the first problem.

Gears, calendars and tuning

The practical use is always the same: a ratio is wanted, and only small whole numbers are allowed. Achille Brocot, a French clockmaker, described in 1861 a tree of fractions for designing gear trains close to a wanted ratio, three years after the number theorist Moritz Stern had published the same structure. Every positive fraction appears in it exactly once, and each is formed from two neighbours by adding numerators and adding denominators, the mediant familiar from the sequences named after John Farey.

Walking down that tree toward a number is the continued fraction in slow motion. The terms count the steps taken right, then left, then right again, and the convergents are the corners where the walk turns. A gear designer with a limit on tooth counts stops at the last fraction that fits.

Calendars are the same problem. The mean tropical year at the start of 2000 was 365.2421897 days, a figure that drifts slowly. The fraction of a day expands to 1/4, then 7/29, 8/33 and 31/128: leap days per span of years. The Gregorian rule uses 97 in 400, which is not on that list and sits a little further from that value than 8/33 does. Its rule is stated in centuries: every fourth year, except century years not divisible by 400.

Music has it too. Twelve equal semitones put the fifth at two to the power seven twelfths, an irrational number whose second convergent is 3/2, the pure fifth. The two differ by about two hundredths of a semitone. The major third is less lucky: its pure ratio 5/4 is also a convergent, but the tempered third sits nearly fourteen hundredths of a semitone away.

None of these fractions is the number. Each is the closest that a given size allows, and the continued fraction is the tool that says, exactly and with a stated error, what that size buys.