5
$\begingroup$

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$.

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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