Kolakoski sequence

In mathematics, the Kolakoski sequence is an infinite list that begins with

1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,...

This is an example of a self-generating sequence, as indicated here:

(1) write 1; read it as the number of 1's to write before switching to 2;

(2) write 2; read it as the number of 2's to write before switching back to 1;

(3) so far... 1,2,2; read the new 2 as the number of 1's to write;

(4) so far... 1,2,2,1,1; read the new 1,1 as the number of 2's and then 1's to write;

(5) so far... 1,2,2,1,1,2,1; continue generating forever.

It seems plausible that the density of 1's is 1/2, but this conjecture remains unproved. This and related simply stated unsolved problems are presented at [http://faculty.evansville.edu/ck6/integer/index.html Integer Sequences and Arrays.] Attempts to solve them are referenced at [http://mathworld.wolfram.com/KolakoskiSequence.html MathWorld] and sequence [http://www.research.att.com/~njas/sequences/?q=A000002&sort=0&fmt=0&language=english A000002] at Online Encyclopedia of Integer Sequences. In the unpublished technical report [http://dimacs.rutgers.edu/TechnicalReports/abstracts/1993/93-84.html Notes on the Kolakoski Sequence] , Chvátal proved that the upper density of 1's is less than 0.50084.

Kolakoski's self-generating sequence has attracted the interest of computer scientists as well as mathematicians. For example, in [http://en.wikipedia.org/wiki/A_New_Kind_of_Science "A New Kind of Science,] " p. 895, [http://en.wikipedia.org/wiki/Stephen_Wolfram Stephen Wolfram] describes the Kolakoski sequence in connection with the history of cyclic tag systems.

William G. Kolakoski

William George Kolakoski (Sept. 17, 1944 - July 26, 1997) published only one mathematical item, wherein he introduced the sequence that now bears his name. The publication is "Advanced Problem 5304" in the "American Mathematical Monthly," submitted during his student years at Carnegie Institute of Technology (now [http://en.wikipedia.org/wiki/Carnegie_Mellon_University Carnegie-Mellon University] ), where he received the Bachelor of Fine Arts Degree in painting in 1967.

The selfness of the Kolakoski sequence, together with its pairing of simplicity and complexity, match Kolakoski's life-experience. In the words of one of his classmates, Pittsburgh-based writer Mike Vargo:

I see Bill's mathematical interests as being a piece with his philosophical and psychological interest. Bill was EXTREMELY obsessed with fundamentals and essentials... As you may know, Bill was a chronic schizophrenic, prone to florid delusional episodes if he didn't take his meds. And that, I think, is a key point, for reasons I'll now try to explain.

Here was this extremely active and facile mind...yet there was this thing living within him that was always threatening to "take over"... So, given this paradoxical situation, one subject which preoccupied Bill was the question of free will. This was the central question of his existence. He wanted to think he was free, yet he knew all too well the power of an "invisible hand," and this drove him to determinism. Back and forth he went...it seems to me that, given this quandary, it was very natural for him to try to create a self-generating number sequence. This particular form of mathematical exercise seems a natural byproduct of a mind preoccupied with the question of free will.

You "invent" the sequence yourself, thus exercising free will — and yet — it was already "there" waiting for you, wasn't it, so actually you just "discovered" it...and once you set it in motion, it goes on self-generating in marvelous order, turning into a profoundly pleasing manifestation of determinism.

[From a letter from Mike Vargo to Clark Kimberling, Feb. 6, 2001.]

Kolakoski fan

The Kolakoski fan is the following array:

1

2

2 2

1 1 2

1 1 2 2 1 2 1 1 2 2 2 1 1 2 1 2 2 1 1 (and continue)

Associated with this array, indexed as [http://www.research.att.com/~njas/sequences/?q=A143477&language=english&go=Search A143477] (in the Online Encyclopedia of Integer Sequences) are many other such arrays, such as [http://www.research.att.com/~njas/sequences/?q=A111090&sort=0&fmt=0&language=english&go=Search A111090] , for which it is conjectured that the growth rate of row-length is asymptotic to "c"(3/2) ^"n" for some constant "c".

External links

* [http://mathworld.wolfram.com/KolakoskiSequence.html Kolakoski Sequence]
* [http://www.research.att.com/~njas/sequences/ Online Encyclopedia of Integer Sequences] (search "Kolakoski")
* [http://pi.lacim.uqam.ca/piDATA/Kolakoski.txt Kolakoski Constant to 25000 Digits.]

References

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

Vašek Chvátal, "Notes on the Kolakoski Sequence", DIMACS Technical Report 93-84, December 1993.

F. M. Dekking, "What Is the Long Range Order in the Kolakoski Sequence?" In "Proceedings of the NATO Advanced Study Institute" held in Waterloo, ON, August 21-September 1, 1995 (dd. R. V. Moody). Dordrecht, Netherlands: Kluwer, pp. 115-125, 1997.

M. S. Keane, "Ergodic Theory and Subshifts of Finite Type." In "Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces" (ed. T. Bedford and M. Keane). Oxford, England: Oxford University Press, pp. 35-70, 1991.

William Kolakoski, proposal 5304, "American Mathematical Monthly" 72 (1965), 674; for a partial solution, see "Self Generating Runs," by Necdet Üçoluk, "Amer. Math. Mon." 73 (1966), 681-2.

J. C. Lagarias, "Number Theory and Dynamical Systems." In "The Unreasonable Effectiveness of Number Theory" (ed. S. A. Burr). Providence, RI: Amer. Math. Soc., pp. 35-72, 1992.

G. Paun and A. Salomaa, "Self-Reading Sequences." "Amer. Math. Monthly" 103, 166-168, 1996.

Bertran Steinsky, "A Recursive Formula for the Kolakoski Sequence A000002," "Journal of Integer Sequences" 9 (2006) Article 06.3.7.