

A000002


Kolakoski sequence: a(n) is length of nth run; a(1) = 1; sequence consists just of 1's and 2's.
(Formerly M0190 N0070)


152



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, 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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

It is an unsolved problem to show that the density of 1's is equal to 1/2.
The sequence is cubefree 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, 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 semirigorous bound freq_1(K)  1/2 <= 1/46.  Jonathan Vos Post, Sep 16 2008
Conjecture: Taking the sequence in word lengths of 10, for example, batch 110, 1120, etc... then there can only be 4, 5 or 6 1's in each batch.  Jon Perry, Sep 26 2012
Historical note: the sequence might be better called the OldenburgerKolakoski sequence, since it was discussed by Rufus Oldenburger in 1939; see references.  Clark Kimberling, Dec 06 2012


REFERENCES

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. 3235, Volume 59 (Jeux math'), April/June 2008, Paris.
O. Bordelles and B. Cloitre, Bounds for the Kolakoski Sequence, J. Integer Sequences, 14 (2011), #11.2.1.
F. M. Dekking, On the structure of selfgenerating sequences, Seminar on Number Theory, 19801981 (Talence, 19801981), 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 longrange aperiodic order (Waterloo, ON, 1995), 115125, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., 489, Kluwer Acad. Publ., Dordrecht, 1997. Math. Rev. 98g:11022.
J. Endrullis, D. Hendriks and J. W. Klop. Degrees of streams, http://www.cs.vu.nl/~diem/publication/pdf/degrees.pdf
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 JeanMarc Fedou and Gabriele Fici, Mar 18 2010]
Mari Huova and Juhani KarhumÃ¤ki, "On Unavoidability of kabelian Squares in Pure Morphic Words", Journal of Integer Sequences, Vol. 16 (2013), #13.2.9.
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), 681682.
J. C. Lagarias, Number Theory and Dynamical Systems, pp. 3572 of S. A. Burr, ed., The Unreasonable Effectiveness of Number Theory, Proc. Sympos. Appl. Math., 46 (1992). Amer. Math. Soc.
R. Oldenburger, Exponent trajectories in symbolic dynamics, Transactions of the Amer. Math. Soc., 46 (1939), 453466.
G. Paun and A. Salomaa, Selfreading sequences, Amer. Math. Monthly 103 (1996), no. 2, 166168.
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. AddisonWesley, Redwood City, CA, 1991, p. 233.


LINKS

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, Theoretical Computer Science, 292 (2003), 931, arXiv:math/0106121.
J.P. Allouche, M. Baake, J. Cassaigns and D. Damanik, Palindrome complexity, Theoretical Computer Science, 292 (2003), 931.
Michael Baake and Bernd Sing, Kolakoski(3,1) is a (deformed) model set
Benoit Cloitre, The Kolakoski transform
Benoit Cloitre, Walk on the 60000 first terms (step of unit length moving right with angle Pi/2 if 2 and left with angle Pi/2 if 1 starting at (0,0))
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 JeanMarc Fedou and Gabriele Fici, Mar 18 2010]
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.
Kerry Mitchell, SpirolateralType Images from Integer Sequences, 2013
Johan Nilsson, A Space Efficient Algorithm for the Calculation of the Digit Distribution in the Kolakoski Sequence, Oct 19, 2011.
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, Kolakoski Sequence
Index entries for "core" sequences


FORMULA

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
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
a(n+1) = 3a(n)+(a(n)a(n1))*(a(b(n))1), where b(n) is the sequence A156253.  JeanMarc Fedou and Gabriele Fici, Mar 18 2010
a(n) = (3 + (1)^A156253(n))/2.  Benoit Cloitre, Sep 17 2013


EXAMPLE

Start with a(1) = 1. By definition of the sequence, this says that the first run has length 1, so it must be a single 1, and a(2) = 2. Thus, the second run (which starts with this 2) must have length 2, so the third term must be also be a(3) = 2, and the fourth term can't be a 2, so must be a(4) = 1. Since a(3) = 2, the third run must have 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 Elemer, corrected by Graeme McRae


MAPLE

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+((n1)mod 2) ]; od: od: s; A000002 := n>s[n];


MATHEMATICA

a[steps_] := Module[{a = {1, 2, 2}}, Do[a = Append[a, 1 + Mod[(n  1), 2]], {n, 3, steps}, {i, a[[n]]}]; a]
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 *)
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] (* Birkas Gyorgy, Jul 10 2012 *)


PROG

(PARI) a=[1, 2, 2]; for(n=3, 80, for(i=1, a[n], a=concat(a, 2n%2))); a
(PARI) {a(n) = local(an=[1, 2, 2], m=3); if( n<1, 0, while( #an < n, an = concat( an, vector(an[m], i, 2m%2)); m++); an[n])};
(Haskell) a = 1:2: drop 2 (concat . zipWith replicate a . cycle $ [1, 2])  John Tromp, Apr 09 2011


CROSSREFS

Cf. A064353, A001462, A001083, A006928, A042942, A069864, A010060, A078880, A079729, A079730, A078929, A171899, A054353, A156077, A074286.
Cf. A054353 (partial sums), A216345.
Cf. A054354, bisections: A100428, A100429.
Cf. A156077, A234322 (number and percent of 1's).
Similarly selfdescribing: A005041, A100144.
Sequence in context: A074293 A013949 A078880 * A074295 A236479 A116514
Adjacent sequences: A000001 * A000003 A000004 A000005 A000006


KEYWORD

nonn,core,easy,nice,changed


AUTHOR

N. J. A. Sloane


EXTENSIONS

Minor edits in example and PARI code by M. F. Hasler, May 07 2014


STATUS

approved



