# Enumerating positive fractions (reference missing)

I remember that the recursion

$r(0)=0, \ \ r(n+1)=\frac{1}{2 [r(n)]+1-r(n)}$ produces a sequence of rational values $0 \mapsto 1 \mapsto 1/2 \mapsto 2 \mapsto 1/3 \mapsto ...$ which exausts the positive fractions (and of course every fraction can only appear once).

Unfortunately I do not remember the reference for this statement. Can anybody help me?

## 1 Answer

Have a look at chapter 19 ("Sets, Functions and the continuum hypothesis") in "Proofs from THE BOOK" (5th edition) by Aigner/ Ziegler.

The sequence originates in the paper "Recounting the Rationals" by Calkin/Wilf but in this paper you can't find the formula you mention.

• Thank you! Actually the keyword "Calkin/Wilf" is really useful: with this you can find also several references online (Wikipedia, OEIS, etc.). en.wikipedia.org/wiki/… – ccarminat Mar 14 '15 at 18:06
• The answers to mathoverflow.net/questions/200656/… also contain a lot information. – gsa Mar 23 '15 at 15:30