Every fraction, exactly once — built by adding badly.
Start with 0/1 and 1/0 — the two impossibilities. Slide a new fraction between them by adding numerators and denominators separately, the way a child would. Repeat forever. The infinite tree you build contains every positive fraction once, already in lowest terms — and the left-right path to each is its continued-fraction expansion.
Between any two fractions a/b and c/d, drop in the mediant (a+c)/(b+d). It is the wrong way to add, but it slides a new fraction strictly between the two — and every positive fraction, exactly once, lives somewhere in the tree this builds.
Begin with 0/1 and 1/0. Their mediant is 1/1. Slide it in. Now between 0/1 and 1/1 sits 1/2; between 1/1 and 1/0 sits 2/1. Keep going. Level by level, every reduced fraction appears, and the value of φ, π, √2 are roads through the same tree.
The tree hides the best rational approximations of every real number — and Brocot built it in 1861 to pick gears for clocks. Number theory, typography, and the digital second-hand all meet on the same diagram.
The mediant of a/b and c/d is what happens if you add numerators and denominators separately — exactly the schoolchild mistake. The result is not a/b + c/d, but it is always a fraction strictly between them, and always already in lowest terms when the parents are. From this single bad addition, an infinite ordered structure falls out.
Three mediants in, and the seeds of every rational are already on the page.
Stern discovered the tree in 1858 as a piece of pure number theory; Brocot rediscovered it in 1861 while picking gear ratios for clocks. Their shared theorem: walk far enough and you meet every reduced fraction p/q with p, q > 0 — each one sitting at its own unique node, no fraction missing, none ever repeated. The tree is simultaneously a complete listing of the positive rationals and a witness that they are merely countable.
Pick any positive number. Walk down from 1/1, going L when you are above your target and R when below. Group the moves into runs and you have written down the continued-fraction expansion of your target — the canonical address of a real number in arithmetic.
3, 22/7, 333/106, 355/113, 103993/33102, …
| step | fraction | decimal | error |
|---|---|---|---|
| 2 | 3/1 | 3.0000000000 | 1.42e-1 |
| 9 | 22/7 | 3.1428571429 | 1.26e-3 |
| 24 | 333/106 | 3.1415094340 | 8.32e-5 |
Stop at the end of an L/R run, just before the direction flips, and the fraction you stand on is a convergent: a best rational approximation of the target, with no smaller denominator getting closer. Stop in the middle of a run and you land on a semiconvergent instead, close but not guaranteed to beat every smaller denominator. Hurwitz' theorem (1891) says every irrational has infinitely many convergents p/q with |x − p/q| < 1/(√5 q²), and the constant √5 is sharp, attained by φ.
For every irrational x, infinitely many fractions p/q satisfy this, and √5 is best possible, attained by the golden ratio.
Gather every fraction anywhere in the tree with denominator at most n that lies in [0, 1], then add the endpoint 0/1. Read left to right, that list is the Farey sequence Fₙ, the sorted reduced fractions in [0, 1] with bounded denominator. A single level never suffices, since a fraction with denominator q already appears by depth q: 1/2 sits at depth 1, so you must sweep the whole subtree down to depth n. The two structures are different views of the same arithmetic skeleton.
Brocot wanted accurate gear trains; today the same tree picks rational approximations for font-hinting on pixel grids, drives the rational-approximation step in digital phase-locked loops, and underlies modern proofs in Diophantine approximation. Wherever you need «the simplest fraction that gets close enough», this is the data structure.
The Explorer lets you type any real number — π, φ, e, √2, or your own — and watch the L/R path unfold, with the convergents listed step by step. Best rational approximations, on tap.
→ Open the ExplorerHow and where this technique lives in the world today.
Topics in the same vein.
