1,2

It is an unsolved problem to show that the density of 1's is equal to 1/2.

The sequence is cube-free and all square subwords have lengths which are one of 2, 4, 6, 18 and 54.

This is a fractal sequence: replace each run by its length and recover the original sequence. - Kerry Mitchell (lkmitch(AT)gmail.com), Dec 08 2005

Kupin and Rowland write: We use a method of Goulden and Jackson to bound freq_1(K), the limiting frequency of 1 in the Kolakoski word K. We prove that |freq_1(K) - 1/2| <= 17/762, assuming the limit exists and establish the semi-rigorous bound |freq_1(K) - 1/2| <= 1/46. [From Jonathan Vos Post (jvospost3(AT)gmail.com), Sep 16 2008]

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

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

F. M. Dekking, On the structure of self-generating sequences, Seminar on Number Theory, 1980-1981 (Talence, 1980-1981), Exp. No. 31, 6 pp., Univ. Bordeaux I, Talence, 1981. Math. Rev. 83e:10075.

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.

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.

W. Kolakoski, Problem 5304, Amer. Math. Monthly, 72 (1965), 674; 73 (1966), 681-682.

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.

G. Paun and A. Salomaa, Self-reading sequences, Amer. Math. Monthly 103 (1996), no. 2, 166-168.

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

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

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

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

N. J. A. Sloane, Table of n, a(n) for n = 1..10502

J.-P. Allouche, M. Baake, J. Cassaigns and D. Damanik, Palindrome complexity

Michael Baake and Bernd Sing, Kolakoski-(3,1) is a (deformed) model set

C. Kimberling, Integer Sequences and Arrays, Illustration of the Kolakoski sequence

Elizabeth J. Kupin and Eric S. Rowland, Bounds on the frequency of 1 in the Kolakoski word, Sep 16, 2008. [From Jonathan Vos Post (jvospost3(AT)gmail.com), Sep 16 2008]

A. Scolnicov, PlanetMath.org, Kolakoski sequence

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

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Index entries for "core" sequences

Omit the initial 1 (so this remark is really about A078880). Then the sequence can be generated by starting with 22 and applying the block-substitution rules 22 -> 2211, 21 -> 221, 12 -> 211, 11 -> 21 (Lagarias)

These two formulae define completely the sequence: a(1)=1, a(2)=2, a(a(1)+a(2)+...+a(k))=(3+(-1)^k)/2 and a(a(1)+a(2)+...+a(k)+1)=(3-(-1)^k)/2 - Benoit Cloitre (benoit7848c(AT)orange.fr), Oct 06 2003

a(n+2)*a(n+1)*a(n)/2 = a(n+2)+a(n+1)+a(n)-3 (this formula doesn't define the sequence, just a consequence of definition) - Benoit Cloitre (benoit7848c(AT)orange.fr), Nov 17 2003

Start with a(1) = 1, a(2) = 2. The rule says that the first run (which is a single 1) has length 1, which it does and the second run (which starts with the 2) has length 2, so the third term must be a 2 also and the fourth term can't be a 2, so must be a 1. So we have a(3) = 2, a(4) = 1. Since a(3) =2, the third run has length 2, so we deduce a(5) = 1, a(6) =2. And so on. The correction I made was to change a(4) to a(5) and a(5) to a(6). (From Labos, E., corrected by Graeme McRae)

M := 100; s := [ 1, 2, 2 ]; for n from 3 to M do for i from 1 to s[ n ] do s := [ op(s), 1+((n-1)mod 2) ]; od: od: s; A000002 := n->s[n];

a[steps_] := Module[{a = {1, 2, 2}}, Do[a = Append[a, 1 + Mod[(n - 1), 2]], {n, 3, lst}, {i, a[[n]]}]; a]

(PARI) a=[ 1, 2, 2 ]; for(n=3, 80, for(i=1, a[ n ], a=concat(a, 1+((n-1)%2)))); a

(PARI) a(n)=local(an, m); if(n<1, 0, an=[1, 2, 2]; m=3; while(length(an)<n, an=concat(an, vector(an[m], i, (m-1)%2+1)); m++); an[n])

Cf. A064353, A001462, A001083, A006928, A042942, A069864, A010060, A078880.

Cf. A079729, A079730. [From Franklin T. Adams-Watters (FrankTAW(AT)Netscape.net), Mar 13 2009]

Sequence in context: A074293 A013949 A078880 this_sequence A074295 A116514 A124767

Adjacent sequences: A000001 this_sequence A000003 A000004 A000005

nonn,core,easy,nice

N. J. A. Sloane (njas(AT)research.att.com).

Replace arxiv URL by a the non-cached version - R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Oct 07 2009