[math-fun] Wanted: an _inefficient_ number representation

[Richard Guy]

Sh'd've checked that these are A000462,
A007961, A000433.       R.

On Mon, 26 Jun 2006, Richard Guy wrote:

> 0, 1, 2, 10, 11, 12, 100, 101, 102, 110, 1000, 1001, 
> ...
>
> is a sqrt(n) example, where the number
>
> abc...k  is to be read as
>
> aT_k + bT_(k-1) + cT_(k-2) + ... + kT_1
>
> where  T_j = j(j+1)/2.
>
> Another example would be
>
> 0, 1, 2, 3, 10, 11, 12, 13, 20, 100, 101, 102, ...
>
> which uses squares instead of triangles.
>
> For a cube root example, use cubes:
>
> 0,1,2,3,4,5,6,7,10,11,12,13,14,15,16,17,20,21,
> 22,23,24,25,26,27,28,29,2a,100,101,...    R.
>
> On Mon, 26 Jun 2006, Henry Baker 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 at mailman.xmission.com
>> http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
>> 
>