Enumerating the Rationals

Jeremy Gibbons, David Lester and Richard Bird (2004). Enumerating the Rationals. May 2004.

In this paper,we explain an elegant technique for enumerating the positive rationals without duplicates. Moreover, we show how to do so as a simple iteration, generating each element of the enumeration from the previous one alone,with constant cost per element (assuming unit cost for simple operations on arbitrary-precision rationals). Best of all, the resulting program is extremely simple...

Cute. Nothing earth shattering, but fun none the less.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

"Proofs from the Book"

The book that they say inspired this paper sounds very nice. I thought about this sort of book many times. Has anyone here read it?

Re: "Proofs from the Book"

I have this one. I haven't read it cover to cover; it's more of a "grazing" book.

I would say that it is "math geek light reading". ;-)

It is definitely a tribute to the beauty and excitement of simple, elegant proofs.

Proofs Missing From the Book

Damn! Unfortunately the section that inpired this paper is new to the third edition. (I have the second edition)

I've been robbed! ;-)

Fourth Edition

Apparently, the fourth edition was recently released...


And now there's a Python version.

Fun paper.

Heh, I just discovered this paper, and was just about to post it. But funnily enough, it's already here! :-)

Personally, I think the Stern-Brocot tree should be the "default" example of an infinite tree in the functional programming community. The Calkin-Wilf tree is new to me.