The Oldenburger-Kolakoski Sequence

Statement:

The Oldenburger-Kolakoski Sequence, A000002 is given by \(a(n)\) is the length of the n-th run; \(a(1)=1\). $$122112122122112112212112122\ldots$$ Question: Show that the density of 1's in this sequence is equal to 1/2.

Author	Date Published	Prize	Paid By
Oldenburger-Kolakoski	1939

Partial Results:

[11] If we map 1 to +1 and 2 to -1, then the mapped sequence would have a [conjectured] mean of 0, since the Kolakoski sequence is [conjectured] to have an equal density (1/2) of 1s and 2s. For the partial sums of this mapped sequence, see A088568. - Daniel Forgues, Jul 08 2015

[12] Looking at the plot for A088568, it seems that although the asymptotic densities of 1s and 2s appear to be 1/2, there might be a bias in favor of the 2s. I.e., \( D(1) = 1/2 - O(log(n)/n), D(2) = 1/2 + O(log(n)/n) \). - Daniel Forgues, Jul 11 2015

Related Problems:



References:

[1] Clark Kimberling Unsolved Problems and Rewards

[2] J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 337.

[3] E. Angelini, "Jeux de suites", in Dossier Pour La Science, pp. 32-35, Volume 59 (Jeux math'), April/June 2008, Paris.

[4] F. M. Dekking, What Is the Long Range Order in the Kolakoski Sequence?, in The mathematics of long-range aperiodic order (Waterloo, ON, 1995), 115-125, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., 489, Kluwer Acad. Publ., Dordrecht, 1997. Math. Rev. 98g:11022.

[5] M. S. Keane, Ergodic theory and subshifts of finite type, Chap. 2 of T. Bedford et al., eds., Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces, Oxford, 1991, esp. p. 50.

[6] J. C. Lagarias, Number Theory and Dynamical Systems, pp. 35-72 of S. A. Burr, ed., The Unreasonable Effectiveness of Number Theory, Proc. Sympos. Appl. Math., 46 (1992). Amer. Math. Soc.

[7] Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.

[8] N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

[9] N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

[10] I. Vardi, Computational Recreations in Mathematica. Addison-Wesley, Redwood City, CA, 1991, p. 233.

[11] Daniel Forgues, Jul 08 2015, OEIS A000002

[12] Daniel Forgues, Jul 11 2015, OEIS A000002

Keywords:

OEIS; Oldenburger-Kolakoski Sequence; string;