Every rational in one sequence

The rung below lists every positive rational exactly once, and needs a tree to do it: to say where $\tfrac{5}{3}$ is, a path of turns has to be given.

There is a way of listing them in a single row, and it is one recursion.

$$s(0) = 0, \quad s(1) = 1, \quad s(2n) = s(n), \quad s(2n+1) = s(n) + s(n+1).$$

The ratios of consecutive terms are $\tfrac11, \tfrac12, \tfrac21, \tfrac13, \tfrac32, \tfrac23, \tfrac31, \ldots$ — every positive rational, once, in lowest terms, with no cancelling and no tree.

Why the ratios never repeat #

The property looks like it should need an argument and it needs a picture instead.

Read the sequence as a tree: put $\tfrac{s(n)}{s(n+1)}$ at node $n$, and the recursion says the node at $2n$ is $\tfrac{s(n)}{s(n)+s(n+1)}$ and the node at $2n+1$ is $\tfrac{s(n)+s(n+1)}{s(n+1)}$. So a node $\tfrac{p}{q}$ has children $\tfrac{p}{p+q}$ and $\tfrac{p+q}{q}$, and the root is $\tfrac11$.

That is the Calkin–Wilf tree, and its two properties are the two the enumeration needs.

Every positive rational appears. Given $\tfrac{p}{q}$ in lowest terms, its parent is $\tfrac{p}{q-p}$ if $q > p$ and $\tfrac{p-q}{q}$ otherwise, and one of the two is always available because $p \ne q$ unless the fraction is $\tfrac11$. Both parts get smaller, so the ascent terminates — at $\tfrac11$, because that is the only fraction with no parent.

The termination is a decreasing measure, which is the same argument shape this collection keeps arriving at. Here the quantity is $p + q$, it falls by at least one at every step of the ascent, and a decreasing sequence of positive whole numbers cannot go on forever. Nothing about fractions is used beyond that they are pairs of positive whole numbers, so the argument would work for any construction whose parent operation is a subtraction.

No rational appears twice. The ascent is deterministic: which parent to take is decided by comparing $p$ and $q$, with no choice. So a fraction has exactly one path back to the root and therefore one place in the tree.

The ascent is Euclid’s algorithm, subtracting the smaller from the larger, which is where the coprimality is preserved and why the terminating value is $\tfrac11$ rather than anything else.

Where the tree structure went #

The single row and the tree are the same object, and the index carries the address.

Write $n$ in binary. Stripping the leading $1$ leaves a string of bits, and that string is the path from the root — a $0$ meaning “left child”, a $1$ meaning “right”. The recursion says so directly: $s(2n)$ and $s(2n+1)$ are the two children of $s(n)$, and doubling appends a bit.

So the tree has not been removed; it has been encoded in the index, and the flattening is the observation that a binary expansion is a path. That is the same trick the parity of a binomial coefficient uses one field away, where a fractal appears because binary place value is a doubling structure.

The consequence worth having is that the enumeration is computable in place. To find the fraction at position $n$, no tree needs building and no earlier term needs storing — the recursion can be run from the binary digits of $n$ alone.

There is a still tidier form of that, and it is startling enough to be worth writing out. The map taking one fraction to the next in the sequence is

$$\frac{p}{q} \;\longmapsto\; \frac{1}{2\lfloor p/q\rfloor - p/q + 1},$$

a single expression involving one floor. Apply it to $\tfrac11$ and the whole enumeration falls out, one fraction at a time, with no index and no recursion at all.

Every positive rational, in order, from one formula and a starting value. That the enumeration has such a form is a consequence of the overlapping-pairs property — the next fraction’s numerator is this one’s denominator, so only one new number is needed at each step, and the formula computes it.

The floor is where the tree’s branching went. Whether the next step goes left or right in the tree is decided by comparing $p$ and $q$, and $\lfloor p/q \rfloor$ is that comparison generalised to a count — which is the continued fraction’s quotient again, appearing for the third time on this ladder in a third disguise.

What the terms count #

The recursion produces whole numbers and the natural question is what they count. The answer is unexpected and it is the reason the sequence has a name.

$s(n+1)$ is the number of ways of writing $n$ as a sum of powers of two using each power at most twice.

Those are the hyperbinary representations. Ordinary binary uses each power at most once and is unique; allowing two of each makes the representation non-unique, and the count of representations is Stern’s sequence.

The figures check it by enumerating: for each $n$ up to twelve, every hyperbinary representation is generated and counted, and the count is compared against the sequence’s term.

