|
%I M0190 N0070
%S 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,
%T 2,2,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,
%U 2,1,1,2,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 Kolakoski sequence: a(n) is length of n-th run; a(1) = 1; sequence consists just of 1's and 2's.
%C It is an unsolved problem to show that the density of 1's is equal to 1/2.
%C The sequence is cube-free and all square subwords have lengths which are one of 2, 4, 6, 18 and 54.
%C This is a fractal sequence: replace each run by its length and recover the original sequence. - _Kerry Mitchell_, Dec 08 2005
%C 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. [_Jonathan Vos Post_, Sep 16 2008]
%C Conjecture: Taking the sequence in word lengths of 10, for example, batch 1-10, 11-20, etc... then there can only be 4, 5 or 6 1's in each batch. - _Jon Perry_, Sep 26 2012
%C Historical note: the sequence might be better called the Oldenburger-Kolakoski sequence, since it was discussed by Rufus Oldenburger in 1939; see references. - _Clark Kimberling_, Dec 06 2012
%D J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 337.
%D E. Angelini, "Jeux de suites", in Dossier Pour La Science, pp. 32-35, Volume 59 (Jeux math'), April/June 2008, Paris.
%D O. Bordelles and B. Cloitre, Bounds for the Kolakoski Sequence, J. Integer Sequences, 14 (2011), #11.2.1.
%D 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 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 J. Endrullis, D. Hendriks and J. W. Klop. Degrees of streams, http://www.cs.vu.nl/~diem/publication/pdf/degrees.pdf
%D J. M. Fedou and G. Fici, Some remarks on differentiable sequences and recursivity, Journal of Integer Sequences 13(3): Article 10.3.2 (2010). [From Jean-Marc Fedou and _Gabriele Fici_, Mar 18 2010]
%D 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 W. Kolakoski, Problem 5304, Amer. Math. Monthly, 72 (1965), 674; 73 (1966), 681-682.
%D 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 R. Oldenburger, Exponent trajectories in symbolic dynamics, Transactions of the Amer. Math. Soc., 46 (1939), 453-466.
%D G. Paun and A. Salomaa, Self-reading sequences, Amer. Math. Monthly 103 (1996), no. 2, 166-168.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D Bertran Steinsky, A Recursive Formula for the Kolakoski Sequence A000002, Journal of Integer Sequences, Vol. 9 (2006), Article 06.3.7.
%D I. Vardi, Computational Recreations in Mathematica. Addison-Wesley, Redwood City, CA, 1991, p. 233.
%H N. J. A. Sloane, <a href="/A000002/b000002.txt">Table of n, a(n) for n = 1..10502</a>
%H J.-P. Allouche, M. Baake, J. Cassaigns and D. Damanik, <a href="http://www.lri.fr/~allouche/">Palindrome complexity</a>
%H Michael Baake and Bernd Sing, <a href="http://arXiv.org/abs/math.MG/0206098">Kolakoski-(3,1) is a (deformed) model set</a>
%H J.M. Fedou and G. Fici, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL13/Fici/fici.html">Some remarks on differentiable sequences and recursivity</a>, Journal of Integer Sequences 13(3): Article 10.3.2 (2010). [From Jean-Marc Fedou and _Gabriele Fici_, Mar 18 2010]
%H C. Kimberling, Integer Sequences and Arrays, <a href="http://faculty.evansville.edu/ck6/integer/index.html">Illustration of the Kolakoski sequence</a>
%H 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.
%H Johan Nilsson, <a href="http://arxiv.org/abs/1110.4228">A Space Efficient Algorithm for the Calculation of the Digit Distribution in the Kolakoski Sequence</a>, Oct 19, 2011.
%H A. Scolnicov, PlanetMath.org, <a href="http://planetmath.org/encyclopedia/KolakoskiSequence.html">Kolakoski sequence</a>
%H 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/KolakoskiSequence.html">Kolakoski Sequence</a>
%H <a href="/index/Cor#core">Index entries for "core" sequences</a>
%F 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_, Oct 06 2003
%F 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, it is just a consequence of the definition). - _Benoit Cloitre_, Nov 17 2003
%F a(n+1) = 3-a(n)+(a(n)-a(n-1))*(a(b(n))-1), where b(n) is the sequence A156253. [Jean-Marc Fedou and _Gabriele Fici_, Mar 18 2010]
%e 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). (Labos, E., corrected by Graeme McRae)
%p 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 a[steps_] := Module[{a = {1, 2, 2}}, Do[a = Append[a, 1 + Mod[(n - 1), 2]], {n, 3, steps}, {i, a[[n]]}]; a]
%t a[ n_] := If[ n < 3, Max[ 0, n], Module[ {an = {1, 2, 2}, m = 3}, While[ Length[ an] < n, an = Join[ an, Table[ Mod[m, 2, 1], { an[[ m]]} ]]; m++]; an[[n]]] (* Michael Somos, Jul 11 2011 *)
%t n=8; Prepend[ Nest[ Flatten[ Partition[#, 2] /. {{2, 2} -> {2, 2, 1, 1}, {2, 1} -> {2, 2, 1}, {1, 2} -> {2, 1, 1}, {1, 1} -> {2, 1}}] &, {2, 2}, n], 1] (* Gyorgy Birkas, Jul 10 2012 *)
%o (PARI) a=[ 1,2,2 ]; for(n=3,80, for(i=1,a[ n ],a=concat(a,1+((n-1)%2)))); a
%o (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])}
%o (Haskell) a = 1:2: drop 2 (concat . zipWith replicate a . cycle $ [1,2]) -- John Tromp, Apr 09 2011
%Y Cf. A064353, A001462, A001083, A006928, A042942, A069864, A010060, A078880, A079729, A079730, A078929, A171899, A054353, A156077, A074286.
%Y Cf. A054353 (partial sums), A216345.
%K nonn,core,easy,nice
%O 1,2
%A _N. J. A. Sloane_.
|
