Author |
Topic: Representation Schemes for Natural Numbers (Read 520 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Representation Schemes for Natural Numbers
« on: Apr 15th, 2005, 9:58am » |
 Quote  Modify
|
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 LR(n) the length of the representation of number n in R. What is the asymptotic behaviour of LR(n) for your R?
3. Let say that representation R dominates representation Q if
a) There exists N such that LR(n) <= LQ(n) for every n > N.
b) LR(n) < LQ(n) for infinitely many n.
Can you devise an “absolutely dominant” representation (i.e. that dominates every other representation)? What’s its asymptotic behaviour?
|
| « Last Edit: Apr 15th, 2005, 11:38am by Barukh » |
 IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Representation Schemes for Natural Numbers
« Reply #1 on: Apr 15th, 2005, 10:35am » |
Quote Modify
|
1. R(n) = F(n) 1's followed by a 0 where F(n) is a monotonically increasing function over the naturals
2. limn->[inf]LR(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?) 
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Representation Schemes for Natural Numbers
« Reply #2 on: Apr 15th, 2005, 11:40am » |
Quote Modify
|
on Apr 15th, 2005, 10:35am, SMQ wrote:| Are you sure that's what you meant to ask? (Or am I somewhere off my nut again?) --SMQ |
|
Of course, I am not sure ! I mistyped the signs in inequalities.
Corrected.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Representation Schemes for Natural Numbers
« Reply #3 on: Apr 15th, 2005, 4:44pm » |
Quote Modify
|
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,
limn -> [infty] LR(i)/lg(i) = 1.
However, it's nowhere near absolutely dominant!
Define g(R,i) = LR(2i) - i. Let Rf be the above representation using f(i). If a representation (call it S) beats all Rf then we must have g(S,i) be eventually less than g(Rf,i) for all f. Since g(Rf, 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 LS(n) < lg(n) + c for some c, then the total space used is
[sum]n 2-LS(n)
> [sum]n 2-lg(n) - c
> [sum]i 2i-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...
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Representation Schemes for Natural Numbers
« Reply #4 on: Apr 15th, 2005, 8:17pm » |
Quote Modify
|
Define log* (n) ::= the number of recursive applications of floor(log2(x)) to n to reach 0. Define Li(n) ::= the ith value
in the reversed sequence of results of such applications, ending with n.
The sequence always starts with L0(n) = 0, L1(n) = 1.
Then write log*(n) 1's, a 0, the value of L2(n) if it exists without the most significant 1, the value of L3(n) if it exists without the 1, etc. The length of Li(n) in bits is defined by Li-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
...
2100 = 111110 0 10 100100 and 100 0's
21000 = 111110 1 001 111101000 and 1000 0's
|
| « Last Edit: Apr 15th, 2005, 8:26pm by Leo Broukhis » |
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Representation Schemes for Natural Numbers
« Reply #5 on: Apr 17th, 2005, 5:27am » |
Quote Modify
|
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 Rf with f(i)=i, taken to the infinite power. But we can take powers Li, which will have initial strings of 1's of length (log*)(i) (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!
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print