The proof is the recursion read as a case analysis. To write $n$ hyperbinarily: if $n$ is even, the number of $1$s used must be even, so it is nought or two — nought gives representations of $n/2$ doubled, two gives representations of $(n-2)/2$ doubled with two ones. If $n$ is odd, one $1$ must be used, and what remains is $(n-1)/2$ doubled. Collecting the cases gives exactly $s(2n) = s(n)$ and $s(2n+1) = s(n) + s(n+1)$.

So a question about fractions and a question about binary representations have the same answer, and neither construction mentions the other.

The correspondence gives a second proof of the enumeration’s key property, and it is the one worth carrying because it is a statement about counting rather than about paths. If $\tfrac{s(n)}{s(n+1)}$ equalled $\tfrac{s(m)}{s(m+1)}$ for two different indices, two different numbers would have hyperbinary counts in the same ratio — which is not immediately impossible, so the argument needs the stronger form: consecutive terms are coprime, so equal ratios force equal terms, and the sequence’s own recursion then forces equal indices.

Coprimality is doing the work in both proofs, and it is the property that has to be established first whichever route is taken. From the tree it comes from the mediant’s determinant; from the recursion it comes from an induction with two cases; and the two arguments are the same argument, since the determinant condition is what the induction is checking.

There is a pleasing consequence about hyperbinary representations that falls out and would be hard to see directly. The number of hyperbinary representations of $n$ and of $n+1$ are always coprime — a fact about counting sums of powers of two, established by a fact about fractions, with no evident way of proving it in its own terms.

The shape of the sequence #

The bar chart is not smooth and its features are all explicable from the recursion, which is worth doing because it says what kind of object the sequence is.

The valleys are at the powers of two. $s(2^k) = s(2^{k-1}) = \cdots = s(1) = 1$, because doubling an index never changes the term. So the sequence returns to one infinitely often, and those returns are exactly the powers of two.

The peaks are at the runs of ones. The largest term in the block from $2^k$ to $2^{k+1}$ is the Fibonacci number $F_{k+2}$, and it occurs at the index whose binary expansion alternates — which is the same alternating path that produced the Fibonacci ratios in the matrix reading, arriving here as a statement about where a maximum sits.

And the average over a block grows like $(3/2)^k$. Summing the recursion over one block gives three times the sum over the previous one, while the block’s length doubles — so the mean multiplies by $3/2$ each time, which is the same $3$-against-$2$ arithmetic Pascal’s triangle modulo two produces and for the same reason: a doubling of the index with a tripling of a total.

So the sequence grows on average like $n^{\log_2(3/2)} \approx n^{0.585}$ with peaks at $n^{\log_2\phi} \approx n^{0.694}$ and valleys pinned at one, forever. A sequence that returns to its minimum infinitely often while its average grows without bound is an unusual shape, and it is a direct consequence of the two cases of the recursion doing completely different things.

Two enumerations, and what each is good for #

The rung below’s tree and this one contain the same fractions and are not the same tree, and the difference decides which to use.

The Stern–Brocot tree is ordered. Reading it left to right reads the fractions in increasing order, so it can be flattened into the Farey sequences, it supports a binary search for the simplest fraction in an interval, and it says everything about approximation.

The Calkin–Wilf tree is not ordered and has a property the other lacks: the denominator of each fraction is the numerator of the next, all the way along. That is what makes the single sequence possible — the list of fractions is really a list of numbers read in overlapping pairs, so $n$ numbers give $n-1$ fractions with nothing repeated.

The two trees are related by reversing the binary expansion of the index, which is a clean statement and an odd one: the same fractions in two orders, and the transformation between the orders is bit-reversal.

Neither is better and the choice is decided by the question. Enumeration wants Calkin–Wilf; approximation wants Stern–Brocot, which is the rung above.

What the enumeration proves #

Listing every positive rational exactly once is a proof that the rationals are countable, and it is a tidier proof than the standard one.

The usual argument arranges the fractions in a grid and zigzags through it. That visits $\tfrac24$ and $\tfrac12$ separately, so it is not a bijection until duplicates are skipped, and skipping requires testing each fraction for lowest terms as it arrives.

This one visits each fraction once, already reduced, with no test and no skipping. The bijection is exhibited rather than repaired, and the function realising it — index to fraction — is computable from the index’s binary digits.

That is worth putting beside what the diagonal argument shows about the reals. The rationals are listable and the reals are not, and the contrast is sharper when the listing is this explicit: there is a formula taking a whole number to a rational, hitting every one exactly once, and there provably is no such thing for the reals.

