The Stern-Brocot Tree: Every Fraction, Exactly Once, in Perfect Order

In 1858, a German number theorist named Moritz Stern published a paper describing a strange, infinite tree. Three years later, and apparently with no knowledge of Stern's work, a Parisian clockmaker named Achille Brocot stumbled onto the exact same structure — not because he cared about number theory, but because he needed to build gears. Both men had found the same object from opposite directions: a tree that contains every positive fraction in existence, each one appearing exactly once, already reduced to lowest terms, arranged in perfect increasing order. No duplicates. No missing fractions. No simplifying required. Just an infinite, perfectly organized filing cabinet for all of rational number land, built from nothing but addition.

The Concept

Here's the trick at the heart of it, called the mediant. Take two fractions, a/b and c/d. Their mediant is not what you'd get from adding them normally — it's (a+c)/(b+d), just smashing the numerators together and the denominators together. It's the fraction you'd get if a math student "incorrectly" added two fractions by crossing out the rule they were taught. And it has a beautiful property: the mediant of two fractions always falls strictly between them in value.

Start with two boundary fractions representing zero and infinity: 0/1 and 1/0. Take their mediant: (0+1)/(1+0) = 1/1. That's the root of the tree.

Now you have two gaps to fill: between 0/1 and 1/1, and between 1/1 and 1/0. Take the mediant of each pair. Between 0/1 and 1/1, the mediant is 1/2. Between 1/1 and 1/0, the mediant is 2/1. Those become the next row of the tree.

Keep going forever. Every new row is built by taking the mediant of each fraction with its two tree-neighbors. Row by row, you get:

`` 1/1 1/2 2/1 1/3 2/3 3/2 3/1 1/4 2/5 3/5 3/4 4/3 5/3 5/2 4/1 ``

Every positive rational number you can name — 22/7, 355/113, 1/1000000 — sits at exactly one node, exactly once, already in lowest terms. You never see 2/4 anywhere in this tree, because 1/2 already claimed that spot. It's not a coincidence or a rule that needs enforcing from outside; the mediant construction makes it mathematically impossible for a reduced fraction to appear twice.

Why It Matters

This is more than a cute party trick with fractions. The Stern–Brocot tree is a computational engine, and it was discovered by a clockmaker precisely because it solves a brutally practical engineering problem: how do you build a gear train for a ratio you can never build exactly?

Brocot's problem, as described in historical accounts of 18th- and 19th-century clockmaking, looked like this. Say you want a shaft that spins once per hour to drive a wheel that completes one rotation per mean tropical year — 365 days, 5 hours, 49 minutes. Worked out as a fraction, that ratio is 720/525,949. The denominator, 525,949, is prime. You cannot factor it. You cannot build a gear with 525,949 teeth, and you certainly can't chain together smaller gears to produce that exact ratio, because prime numbers don't break into smaller gear-sized pieces.

So instead, you approximate. But you want the best possible approximation using the smallest possible numbers, because every tooth costs metal, precision, and friction. This is exactly the question the Stern–Brocot tree answers. If you walk down the tree, at each step choosing the branch (left toward smaller, right toward larger) that moves you closer to your target value, every node you touch is provably the best rational approximation achievable with denominators that small — better, in a precise sense, than anything else nearby. Walking the tree toward 720/525,949 lands on 196/143,175, a ratio accurate enough for the clock and small enough to factor into four manageable gear stages: 2/3 × 2/25 × 7/23 × 7/83. That's an engineering solution extracted directly from a number-theoretic structure, decades before anyone called it "the Stern–Brocot tree."

The same approximation power shows up anywhere continuous, irrational-ish quantities need to be approximated by simple ratios: musical tuning systems (approximating the irrational ratios of equal temperament with simple string or pipe-length ratios), camera lens aspect ratios, old mechanical calculators, and any system where you need "close enough" expressed in small whole numbers.

The Details

What makes the tree even richer is its relationship to two other major ideas in mathematics: continued fractions and the Euclidean algorithm.

