Read out the bottom sequence of run lengths, and be amazed that it's the same as the first 7 digits as the top sequence. Extend the bottom to continue to recapitulate the top sequence, and add terms to the top sequence accordingly to reflect the run lengths in the bottom sequence. Repeat infinitely.
AnotherGoodName 1 days ago [-]
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?
robotpepi 16 hours ago [-]
> So there's nothing about this particular sequence?
Kolakoski's sequence is conjectured to be "uniformly recurrent", which means that every block of contiguous symbols appearing once in the sequence appears infinitely often and with bounded gaps. This is clearly not true for any sequence constructed like this. And the fact that we don't know how to prove uniform recurrence for Kolakoski's, which is arguably the simplest sequence defined by this method, is remarkable. There are other conjectures about frequencies of symbols, etc.
MontyCarloHall 1 days ago [-]
>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--
What are the values of x and y?
>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.
AnotherGoodName 1 days ago [-]
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).
flufluflufluffy 1 days ago [-]
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)
MontyCarloHall 1 days ago [-]
You are still choosing random numbers here. The Kolakoski sequence has zero randomness whatsoever.
AnotherGoodName 1 days ago [-]
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.
MontyCarloHall 1 days ago [-]
This is just the Kolakoski sequence starting from the second term.
A few hops away, the non-mathematical part of this story is interesting[0] and Conway's related weird world of audio-active decay is another recurring favorite[1]. Both are even more fun with esolangs[2]. I'm sure I've heard audio-encodings of Kolakoski before, but couldn't find any with a quick search
Is it a coincidence that it is number 2 in the OEIS?)
1 days ago [-]
globalnode 1 days ago [-]
does it repeat? or is it like pi? -- oh the wiki says its an infinite sequence. that might be handy for generating pseudo random numbers i guess. i wonder if theres a function that generates the correct digit at position n? doh, wiki says theres a recursive formula for the i'th term.
robotpepi 17 hours ago [-]
nwellnhof shared a link with a more efficient method for generating it.
although the sequence is not completely random (there are around n^alpha length-n blocks of contiguous symbols, for some alpha in [2,3) ), what people have done with other sequences is to take two simple PRNG (e.g. from a linear recurrence mod p) and alternate them according to the symbol you read from the sequence.
and the sequence does repeat. it is conjectured that any finite block of contiguous symbols occurs infinitely many times and moreover the gap between consecutive occurrences is uniformly bounded.
vindex10 23 hours ago [-]
it doesn't repeat at least:
> More generally, the sequence is cube-free, i.e., has no substring of the form w w w with w some nonempty finite string.
from wiki
Rendered at 22:30:22 GMT+0000 (Coordinated Universal Time) with Vercel.
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?
Kolakoski's sequence is conjectured to be "uniformly recurrent", which means that every block of contiguous symbols appearing once in the sequence appears infinitely often and with bounded gaps. This is clearly not true for any sequence constructed like this. And the fact that we don't know how to prove uniform recurrence for Kolakoski's, which is arguably the simplest sequence defined by this method, is remarkable. There are other conjectures about frequencies of symbols, etc.
No, because there's no deterministic way to infinitely extend that sequence. In your first example:
What are the values of x and y?>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.
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).
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.
[0] https://en.wikipedia.org/wiki/William_Kolakoski#Personal_sig... [1] https://en.wikipedia.org/wiki/Look-and-say_sequence [2] https://esolangs.org/wiki/Kolakoski_sequence
although the sequence is not completely random (there are around n^alpha length-n blocks of contiguous symbols, for some alpha in [2,3) ), what people have done with other sequences is to take two simple PRNG (e.g. from a linear recurrence mod p) and alternate them according to the symbol you read from the sequence.
and the sequence does repeat. it is conjectured that any finite block of contiguous symbols occurs infinitely many times and moreover the gap between consecutive occurrences is uniformly bounded.
> More generally, the sequence is cube-free, i.e., has no substring of the form w w w with w some nonempty finite string.
from wiki