Re: Mapping rationals to binary strings while preserving order



On Thu, 13 Jul 2006, Lars Christian Jensen wrote:

Your solution is obvioiusly optimal for v=1:

0/ 1 0.000000 0
1/ 1 1.000000 1

Then for v=2, you must also represent 1/2 by a string greater than 0 and
smaller than 1, and you have the only optimal solution for this too:

1/ 2 0.500000 01

Then for v=3, you must also represent 1/3 by a string greater than 0 and
smaller than 01, and you have the only optimal solution for this too:

1/ 3 0.333333 001


It is inevitable to add an extra bit for each increment o of v, so your
solution is optimal, unless you are willing to sacrifice the optimal
solution for smaller v's.

I agree -- I guess this could be formalized in the following way: for a
given mapping f, define
S_f(v) = max { length(f(u/v)) : 0 <= u <= v, gcd(u, v) = 1 }
and we are interested in the asymptotic behavior of S_f(v) as v grows
towards infinity. The solution in my original post has S_f(v) = v, and
what I was wondering is if some other suitable (i.e. order-preserving)
mapping f exists for which S_f(v) is sublinear in v.

An optimal solution for v=9 is trivial. Just map the 29 possible numbers
above to 29 integers, and use their bit representation.

I agree, but I'd like a solution that works for arbitrarily large values
of v.

-----
Janez


.