Where it needs care #

The sequence starts at nought and the fractions at one. $s(0) = 0$ is needed for the recursion and $\tfrac{s(0)}{s(1)} = \tfrac01$ is not a positive rational, so the enumeration is $\tfrac{s(n)}{s(n+1)}$ for $n \ge 1$.

Only positive rationals appear. Negatives and nought need to be tacked on by an interleaving, exactly as any enumeration of the integers does, and nothing about the construction supplies them.

The coprimality needs the recursion, not the ratio. $s(n)$ and $s(n+1)$ being coprime is proved by induction on the recursion; it is not visible in the values, and a sequence that satisfied a similar recursion with different starting values would generally fail it.

And the flattening is not order-preserving. Consecutive terms of the sequence are consecutive in the tree’s breadth-first order, which jumps about in size — $\tfrac13$ is followed by $\tfrac32$. Anybody expecting a listing to be increasing will find this one useless for approximation, which is exactly the division of labour above.

The successor formula needs the fraction in lowest terms. Handed $\tfrac24$ it returns something that is not the successor of $\tfrac12$, because the floor sees a different quotient. That is not a fragility of the formula; it is the same fact the rung below records about the mediant, which also depends on how a fraction is written. Both operate on pairs of counts rather than on numbers, and both are correct exactly because the construction never presents them with anything else.

And nothing here enumerates the reals or claims to. The listing is of the rationals and its whole content is that they can be listed; that no listing of the reals exists is a different theorem with a different proof, and the contrast between the two is the reason an explicit listing is worth having.

1858, and 2000 #

Moritz Stern introduced the sequence in the same 1858 paper as the tree, and the two halves of that paper were treated as one subject for a long time and then diverged: the tree became a topic in approximation and the sequence became a curiosity in the literature on binary representations.

Calkin and Wilf published their tree in 2000, in a three-page paper, and the striking thing about it is that nothing in the paper is difficult. The tree is defined, the two properties are proved in a paragraph each, the connection to hyperbinary representations is a case analysis, and the whole is elementary throughout.

A construction this simple sitting undiscovered for a century and a half is worth registering rather than explaining away. Stern had the sequence; the observation that its consecutive ratios enumerate the rationals is one line from there, and nobody wrote it.

The plausible reason is that nobody was looking. Countability of the rationals was settled by Cantor in the 1870s and the zigzag proof was good enough for the purpose; an explicit bijection is a better object and there was no question outstanding that required one. Constructions get found when somebody has a reason to want them, and here the reason arrived long after the materials.

What the pictures cannot show #

The bars are the sequence’s values and the interesting object is the sequence of ratios, which is written under the bars only when there is room. A ratio is a relation between two adjacent bars, and a bar chart shows the terms and not the relation.

The enumeration’s completeness is not shown at all. That every positive rational appears somewhere is a statement about all of them, proved by the ascent argument; the figures check that the first forty-eight terms match an independent walk of the tree, which is a check on the implementation.

And the hyperbinary count is checked and not drawn. Enumerating the representations of twelve is a list of nine sums, and a figure of it would be a figure of arithmetic rather than of the correspondence.

The ladder from here #

Rungs above: the descent towards an irrational, where the ordered tree does what this one cannot. The bit-reversal relating the two trees, and what it does to the continued fraction. Stern’s sequence’s asymptotics, where the maximum over a block of $2^k$ terms is a Fibonacci number and the average is a power of $3/2$. The Minkowski question-mark function, which sends the Stern–Brocot order to the binary expansions and is continuous, increasing, and has zero derivative almost everywhere. And the Takagi function, which is the same recursion’s continuous cousin.

A sequence that counts two things #

The habit is the one the hyperbinary correspondence exhibits: when a recursion produces whole numbers, ask what they count.

Nothing about the definition of $s$ suggests representations of anything. It is a recursion with two cases, written down to generate fractions, and the numbers it produces would ordinarily be treated as intermediate quantities. That they count something is found by comparing the recursion against a case analysis of a completely different problem — which is a search rather than a deduction, and is how most such correspondences are found.

The payoff is that a correspondence turns one hard question into another, and which of the two is hard varies. That consecutive terms are coprime is easy from the recursion and would be hard from the counting; that the sequence’s maximum over a block is a Fibonacci number is easy from the counting and awkward from the recursion.

The general recommendation is to keep both descriptions and reach for whichever the question is about. A quantity with two definitions is not redundant; it is a quantity with two sets of available theorems.