wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Representation Schemes for Natural Numbers
        
(Message started by: Barukh on Apr 15^th, 2005, 9:58am)

Title: Representation Schemes for Natural Numbers
Post by Barukh on Apr 15^th, 2005, 9:58am

1. Device a scheme to represent arbitrary large natural numbers as sequences of 0s and 1s subject to the following properties:

a) The representation of each number is never a prefix of the representation of another number.
b) The representation of each number is “lexicographically smaller” than the representation of every larger number.

2. If R is a representation scheme as defined above, denote L_R(n) the length of the representation of number n in R. What is the asymptotic behaviour of L_R(n) for your R?

3. Let say that representation R dominates representation Q if

a) There exists N such that L_R(n) <= L_Q(n) for every n > N.
b) L_R(n) < L_Q(n) for infinitely many n.

Can you devise an “absolutely dominant” representation (i.e. that dominates every other representation)? What’s its asymptotic behaviour?

Title: Re: Representation Schemes for Natural Numbers
Post by SMQ on Apr 15^th, 2005, 10:35am

1. R(n) = F(n) 1's followed by a 0 where F(n) is a monotonically increasing function over the naturals

2. lim_n->[inf]L_R(n) = [Inf]

3. No. F(n) can be chosen to grow arbitrarily fast, so no absolutely dominant representation exists.

Are you sure that's what you meant to ask? (Or am I somewhere off my nut again?) ;D

--SMQ

Title: Re: Representation Schemes for Natural Numbers
Post by Barukh on Apr 15^th, 2005, 11:40am

on 04/15/05 at 10:35:18, SMQ wrote:

Are you sure that's what you meant to ask? (Or am I somewhere off my nut again?) ;D--SMQ

Of course, I am not sure ;D! I mistyped the signs in inequalities.

Corrected.

Title: Re: Representation Schemes for Natural Numbers
Post by Deedlit on Apr 15^th, 2005, 4:44pm

Just to be sure: 100 is lex smaller than 11, right?

If so, then the following is halfway decent: the numbers in "step i" are represented by a prefix of i-1 1's and one 0, followed by f(i) = i^2 bits which can be either 0 or 1.

So we start with

1 = 00
2 = 01

and then

3-18 = 10abcd

and then

19-530 = 110abcdefghi

and so on. We can make f(i) larger to improve the best cases, or make f(i) smaller to improve the worst cases. I chose f(i) = i^2 so that,

lim_{n -> [infty]} L_R(i)/lg(i) = 1.

However, it's nowhere near absolutely dominant!

Define g(R,i) = L_R(2ⁱ) - i. Let R_f be the above representation using f(i). If a representation (call it S) beats all R_f then we must have g(S,i) be eventually less than g(R_f,i) for all f. Since g(R_f, f(i)) <= i and f is arbitrary, we cannot have that limsup g(S,i) = [infty]. Hence there is an upper bound to how many "extra bits" representation S uses. But this is impossible. In a set of binary sequences where no element is the prefix of another, each sequence of length n uses up a 2^-n portion of the available space; if we have L_S(n) < lg(n) + c for some c, then the total space used is

[sum]_n 2^-L_S(n)
> [sum]_n 2^{-lg(n) - c}
> [sum]_i 2^i-1 2^-i-c
= [sum]_i 2^-1-c
= [infty].

But from reading Barukh's original post, it looks like he was leading to there actually being such a representation. Hmmm...

Title: Re: Representation Schemes for Natural Numbers
Post by Leonid Broukhis on Apr 15^th, 2005, 8:17pm

Define log_* (n) ::= the number of recursive applications of floor(log₂(x)) to n to reach 0. Define L_i(n) ::= the i^th value
in the reversed sequence of results of such applications, ending with n.
The sequence always starts with L₀(n) = 0, L₁(n) = 1.
Then write log_*(n) 1's, a 0, the value of L₂(n) if it exists without the most significant 1, the value of L₃(n) if it exists without the 1, etc. The length of L_i(n) in bits is defined by L_i-1(n).

L is for Levenstein who first described such coding, of course.

So,
0 -> 0,
1 -> 10
2 -> 1100
3 -> 1101
4 -> 1110000
5 -> 1110001
6 -> 1110010
7 -> 1110011
8 -> 11101000
9 -> 11101001
...
2¹⁰⁰ = 111110 0 10 100100 and 100 0's
2¹⁰⁰⁰ = 111110 1 001 111101000 and 1000 0's

Title: Re: Representation Schemes for Natural Numbers
Post by Deedlit on Apr 17^th, 2005, 5:27am

After reading Leonid's post, I noticed something interesting: If we have a representation scheme R that involves an initial string of 1's that increases with n, we can take any representation scheme S (which can be R itself) and replace the initial string of 1's with the representation for the length of that string. The fact that S is prefix-avoiding and lex-increasing will imply that this new representation scheme is prefix-avoiding and lex-increasing. If we think of this as a "product" S*R, then Leonid's scheme L is like my R_f with f(i)=i, taken to the infinite power. But we can take powers Lⁱ, which will have initial strings of 1's of length (log_*)⁽ⁱ⁾ (n); if we take the "infinite power" again, we can reduce the length of the initial string to the inverse of Ackermann(4,n), using the first definition of Ackermann from the "unusual sequence" thread. Continuing in this fashion, we can eventually reach the inverse of the full Ackermann function and beyond, and each subsequent scheme will dominate all the previous ones.

Of course, I don't know if this sequence approaches the best possible asymptotics; there might be some scheme which blows them all away!