The explanation at http://mathlesstraveled.com/2009/10/18/the-hyperbinary-sequence-and-the-calk... of the "Calkin-Wilf [rooted binary] tree" makes it clear that this remarkable ordering of the rationals is simply from left to right within each level of the tree in a "raster scan." The root of the tree is 1/1 and the left child of a/b is a/(a+b) and the right child is (b+a)/b. That makes it easy to find the Nth rational number because we know the tree has 2^k nodes at level=k>=0 so we can in O(logN) steps walk down the tree to the right place. The "right place" is at level k where N is a (k+1)-bit positive integer and in the (N-2^k)th location (first location is "0") within that level. This is a simpler O(logN)-step algorithm than I described before: You simply walk k steps down the tree going right (1) or left (0) according to the bits in N's binary expansion (most-significant first) except that you ignore THE most significant bit of N since it always is 1. (Sorry to be playing catch-up here...) Now, let me return to the problem I had posed last post of answering the reverse problem -- given a rational number a/b, what is its number N? The tree-parent of a/b [assumed reduced so GCD(a,b)=1] is: a/(b-a) if b>a (a-b)/b if a>b has no parent (it is the tree-root) if a=b. This allows us also to walk UP the tree. So given a/b we reduce it using Euclidean GCD algorithm, then walk up the tree to the root. As we walk, each step we know whether that was a left-child (0) or right-child (1). These bits tell us the binary representation of N as described above. This algorithm runs in O(1+log(a+b)) steps. We now can do such fine things as compare two rationals a/b and c/d to decide which comes first in order, in O(1+log(a+b+c+d)) steps. As I noted before, the amazing sequence http://oeis.org/A002487 a(0,1,2,3,...) = 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8... which generates the nonnegative rationals 0/1, 1/1, 1/2, 2/1, 1/3, 3/2,... in Calkin-Wilf order obeys the non-Fibonacci recurrence a(n+2) = 2*a(n+1)*Floor(a(n)/a(n+1)) + a(n+1) - a(n) which trivially allows us to walk the rationals 1 step at a time in the forward direction. It also allows us to walk in the decreasing-n (backward) direction 1 step at a time in O(1) operations per step, although realizing that, is a bit trickier. [An "operation" x+y, x-y, or floor(x/y) is assumed to be O(1) "steps" in our model of computation...] Wikipedia https://secure.wikimedia.org/wikipedia/en/wiki/Stern–Brocot_tree says the "Stern Brocot" tree is related to the Calkin-Wilf tree by a bit-reversal permutation and explains the connection between the SB tree and the continued fraction expansion of a rational number. It also points out the SB tree is a valid binary search tree with the rational numbers (according to the usual real-number ordering)! https://secure.wikimedia.org/wikipedia/en/wiki/Calkin–Wilf_tree The "Minkowski question mark" function is a continuous analogue of the discrete Stern-Brocot tree which works with the real numbers instead of the integers... https://secure.wikimedia.org/wikipedia/en/wiki/Minkowski%27s_question_mark_f... http://mathworld.wolfram.com/MinkowskisQuestionMarkFunction.html And what, I wonder, is the fourier series expansion of ?(x)-x ? quite amazing stuff... -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)