[math-fun] Wanted: an _inefficient_ number representation
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)) ?
On 6/26/06, Henry Baker <hbaker1@pipeline.com> wrote:
Are there representations of n that grow as O(sqrt(n)) or O(cbrt(n)) ?
Here's one example: http://www.research.att.com/~njas/sequences/A110301 --Joshua Zucker
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@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
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@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
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
participants (4)
-
Fred lunnon -
Henry Baker -
Joshua Zucker -
Richard Guy