I recently encountered a collection of related articles regarding an amazing explicit enumeration of the non-negative rational numbers. Whilst experimenting with the mathematical constructs described, I made some discoveries of my own (which I doubt are new, but I have not found them described elsewhere).

Below, are the references and links to those articles. They’re all worth a read.

The Stern–Brocot tree is a binary tree of positive rational numbers. Each rational number appears (in its simplest form) in the tree exactly once [which is amazing]. Child nodes are generated from ancestor nodes by taking *mediants* of the two horizontally-nearest ancestor nodes. As a result, the tree has the rationals in *in-order*; in particular the numbers in each row are ordered by value. The first few rows contain (without attempting to draw the tree):

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

…

(Complete sequences of mediants have the amazing property that consecutive pairs of values *a/b* and *c/d* are always such that .)

The Calkin–Wilf tree is related. Again, it is a binary tree of positive rational numbers, each appearing exactly once [again, amazing]. Child nodes are generated from a much simpler rule from just the parent node: *r/s* has children *r/(r+s)* and *(r+s)/s*. The first few rows contain:

1/1

1/2, 2/1

1/3, 3/2, 2/3, 3/1

1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4/1

…

Notice that in the Calkin–Wilf tree, consecutive pair of values *a/b* and *c/d* in a row are always such that .

One of my discoveries is: consider any row, say row *N* (counting from 0), of the Calkin–Wilf tree, and index them with their horizontal position 0 to . Now, consider the *N*-bit binary representation of the indices, and bit-reverse them (so 0001011 becomes 1101000). Now sort the values by index. The values are now in order, and as in the corresponding row of the Stern–Brocot tree. Thus, to convert between Stern–Brocot and Calkin–Wilf trees, just bit-reverse the indices within each row.

Next, here’s Dijkstra’s *fusc* function, also known as *Stern’s diatomic series* or *sequence*:

— note that this case with implies the first rule

The sequence starts:

0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, …

The next amazing thing is that the sequence of ratios of consecutive elements of the fusc sequence contains all the non-negative rational numbers exactly once. The values produced are 0/1 followed by the rows of the Calkin–Wilf tree in turn and in order.

0/1, 1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, 1/4, 4/3, 3/5, 5/2, …

From the references, the follow recurrence relations and other formulae were given (sometimes indirectly):

equivalently:

From these, the following may be deduced:

equivalently:

Another remarkable formula given is:

Writing (where , optionally):

where I define the notation

for the function that rounds down to the nearest multiple of *m*.

To invert the above formula, we find that we need to solve

for . The solution is:

where, similarly,

From which we obtain:

Given , the *n* such that may be found by where:

if *q* < 1 then

if *q* > 1 then

Yet another amazing formula is:

where

where

is the *m*-multiple fraction part, or *m*-modulus or *m*-remainder, where

is the *m*-floor, as defined above.

For more information, see the references below.

## References

[1] Stern–Brocot tree, Wikipedia

[2] Calkin–Wilf tree, Wikipedia

[3] EWD570, Edsger W. Dijkstra, “An exercise for Dr. R. M. Burstall”

[4] EWD578, Edsger W. Dijkstra, “More about the function “fusc” (A sequel to EWD570)”

[5] Stern’s Diatomic [Sequence], Mathworld

Note that some of these references differ from each other in the indexing of sequences.

## Leave a Reply