What would you consider nontrivial? For example, represent x by the unary pair (y, x - y^k) where y = [x^(1/k)], separated by zeros. For fixed k, this obviously has length O(x^1/k). Or you could make it less inefficient(!) by choosing k = y, etc etc --- a unary version of Knuth's asymptotically infinitely efficient representation. WFL On 6/26/06, Henry Baker <hbaker1@pipeline.com> wrote:
A "unary" representation of a natural number n is
1 "1" 2 "11" 3 "111"
etc.
A "positional" representation of a natural number to base b is
d_0+d_1*b+d_2*b^2+...+d_n*b^n
where 0<=d_i<b.
The length of a unary representation of n is O(n), while the length of a positional representation of n is O(log(n)).
Are there representations of n that grow as O(sqrt(n)) or O(cbrt(n)) ?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun