%I A000002 M0190 N0070
%S A000002 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,2,1,1,2,1,2,
               2,
%T A000002 1,2,2,1,1,2,1,2,2,1,2,1,1,2,1,1,2,2,1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,
               2,
%U A000002 1,2,2,1,2,1,1,2,2,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
%N A000002 Kolakoski sequence: a(n) is length of n-th run; a(1) = 1; sequence consists 
               just of 1's and 2's.
%C A000002 It is an unsolved problem to show that the density of 1's is equal to 
               1/2.
%C A000002 The sequence is cube-free and all square subwords have lengths which 
               are one of 2, 4, 6, 18 and 54.
%C A000002 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
%C A000002 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]
%D A000002 J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 
               2003, p. 337.
%D A000002 E. Angelini, "Jeux de suites", in Dossier Pour La Science, pp. 32-35, 
               Volume 59 (Jeux math'), April/June 2008, Paris.
%D A000002 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.
%D A000002 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.
%D A000002 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.
%D A000002 W. Kolakoski, Problem 5304, Amer. Math. Monthly, 72 (1965), 674; 73 (1966), 
               681-682.
%D A000002 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.
%D A000002 G. Paun and A. Salomaa, Self-reading sequences, Amer. Math. Monthly 103 
               (1996), no. 2, 166-168.
%D A000002 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 
               (includes this sequence).
%D A000002 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A000002 Bertran Steinsky, A Recursive Formula for the Kolakoski Sequence A000002, 
               Journal of Integer Sequences, Vol. 9 (2006), Article 06.3.7.
%D A000002 I. Vardi, Computational Recreations in Mathematica. Addison-Wesley, Redwood 
               City, CA, 1991, p. 233.
%H A000002 N. J. A. Sloane, <a href="b000002.txt">Table of n, a(n) for n = 1..10502</
               a>
%H A000002 J.-P. Allouche, M. Baake, J. Cassaigns and D. Damanik, <a href="http:/
               /www.lri.fr/~allouche/">Palindrome complexity</a>
%H A000002 Michael Baake and Bernd Sing, <a href="http://arXiv.org/abs/math.MG/0206098">
               Kolakoski-(3,1) is a (deformed) model set</a>
%H A000002 C. Kimberling, Integer Sequences and Arrays, <a href="http://faculty.evansville.edu/
               ck6/integer/index.html">Illustration of the Kolakoski sequence</a>
%H A000002 Elizabeth J. Kupin and Eric S. Rowland, <a href="http://arxiv.org/abs/
               0809.2776">Bounds on the frequency of 1 in the Kolakoski word</a>
               , Sep 16, 2008. [From Jonathan Vos Post (jvospost3(AT)gmail.com), 
               Sep 16 2008]
%H A000002 A. Scolnicov, PlanetMath.org, <a href="http://planetmath.org/encyclopedia/
               KolakoskiSequence.html">Kolakoski sequence</a>
%H A000002 Bertran Steinsky, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL9/
               Steinsky/steinsky5.html">A Recursive Formula for the Kolakoski Sequence 
               A000002</a>, J. Integer Sequences, Vol. 9 (2006), Article 06.3.7.
%H A000002 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               KolakoskiSequence.html">Link to a section of The World of Mathematics.</
               a>
%H A000002 <a href="Sindx_Cor.html#core">Index entries for "core" sequences</a>
%F A000002 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)
%F A000002 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
%F A000002 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
%e A000002 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)
%p A000002 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];
%t A000002 a[steps_] := Module[{a = {1, 2, 2}}, Do[a = Append[a, 1 + Mod[(n - 1), 
               2]], {n, 3, lst}, {i, a[[n]]}]; a]
%o A000002 (PARI) a=[ 1,2,2 ]; for(n=3,80, for(i=1,a[ n ],a=concat(a,1+((n-1)%2)))); 
               a
%o A000002 (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])
%Y A000002 Cf. A064353, A001462, A001083, A006928, A042942, A069864, A010060, A078880.
%Y A000002 Cf. A079729, A079730. [From Franklin T. Adams-Watters (FrankTAW(AT)Netscape.net), 
               Mar 13 2009]
%Y A000002 Sequence in context: A074293 A013949 A078880 this_sequence A074295 A116514 
               A124767
%Y A000002 Adjacent sequences:   A000001 this_sequence A000003 A000004 A000005
%K A000002 nonn,core,easy,nice
%O A000002 1,2
%A A000002 N. J. A. Sloane (njas(AT)research.att.com).
%E A000002 Replace arxiv URL by a the non-cached version - R. J. Mathar (mathar(AT)strw.leidenuniv.nl), 
               Oct 07 2009