="Veit Elser" <ve10@cornell.edu> By the way, a solution to this puzzle gives a bijection between rationals and integers and would have fit nicely in the set theory chapter of my new math book.
Or integers and any pairs (j,k), for instance extensions like j + k sqrt(2). Moreover, as mentioned in a comment to A000695, via repeated application the Moser-de Bruijn sequence gives a fun bijection between lists of integers and integers: f([L1,L2,L3...]) := a(L1)+2*a(f([L2,L3...])), with f([]) <--> 0. This gives many pleasant single-integer encodings. For example partitions, the exponents in prime factorizations, finite continued fractions, etc. --------- Programming puzzle: compute Y=a(n+1) efficiently from X=a(n). Martian solution: Y = (X + 1/3) & -2/3 where & denotes bitwise AND. (Of course this only works on computers where, just as -1 is represented in two's-complement by the infinite dyadic ...1111111111, -2/3 is ...1010101010 and thus 1/3 is ...1010101011.)