%0 Book Section
%B Mathematics of Program Construction (LNCS 5133)
%D 2008
%T Recounting the Rationals: Twice!
%A Roland Backhouse
%A João F. Ferreira
%I Springer
%X <p>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.</p>