Kolakoski sequence

ITT we prove that the Kolakoski sequence has the same density of 1s and 2s.

It's defined as the unique sequence of only 1s and 2s starting with 12 such that the [math]n^{th}[/math] element defines the run length of the [math]n^{th}[/math] run of elements.

The sequence starts as follows: 12211212212211211221211. It's also not hard to calculate either once you're used to it, so don't get put off too fast.

Notice that when we group the runs of elements and create the sequence of their lengths, we recover the original sequence.

[1][22][11][2][1][22][1][22][11][2][11][22][1][2][11]

Taking the size of each bracketed group we get 122112122122112, which matches the original sequence.

Conversely, by grouping every pair of elements, and then expanding them with the following rules, we also recover the original sequence.

Here are the rules.

[math]11 \rightarrow 12[/math]
[math]12 \rightarrow 122[/math]
[math]21 \rightarrow 112[/math]
[math]22 \rightarrow 1122[/math]

Group every other pair of consecutive elements in the sequence, and then expand using the rules.

[12][21][12][12][21][22][11][21][12][21][21]
122112122122112112212112122112112

Again, we recover the original sequence.

Note that this last mentioned property can used to generate the sequence.

Also, better methods exist, with the best I've seen allowing you to calculate that [math]n^{th}[/math] element of this sequence using O(log(n)) memory rather than O(n) memory as the naive method hinted at above would use.

Let's do this shit senpaitachi.

en.wikipedia.org/wiki/Kolakoski_sequence
oeis.org/A000002

We can write a proof by considering the rules as a singular transformation which preserves a uniform density. Thus equipartition of the 1s and 2s is unchanged while the number of digits increases. Thusly fluctuating from 12->122 to 22->1122 or 21->112 composes a cycle with closure such that the density on the RHS remains uniform.

Right now I would not mind oz.

Thanks for introducing something to me, but, help me write a novel paper thread sounds a lot like a homework thread.

Maybe I'm misunderstanding you, but consider this.

1212121212...

If we expand this sequence according to the rules above we get this.

122122122122122...

So obviously, for some sequences of 1s and 2s, we fail to keep an even distribution in the expanded sequence.

How would you handle something like that?

>It's defined as the unique sequence of only 1s and 2s starting with 12 such that the
show me the proof of the uniqueness

Not OP, but

The example sequence does not follow the rules of being its own run-length encoding.

Uniqueness is irrelevant to the problem.

OP: Are you aware if there exist similar sequences for, say, {1, 2, 3}?

First note that the symbol of each run will alternate between 1 and 2, starting with 1. So that very first 2 tells you that you'll have another 2, and then after that you must have some 1s, and the amount is defined by the value after that first 2. In general, we'll be reading some symbols behind where we're writing symbols, since we always write at least 1 symbol, and sometimes 2, but we only ever read off a single symbol.

Anyways, the whole point here is that your given initial configuration forces you to expand what you've got with only 1 possible value.

You could make this a bit more rigorous just by going for a simple contradiction by showing where they first differ (assuming both plausible sequences started with 12), that there must by some "parent" symbol which defines the run length including the element before the differing symbol, so one of the two sequences must be wrong.

I've probably rambled a bit, and didn't structure this good, but there's your proof pleb.

It's actually all pretty trivial.

I am implicitly using a closed cycle to take a limit in the final step of my proof.

Do you want me to exhaust the example and write out the matrix algebra?

I want oz.

>OP: Are you aware if there exist similar sequences for, say, {1, 2, 3}?
Yes.

Something else that's interesting, is that the corresponding sequence for {1, 3} is "trivial" to analyze, and gives about 62.08% 3s.

>Do you want me to exhaust the example and write out the matrix algebra?
Sure.

>>You could make this a bit more rigorous just by going for a simple contradiction
>rigorous
>by contradiction

found the pleb

>Sure.
Not sure if OP but I recognize the writing voice.
So if I may take the aforementioned sequence
122122122122122...
and bracket it like so:
[12][21][22][12][21][22]...
the sequence converges in the next step of the cycle:
[122][112][1122][122][112][1122]...

In simpler terms, the singular transformation is transitive with respect to the final, uniform density. An adjacency matrix on the morphisms is equivalent to the identity matrix.

>>>You could make this a bit more rigorous just by going for a simple contradiction
>>rigorous
>>by contradiction

>found the pleb

I am glad someone pointed that out.

Consider this similar but different sequence where we use 1s and 3s instead of 1s and 2s.

Our rules would become this.

[math]11 \rightarrow 13[/math]
[math]13 \rightarrow 1333[/math]
[math]31 \rightarrow 1113[/math]
[math]33 \rightarrow 111333[/math]

Would what you have still imply that this sequence has an equal distribution of 1s and 3s?

No, because there are triplets instead of pairs.

31 is less likely to occur as a result of the greater word length. There is no monad limit cycle because the iterated transformations are chaotic.

>Thusly fluctuating from 12->122 to 22->1122 or 21->112 composes a cycle with closure
What's that supposed to mean?

>What's that supposed to mean?
You sound offended.
We have a closed cycle with uniformly distributed digits after 11->12.

>You sound offended.
Not at all.

>We have a closed cycle
This is what I'm trying to figure out.

How is
>12->122 to 22->1122 or 21->112
a cycle?
I don't understand.

I don't quite understand?
From this sequence [1][22][11][2][1][22][1][22][11][2][11][22][1][2][11], this sequence 122112122122112 can easy be calculated without looking at the length of the bracketed parts. You can obtain a O(n) solution by looking at the next number in the sequence if the nth element is equal to that of the n+1th element then we can count 2, if not we can count 1.

Is that what we are trying to do here?

It's just showing some of the properties of the sequence. That one in particular isn't very useful for calculating much, but I think it does make it clear how the [math]n^{th}[/math] run length equals the [math]n^{th}[/math] element.

The transformation constitutes a cycle after the first step as given in the example.

11 directly maps to 12, so the other three, {[12],[21],[22]} suffice to show a closed cycle.

In more detailed terms: {[11], [12],[21],[22]} is not irreducible, because {[11]->[12], [12],[21],[22]} is simplified as {[12],[21],[22]}. It is necessary to show a monad so that the limit cycle is sufficient proof of the stationary density of digits.

I think you were implying that in the first place, so my supposition is referential to that context.
Please excuse my terseness.

How is a monad limit cycle sufficient proof of the stationary density of digits?

The density of digits is stationary under the left singular transformation because the elements constitute a limit cycle functor into the unit map, so that the multiplication map abridges the [11]->[12] transformation. The monad laws hold so that the multiplication map produces a stationary, uniform distribution; and the unit map goes into the multiplication map.

You're purposefully trying to not make sense.

What is that supposed to mean?

Are there any other useful properties that it has?

This is equivalent to proving that there is no correlation between the parity of n and the parity of the nth element (because if there was a correlation then even or odd runs would be more likely to be double runs, thus unbalancing the ratio). I don't know where to go from there.

bump

bump