Er, do you know of a nice bijection between rationals and pairs of integers? --Rich ----- Quoting Marc LeBrun <mlb@well.com>:
="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.)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun