Continued fractions
Named by 32 essays across 5 fields — each of them below, with the objects they name alongside it.
The oldest algorithm, drawn as a tiling
Euclid's method for finding a greatest common divisor is usually presented as a loop. It is also a way of tiling a rectangle with squares, and the tiling explains why it works.
The rectangle that eats itself
Cut a square off a golden rectangle and what is left is a golden rectangle. That single property is the whole of the golden ratio, and it explains both what the number really does and most of what is wrongly claimed for it.
A fraction that never closes
Euclid's algorithm throws away everything except the number of squares it peeled at each step. Those counts are a second name for the number it started from — one that terminates exactly when the ratio is a ratio.
Every fraction, exactly once
Take two fractions, add the tops and add the bottoms. That is not how fractions are added, it is not an average, and repeating it produces every positive rational exactly once, already in lowest terms.
How close a fraction can get
Drop eight points into seven boxes and two of them share. That one line, applied to the multiples of an irrational number, proves that every irrational has infinitely many astonishingly good rational approximations — and no construction is needed anywhere.
The square that cannot shrink
The usual proof that the square root of two is irrational is about even and odd numbers. There is a proof about squares instead, in which a supposed solution is folded into a smaller one — and the folding is a drawing.
Three gaps and no more
Turn a circle by the same irrational angle over and over. The points never repeat and never settle, and yet at every single stage the gaps they leave take at most three different lengths — never four, at any number of steps, for any angle.
One solution that makes all the others
The equation x² − 2y² = 1 has infinitely many whole-number solutions, and every one of them is a power of the smallest. The multiplication that produces them is what multiplying two numbers of the form a + b√2 comes to when the √2 terms are collected — so an equation about a hyperbola turns out to carry a group.
Approached too fast to be algebraic
An algebraic number of degree d cannot be approached by fractions faster than the denominator's dth power. So a number that is approached faster than that is the root of no polynomial at all — and one can be built by choosing where its decimal digits go.
How short a cycle could be
The drift argument cannot see cycles at all, which is why it is not a proof. What can see them is arithmetic — a cycle's shape has to be a fraction that approximates the logarithm of three to base two extraordinarily well, and there are very few such fractions.
The fractions that beat every smaller one
Walking down the tree towards a number produces a sequence of fractions closing in on it. Most of them are steps along the way; a few are the best approximations there are — closer than every fraction with a smaller denominator — and which few is decided by where the turns change direction.
The arcs a line crosses on its way to a number
Draw a semicircle over every pair of neighbouring fractions and the half-plane above the number line is cut into curved triangles that never overlap. A straight line dropped towards any number crosses those arcs one after another, and the arcs it crosses, and the side it leaves each triangle by, are exactly the steps of the Stern–Brocot descent towards that number.
The function that sends fractions to binary
The Stern–Brocot tree and the tree of binary fractions have exactly the same shape, so there is a function that sends each fraction to the binary fraction in the same position. It is continuous and increasing, it turns every quadratic irrational into an ordinary fraction, and it does all of its rising on a set of numbers so thin that at almost every point its slope is nought.
A method that is allowed to miss
Bhāskara's cyclic method solves x² − Dy² = 1 by aiming at the wrong target. It keeps a pair a, b with a² − Db² = k for some small k, combines it with a helper chosen so that k can be divided out, and repeats until k is 1. For D = 61 it reaches the ten-digit fundamental solution in 13 steps, where walking the convergents of √61 takes 22 — and for every D up to 100 it is faster.
Why the expansion has to repeat
The continued fraction of √61 runs 7; 1, 4, 3, 1, 2, 2, 1, 3, 4, 1, 14 and then starts again. It must: each step's state is a pair of whole numbers trapped in a small band, and only 14 pairs fit. The expansion of √61 visits 11 of them in a cycle, the other 3 form a cycle of their own, and the period reads the same backwards before its last term, which is twice the first.
The fraction Lambert built for the tangent
The first proof that π is not a fraction, from 1761, does not look at π at all. It writes the tangent as an endless continued fraction, shows that the fraction's value at any rational point other than zero cannot be rational — because its tails are trapped between nothing and one — and then notes that tan(π/4) = 1.
The pattern in e's continued fraction
Written as a continued fraction, e is 2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8 — two ones, then the next even number, for ever. Euler found the pattern and proved it with a differential equation. A proof from 2006 needs only three integrals, each of which turns out to be exactly the error of one of e's own convergents.
Sixty needs two digits and sixty-one needs ten
The smallest solution of x² − 60y² = 1 is x = 31. For x² − 61y² = 1 it is x = 1,766,319,049. The jump is not an accident of 61: the solution is exactly the product of one period's complete quotients, so its size is set by how long the continued fraction takes to come home — and for the cattle problem Archimedes is said to have posed, that product has 103,273 digits.
The player who meets the first long run
Turn Euclid's algorithm into a game: two players take turns cutting squares off the rectangle, any number from the current run, and whoever cuts the last one wins. The whole game is decided before it starts — by whether the ratio of the sides is more or less than the golden ratio, which is the same thing as how many runs of length one come first.
The diagonal no unit measures
Draw the five diagonals of a regular pentagon and they make a star with a smaller pentagon at its centre. Subtract the side from the diagonal and what is left is the smaller pentagon's diagonal; subtract that from the side and what is left is its side. The pentagon has handed back a smaller copy of itself, and it will do so for ever — which means no unit, however small, measures both the side and the diagonal an exact whole number of times.
Two counts that agree for no visible reason
Write 10 as a sum of whole numbers that differ from each other by at least two, and there are six ways. Write 10 as a sum of numbers that each leave 1 or 4 on division by 5, and there are six ways. The same happens for 20 (thirty-one each), for 40 (three hundred and seventy-four each), for every number anyone has checked and every number there is. The two lists look nothing alike, and no one has found a simple way to turn one into the other.
When minus one can be reached
x² − Dy² = 1 always has a solution. Put −1 on the right and it sometimes does and sometimes does not. A remainder rules out most D at a glance, every prime of the form 4k + 1 is guaranteed one, and between the two lies a set of D decided by arithmetic several layers deep — of which, a million numbers in, 78% are solvable, on the way to a limit of 58% that was proved only in 2022.
A cube root that looks like chance
The continued fraction of √61 repeats after eleven terms, and every square root's must. The cube root of 2 obeys no such law. Computed exactly, by a method of Lagrange's that never leaves the whole numbers, its terms run 1, 3, 1, 5, 1, 1, 4 … and throw up a 534 at the thirty-fifth place and a 7,451 at the 571st — and in every statistic anyone has measured, they look like the terms of a number picked at random.
How smooth the disguise is
An unlocked circle map is a rigid rotation in different coordinates, and whether those coordinates are smooth is decided by arithmetic. Solving for the change of coordinates means dividing, harmonic by harmonic, by numbers that come arbitrarily close to nought — and the golden rotation number keeps them far enough away that the result is not merely smooth but analytic, while a number lying close to a fraction makes it buckle.
A series that waits on π
Add 1/(n³ sin² n) for n = 1, 2, 3, … and the terms are mostly tiny, except where n is almost a multiple of π and sin n is almost nought. Ten million terms add to 30.3145, four-fifths of it from the single term at n = 355. Whether the sum is finite depends on how closely fractions can approach π — on a number called its irrationality measure — and the best proof available says only that the measure is below 7.1, where the series needs it below 2.5.
The numbers that come after the golden ratio
The golden ratio is the number worst approximated by fractions: no constant larger than √5 works in Hurwitz's theorem. Set it aside and √2 is worst, with √8. Set that aside and the next is a number whose continued fraction repeats 2, 2, 1, 1, with √221/5. Markov proved in 1879 that the list continues for ever below 3, one entry for each solution of x² + y² + z² = 3xyz.
Real fields that factorise uniquely
Among the fields Q(√−d) only nine have unique factorisation, and Gauss guessed as much. Among the real fields Q(√p) he guessed the opposite — infinitely many — and the guess is still unproved. Counting cycles of reduced quadratic forms for the 16,900 primes p ≡ 1 mod 4 below 400,000 finds 79 per cent with class number one, drifting slowly down towards the 75.45 per cent that Cohen and Lenstra's heuristic predicts — and finds the reason the real fields behave so differently: their units are enormous.
Rounding to the nearest remainder
Euclid's algorithm divides and keeps the remainder, and the remainder it keeps is the one left after rounding the quotient down. Rounding to the nearest instead — allowing a remainder to be taken from above — never takes more steps, and Kronecker proved that no mixture of rounding up and down does better. On average it saves three steps in ten, the ratio of the logarithms of the golden ratio and of two. And its slowest inputs are not Fibonacci numbers but Pell numbers, because the worst case of each algorithm is the number its own kind of continued fraction expands most slowly: the golden ratio for one, the square root of two for the other.
A small quotient for every denominator
Pick a denominator, any whole number. Among the fractions with that denominator, is there always one whose continued fraction has no large entries — whose path down the Stern–Brocot tree never turns the same way more than five times running? Stanisław Zaremba guessed so in 1972, for a reason to do with sampling a square evenly. Every denominator up to a hundred thousand obeys, with only 6, 54 and 150 needing a five. The guess is proved for almost every denominator and not for all, and the reason it ought to be true is a dimension: the reals whose quotients stay at most five fill a set of dimension 0.837, enough to give each denominator thousands of good fractions on average, and the open question is whether averages are kept everywhere.
Two numbers approximated at once
Thirty-seven points in thirty-six boxes force a multiple of √2 and a multiple of √3 to land near whole numbers together, and the same count in more boxes makes q times the two distances less than one infinitely often. Littlewood guessed that the product can be made as small as anyone likes. Each number alone has a floor; the product finds a new record eight times below twenty million, and nobody can prove it will keep going.
The sum after Leibniz's, made geometric
Leibniz's series adds the reciprocals of the odd numbers with alternating signs and gives π/4. Square the odd numbers and the same pattern gives Catalan's constant, 0.915965…, about which almost nothing is known — not even whether it is a fraction. A formula of Ramanujan's turns its slow series into one whose terms shrink by a factor of four, which makes a thousand decimals cheap, and the decimals and continued fraction then say exactly how much digits can settle and where they stop.
The silver mean at the flat point
At the golden-mean rotation number, the circle map with a flat point has two universal constants, 2.8336 and 1.2886. Repeat the measurement at the silver mean, √2 − 1, and two different numbers appear — 6.7992 and 1.5868 — shared by every map with the same kind of flat point. Below the critical line the silver gaps shrink by (1 + √2)², the square of the silver ratio, exactly as a rigid rotation predicts; on it they do not. Every rotation number with a repeating continued fraction carries its own pair, and a number whose expansion ends in ones inherits the golden pair, whatever came first.
Named alongside it
The objects these essays reach for when they reach for this one.
Diophantine approximationGolden ratioPell equationIrrationalityRational approximationQuadratic irrationalFundamental solutionPeriodicityStern brocot treeFibonacciIncommensurabilityMediant