The Kolakoski word can be defined in a number of different ways, but probably the simplest is as the unique infinite word k over the alphabet {1, 2}, starting with 1, such that the sequence of lengths of blocks of consecutive identical symbols is equal to k itself.

The first few terms are 12211212212211211221211212211211212212211212212112. As you can see, the lengths of successive blocks are 1,2,2,1,1, etc., the sequence itself.

W. Kolakoski asked [Elementary Problem 5304, Amer. Math. Monthly 72 (1965), 674] for a formula for the nth term, and if the sequence is periodic. Recently, however, Jean Berstel and Srecko Brlek reported that the Kolakoski sequence actually appeared as early as 1939, in two papers of Oldenburger, cited below. Thus it should probably be called the Oldenburger-Kolakoski sequence.

A result of Shallit and Swart ["An efficient algorithm for computing the i'th letter of φⁿ (a)", Proc. 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1999, pp. 768-775] that shows that Kolakoski is a member of a general class of sequences (i. e., those generated by finite-state transducers) for which predicting the n'th term of the i'th iterate is provably hard (in a computational complexity sense). Unfortunately this proves nothing about the particular case of the Kolakoski sequence.

A more interesting question is if the symbols "1" and "2" occur with limiting frequency 1/2. This problem is still open. The best result is that if the frequency exists, then the frequency is between .499 and .501, and is due to Chvátal in a technical report.

If, instead of 1's and 2's, we use 1's and 3's, then the resulting sequence is morphic.

The image shows a discussion of the problem at an Oberwolfach meeting, December 16 1988.

References:

A. Carpi. Repetitions in the Kolakovski [sic] sequence. Bull. European Assoc. Theor. Comput. Sci. (50) (1993), 194-196.

A. Carpi. On repeated factors in C^∞-words. Inform. Process. Lett. 52 (1994), 289-294.

V. Chvátal. Notes on the Kolakoski sequence. Technical Report 93-84, DIMACS, March 1994. Revised.

K. Culik II and J. Karhumäki. Iterative devices generating infinite words. In STACS 92, Proc. 9th Symp. Theoretical Aspects of Comp. Sci., Vol. 577 of Lecture Notes in Computer Science, pp. 531-543. Springer-Verlag, 1992.

K. Culik II, J. Karhumäki, and A. Lepistö. Alternating iteration of morphisms and the Kolakovski [sic] sequence. In G. Rozenberg and A. Salomaa, editors, Lindenmayer Systems, pp. 93-103. Springer-Verlag, 1992.

F. M. Dekking. Regularity and irregularity of sequences generated by automata. Sém. Théor. Nombres Bordeaux (1979-80), 9.01-9.10.

F. M. Dekking. On the structure of selfgenerating sequences. Sém. Théor. Nombres Bordeaux (1981), 31.01-31.06.

F. M. Dekking. What is the long range order in the Kolakoski sequence? In R. V. Moody, editor, The Mathematics of Long-Range Aperiodic Order, Vol. 489 of NATO ASI Ser., Ser. C., Math. Phys. Sci., pp. 115-125. Kluwer, 1997.

M. S. Keane. Ergodic theory and subshifts of finite type. In T. Bedford, M. Keane, and C. Series, editors, Ergodic Theory, Symbolic Dynamics, and Hyperbolic Spaces, pp. 35-70. Oxford University Press, 1991.

C. Kimberling. Advanced problem 6281. Amer. Math. Monthly 86 (1979), 793.

C. Kimberling. The Kolakoski sequence and other runners. Unpublished manuscript, 2003.

W. Kolakoski. Elementary problem 5304. Amer. Math. Monthly 72 (1965), 674. Solution, 73 (1966), 681-682.

A. Lepistö. Repetitions in Kolakoski sequence. In G. Rozenberg and A. Salomaa, editors, Developments in Language Theory, pp. 130-143. World Scientific, 1994.

Rufus Oldenburger. Exponent trajectories in symbolic dynamics. Trans. Amer. Math. Soc. 46 (1939), 453-466.

Rufus Oldenburger. Recurrence of symbolic elements in dynamics. Bull. Amer. Math. Soc. 47 (1941), 294-297.

G. Paun. How much Thue is Kolakovski? [sic]. Bull. European Assoc. Theor. Comput. Sci. (49) (February 1993), 183-185.

Chuanlong Shen and Yunbao Huang. Some properties of C^∞-words with applications. SEA Bull. Math. 20 (1996), 19-30.

B. Sing. Kolakoski-(2m, 2n) are limit-periodic model sets. J. Math. Physics 44 (2003), 899-912.

B. Sing. More Kolakoski sequences. Preprint, available at http://arxiv.org/abs/1009.4061, September 21 2010.

R. Steacy. Structure in the Kolakoski sequence. Bull. European Assoc. Theor. Comput. Sci. (59) (1996), 173-182.

B. Steinsky. A recursive formula for the Kolakoski sequence A000002. J. Integer Sequences 9 (2006), Article 06.3.7.

W. D. Weakley. On the number of C^∞-words of each length. J. Combin. Theory. Ser. A 51 (1989), 55-62.

-- JeffreyShallit - 13 Jul 2011

• kolakoski-oberwolfach.JPG: