Functional Pearl: Enumerating the Rationals [pdf](cs.ox.ac.uk)
cs.ox.ac.uk
Functional Pearl: Enumerating the Rationals [pdf]
https://www.cs.ox.ac.uk/jeremy.gibbons/publications/rationals.pdf
4 comments
Related: the Farey sequence [1]. Well worth investigating if you found this paper interesting.
[1] https://en.wikipedia.org/wiki/Farey_sequence
[1] https://en.wikipedia.org/wiki/Farey_sequence
An interesting (later) paper about generating the Stern-Brocot tree and the Calkin-Wilf tree simultaneously from a sequence of 2x2 matrices: http://www.cs.nott.ac.uk/~psarb2/MPC/RecountingRationalsTwic...
This looks very weird in my pdf-viewer.
Try a different PDF viewer? It looks fine here in Chrome and Adobe Reader, both on Windows 10.
Also looks fine in Firefox in Linux
There are two things that could be improved about the paper in my opinion, but they are minor. First, the proof of the formula for the next sibling in the Calkin-Wilf tree (Figure 3 in the paper) becomes much more obvious when you express x and x_0' in terms of y instead of expressing y and x_0' in terms of x. Second, the Stern-Brocot tree is a bit of a detour without any real payoff. It's just as easy to go from the traced gcd directly to the Calkin-Wilf tree.
The latter part is a bit of a shame, since there are plenty of things that could be said about the Stern-Brocot tree (see e.g. Concrete Mathematics by Graham, Knuth, and Patashnik), but then it would have to be moved to the end of the paper. The paper doesn't do this in order to have the nice closed form solution for the titular enumeration at the end instead...