Recounting the Rationals: Twice!

[ CiteULike link ]
Authors

Roland Backhouse and João F. Ferreira

Downloads
Status

Published in Mathematics of Program Construction, Springer-Verlag, LNCS 5133, pp. 79—91 (proceedings of the 9th International Conference Mathematics of Program Construction, MPC 2008, Marseille, France, July 15—18, 2008)

Abstract

We derive an algorithm that enables the 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.

Keywords

program construction, calculational method, algorithms

Bibtex entry
@inproceedings{jff*08:rationals,
	author = {Backhouse, Roland   and Ferreira, Jo\~{a}o  },
	citeulike-article-id = {3049781},
	doi = {10.1007/978-3-540-70594-9\_6},
	journal = {Mathematics of Program Construction},
	keywords = {algorithm-derivation, calkin-wilf, jff-bib, stern-brocot},
	pages = {79--91},
	title = {Recounting the Rationals: Twice!},
	url = {http://dx.doi.org/10.1007/978-3-540-70594-9\_6},
	volume = {5133},
	year = {2008}
}
History
  • 17 July 2008 — presented at MPC '08
  • 12 March 2008 — accepted for publication at MPC '08
  • 09 January 2008 — submitted to MPC '08
  • 20 November 2007 — rejected for publication in the journal American Mathematical Monthly
  • 30 April 2007 — submitted to the journal American Mathematical Montly
  • 17 May 2007 — I have presented the algorithm at Fun in the Afternoon, in Cambridge
  • 22 February 2007 — first version of the paper