The Oldenburger-Kolakoski sequence, $OK$, is the unique sequence of $1$s and $2$s that starts with $1$ and is its own runlength sequence:

$$OK = (1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,\ldots).$$

For $n \geq 1$, let $a(n)$ be the number of indices $h \leq n$ such that $OK(h) =1$, and let $b(n)$ be the number of $h \leq n$ such that $OK(h) = 2.$

QUESTION. Is $a(n) = b(n)$ for infinitely many $n$?

For example, the first ten runs are $1,22,11,2,1,22,1,22,11,2$, and the lengths of these runs are $1,2,2,1,1,2,1,2,2,1$.

In the OEIS, the sequence is A000002. There are several related easily stated unsolved problems, such as the conjecture that the limiting density of $1$'s is $1/2$.


The short answer is: nobody knows. To me this problem looks even harder than the problem of limit densities or other open problems like whether the sequence is recurrent and mirror/reversal invariant.

The general opinion among the ones who studied the problem is that it's very unlikely that $d(1)$ doesn't exists (this is in fact another open question), and provided that it exists, your claim is actually much stronger than $d(1)=1/2$.

Some heuristics: let $T(w)$ be the operator associating to every word in $\{1,2\}^*$ the word $v$ starting with 1 and such that $w$ lists the lengths of the runs of $v$ (example: $T(1221)=122112$). If you believe that the parity of the lengths $\ell(T^k(w))$ "behaves like" a Bernoulli variable with probability $1/2$, then "it follows" that the sequence is recurrent and that $d(1)$ equals 1/2 (if it exists). But even assuming this strong heuristic viewpoint, your claim would still be far from obvious.


This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .