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 . Are there any other self-descriptive sequences?
- How does the length of the sequence 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 ? 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 , for all and . 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…