26 Jun
2006
26 Jun
'06
8:29 a.m.
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)) ?