Calkin–Wilf tree

It is named after Neil Calkin and Herbert Wilf, but appears in other works including Kepler's Harmonices Mundi.

Its sequence of numerators (or, offset by one, denominators) is Stern's diatomic series, and can be computed by the fusc function.

The Calkin–Wilf tree is named after Neil Calkin and Herbert Wilf, who considered it in a 2000 paper.

Even earlier, a similar tree (including only the fractions between 0 and 1) appears in Kepler's Harmonices Mundi (1619).

Thus, in either case, the parent is a fraction with a smaller sum of numerator and denominator, so repeated reduction of this type must eventually reach the number 1.

However, it is not a binary search tree: its inorder does not coincide with the sorted order of its vertices.

The sequence of numbers generated in this way gives the continued fraction representation of qi.

Example: In the other direction, using the continued fraction of any qi as the run-length encoding of a binary number gives back i itself.