Kolakoski Sequence
en.wikipedia.org54 points by surprisetalk 6 days ago
54 points by surprisetalk 6 days ago
For those not getting this immediately (I sure didn't):
_____________
sequence 1 2 2 1 1 2 1 2 2 1
run lens 1 2-- 2-- 1 1 2-- 1
Can't you trivially force this to happen for any sequence?
1, 3, 3, 3, 2, 2, 2, 1, 1, 1, 4, 4,
Goes to
1, 3, 3, 3, 2... Etc.
I could extend this trivially too since the bottom sequence trails the sequence we write up top. If i wanted another '2' down the bottom whatever number i choose up top i just write twice right?
So there's nothing about this particular sequence? I can just create any such sequences trivially; Whenever you start a new count, choose a random number and repeat for a many times as needed for the trailing sequence to match the top sequence.
It seems that this particular variant is uninteresting in the broader picture right? I could write another similar one
2, 2, 1, 1, 2, 1
2, 2, 1, 1, ... etc.
I don't get the specialness here?
>Can't you trivially force this to happen for any sequence?
No, because there's no deterministic way to infinitely extend that sequence. In your first example:
1 3 3 3 2 2 2 1 1 1 4 4 x x y y
1 3---- 3---- 3---- 2-- 2-- 2--
>Whenever you start a new count, choose a random number and repeat for a many times as needed for the trailing sequence to match the top sequence.
You answered your own question. The Kolakoski sequence is special because it does not just pick a random number: the sequence is deterministically encoded by the run lengths, and vice versa.
Pick any number that's not 4 and repeat it twice. For the next 2 after that pick any number that's not that previous number and repeat it twice. So on.
It's not like i had any difficulty coming up with that sequence i wrote to that point.
1 3 3 3 2 2 2 1 1 1 4 4 5 5 6 6 8 1 2... as an example of how trivial it is to continue to this.
I get that if you limit yourself to '1' or '2' you force the choice of next number but even then there's two possibilities of this sequence (start on 1 vs start on 2).
I guess you could say the Kolakoski sequence is special in being the “simplest” version of such a sequence (ignoring the finite trivial case {1} xD)
You are still choosing random numbers here. The Kolakoski sequence has zero randomness whatsoever.
Do we care similarly about the version of this that starts on 2?
2, 2, 1, 1, 2, 1, 2...
2, 2, 1, 1,
Again no randomness. Just a variant of the above and trivial to continue this.
There's a fascinating way to generate the Kolakoski sequence with bit fiddling: https://11011110.github.io/blog/2016/10/14/kolakoski-sequenc...
Is it a coincidence that it is number 2 in the OEIS?)