If you record your path down the tree as a sequence of lefts (L) and rights (R) to reach any fraction, that sequence directly encodes the fraction's continued fraction expansion — the representation of a number as 1 divided by (an integer plus 1 divided by (an integer plus ...)). Long runs of L's or R's correspond to large terms in the continued fraction; short alternating runs correspond to fractions that are, in a sense, "maximally irrational-looking," resistant to simple approximation. The most famous example is the golden ratio, φ = (1+√5)/2, whose continued fraction is an endless string of 1s — which corresponds to the single most zig-zagging path imaginable through the tree, alternating left-right-left-right forever. That's the formal reason the golden ratio is often called "the most irrational number": it's the real number that rational approximations have the hardest time sneaking up on.

The tree is also, quietly, the Euclidean algorithm in disguise. Finding where a fraction m/n sits in the tree — which lefts and rights to take — is computationally identical to running Euclid's 2,300-year-old algorithm for the greatest common divisor. Each "subtract the smaller from the larger, repeatedly" step in Euclid's method corresponds to a run of turns in one direction through the tree. Two ideas separated by over two millennia turn out to be the same process wearing different clothes.

There's a sibling structure worth knowing about too: the Calkin-Wilf tree, built with a different but related rule (a node m/n has left child m/(m+n) and right child (m+n)/n). It also contains every positive rational exactly once, but in a different order, and it comes with a surprising bonus: reading the Calkin-Wilf tree breadth-first, row by row, produces a simple sequence where you can jump directly from one fraction to the "next" one using a slick formula discovered by mathematician Moshe Newman: start at 1, then repeatedly apply x → 1/(2⌊x⌋ − x + 1). This turns "list every positive rational number, once each, with no repeats" — a problem that sounds like it should require infinite bookkeeping — into a single one-line recurrence. Computer scientists use these trees and their generating formulas for exact rational-number arithmetic and for enumerating fractions in programming contest problems, where "find the n-th fraction in lowest terms" shows up more often than you'd expect.

And there's human history tangled in here too. Moritz Stern wasn't just a number theorist tinkering with trees — he was a serious mathematician who held the chair at the University of Göttingen (the same institution Gauss had made the center of the mathematical universe), and he holds a distinct historical note as the first Jewish scholar to become a full professor at a German university without converting to Christianity, something no one before him had managed at that academic level. He also mentored a young Bernhard Riemann and helped Gotthold Eisenstein sharpen his proof of quadratic reciprocity, one of Gauss's own favorite theorems. Meanwhile, Achille Brocot, co-founder of the Parisian clockmaking house Brocot & Delettrez, had no idea he was rediscovering a research mathematician's tree — he just wanted his clocks to keep better time with cheaper gears. Pure and applied mathematics, arrived at completely independently, converging on the identical infinite object.

Takeaways

• The Stern–Brocot tree generates every positive fraction exactly once, already in lowest terms, using nothing but the "mediant" operation (a+c)/(b+d) applied over and over.
• It was discovered twice, independently: by number theorist Moritz Stern in 1858, and by clockmaker Achille Brocot in 1861, who used it to design gear trains approximating impossible-to-build exact ratios.
• Paths through the tree (left/right turns) directly correspond to continued fraction expansions — the golden ratio's famously "most irrational" status comes from its path zig-zagging left-right forever.
• The tree encodes the ancient Euclidean algorithm in a different form, linking a 19th-century discovery to 2,300-year-old number theory.
• Its cousin, the Calkin-Wilf tree, gives computer scientists a one-line formula for marching through every rational number exactly once — proof that an idea built for gears and an idea built for proofs can end up fueling modern algorithms alike.

Resources: The American Mathematical Society's feature column "Trees, Teeth, and Time" covers the clockmaking history in detail, and Neil Calkin and Herbert Wilf's original paper "Recounting the Rationals" (2000) is the standard reference for the sibling tree and its computer-science applications.