Recounting the Rationals: Twice!

Backhouse R, Ferreira JF.  2008.  Recounting the Rationals: Twice!. Mathematics of Program Construction (LNCS 5133).


We derive an algorithm that enables the rationals to be efficiently enumerated in two different ways. One way is known and is credited to Moshe Newman; it corresponds to a deforestation of the so-called Calkin-Wilf tree of rationals. The second is new and corresponds to a deforestation of the Stern-Brocot tree of rationals. We show that both enumerations stem from the same simple algorithm. In this way, we construct a Stern-Brocot enumeration algorithm with the same time and space complexity as Newman’s algorithm.

Citation Key: