# Recounting the Rationals: Twice!

**Citation:** *Roland Backhouse, Joao F. Ferreira (2008) Recounting the Rationals: Twice!. Mathematics of Program Construction, LNCS 5133 (RSS)*

**Download:** http://www.joaoff.com/publications/2008/rationals

**Tagged:** Computer Science
(RSS) algorithm enumeration rationals stern-brocot program construction mathematics (RSS)

**Summary:**

This paper shows the derivation of an algorithm that enables the positive rationals to be enumerated in two different ways. One way is known, and is called Calkin-Wilf-Newman enumeration; the second is new and corresponds to a flattening 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 Calkin-Wilf-Newman enumeration.