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?


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.

  • $\begingroup$ 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/… $\endgroup$ – ccarminat Mar 14 '15 at 18:06
  • $\begingroup$ The answers to mathoverflow.net/questions/200656/… also contain a lot information. $\endgroup$ – gsa Mar 23 '15 at 15:30

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.