On Sun, Nov 6, 2011 at 6:28 PM, Warren Smith <warren.wds@gmail.com> wrote:
Question: is there any fast way to go in the other direction: given a rational, what is its position in the order?
Yes, Euclidean algorithm gets you the result in a short time as well. The quotients you encounter there tell you how many times you have to take the left or right branch as you're navigating the tree, i.e., the binary representation of your position in the order. I think my favorite discovery that results from all this is the inverse function of the number of hyperbinary representations: that is, it gives a fast way to determine all EulerPhi[1000] even numbers that have 1000 hyperbinary representations. (Of course there are then infinitely many odd numbers that also have the same 1000 representations, because a(2n+1) = a(n).) I have a paper (coauthored by one of my now eighth-grade tutors and myself, based on some of our work and in collaboration with Brent Yorgey of http://mathlesstraveled.com/2009/10/18/the-hyperbinary-sequence-and-the-calk... ... we plan to submit to Math Horizons, I think, since there's not much original in it other than the method of presentation. Most of what's in it can be found in Brent's series of posts on hyperbinary. --Joshua Zucker