More on compressed numbers

Spoiler alert: we are going to discuss about the previous post, and we will give the solution to the puzzle…

So, the sequence to study was 2, 12, 1112, 3112, 132112… It is easy if you read it aloud: “2” is “one two”, so “12”, which in turn is “one one, one two”, “1112”, and so on.

Let us get abstract. The transformation that takes from one sequence to the next, e.g., from 12 to 1112,  is a kind of description, so we will denote it with the letter D. Transformation D is the most basic compression algorithm! Imagine that you have a sequence like “333333333”. Then, under the operation of D, it transforms to “93”, which is a neat compression. But the main lesson we get from here is that compression algorithms may expand if used without control… This trick  is widely known, it appears as a puzzle for computer science students, normally starting with number 1, so: 1, 11, 21, 1211, etc. I preferred to start with 2, so that you wouldn’t find it on the web… :)

But the properties of this operator are not studied out there, as far as I know… I have been thinking a bit, and today I just made a computer program to mess around… I got a few questions for you:

  • The sequence “22” is “self-descriptive”, in the sense that D(22)=22. Are there any other self-descriptive sequences?
  • How does the length of the sequence D^n(1) grow? I mean: each step is increasing the length of the sequence. Is this going to stop? Is it going to grow exponentially, or what? Why?
  • Can all numbers appear in the sequence D^n(1)? Why?
  • Let us call a sequence “primitive-1” if it comes from the expansion of a sequence of a single number, i.e.: all the D^n(k), for all n and k. Is there any property that will tell us when a sequence is primitive-1?

I have a few hints regarding these questions, but I don’t have the answer to all of them, so we’ll play together, if you want…

Advertisements

12 thoughts on “More on compressed numbers

  1. I’m sorry Javi, but it seems that the operator have been well studied:
    http://en.wikipedia.org/wiki/Look-and-say_sequence

    And I have found it just when I was writing this:

    (…) We have a string of numbers, and we can split it in groups with the same digit. If N is the number of digits of the group, when we apply the operator on the group we get [log (N)] + 2 digits ([x] means floor of x)
    So when the number of digits (N) is greater than the result of this expresion, the group gets compressed (…)

    But we keep on it, whatever means “it” (“from lost to the river” tanslation ;-) )

  2. So, Paco’s link has answered my first three questions:

    (i) The only self-descriptive sequence is “22”
    (ii) The growth is exponential for any other seed, with the same growth factor. My measurement (empirical) is 1.303575, while Conway proved that it is the root of a certain polynomial, and gave the value 1.303577.
    (iii) No numbers beyond 1,2,3 appear if they’re not in the first two instances.

    And the whys? And the fourth one? Do you have any more questions?

  3. A little demonstration of property (i): an instance that is self-descriptive means that all its groups of equal digits are self-descriptive.
    If a group is self-descriptive the number of digits must be kept after expansion. If the number of digits is N we have to solve the following equation:
    [log (N)] + 2 = N
    The solution is N=2, and as it becomes the first digit of the group transformation, the other digit must be 2.

    And an easy question: is there any property which tell us if a instance can come from a expansion? I think it’s a first step for solving the fourth question.

  4. Your equation, N’=[log(N)]+2 is with a base-10 log, right? I think you’re assuming that if we have “10 3’s”, then the result is “103”, not “10,3”. I was assuming the second, but both are interesting :)

    About your “easy question”, consider the “inverse operator” to D. Any sequence with an even number of elements can be “inverted”…

  5. Yes it’s a base-10 log. And yes to the second too.

    The even number of elements is necesary, but not enough. P.e. 1111 can’t be the result of a expansion.

    If the string S: a0b0a1b1a2b2…..
    is the result of a expansion, it must happen that b0 b1, b1 b2, ….

    I’m not sure if there are more conditions, I’m working on it.

    • ¿What happened with all the indexes and symbols in my comment?
      Let’s try it with latex:

      Yes it’s a base-10 log. And yes to the second too.

      The even number of elements is necesary, but not enough. P.e. 1111 can’t be the result of a expansion.

      If the string S: a_0 b_0 a_1 b_1 a_2 b_2…..
      is the result of a expansion, it must happen that b_0 != b_1, b_1!= b_2, ….

      I’m not sure if there are more conditions, I’m working on it.

  6. About latex: \neq is the command you’re looking for ;)

    And you’re right… the thing is that all sequences can be “formally” inverted, in the sense that 1111 would “come from” 11, but without following the rules really. So, there must be some conditions on “feasible” sequences…

  7. Well, I’ve been thinking about the conditions and i’m sure that these are the only two conditions for constructing a instance as the expansion of other instance.

    And with the condition b_{n+1} \neq b_n (thanks Javi) it is obvious that there can’t be groups of equal digits with more than three elements => property (iii)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s