This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A000002 M0190 N0070 #396 Aug 11 2025 09:47:51
%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,
%T A000002 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 A000002 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 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 Historical note: the sequence might be better called the Oldenburger-Kolakoski sequence, since it was discussed by Rufus Oldenburger in 1939; see links. - _Clark Kimberling_, Dec 06 2012. However, to avoid confusion, this sequence will be known in the OEIS as the Kolakoski sequence. It is undesirable to have some entries refer to the Oldenburger-Kolakoski sequence and others to the Kolakoski sequence. - _N. J. A. Sloane_, Nov 22 2017
%C A000002 It is an unsolved problem to show that the density of 1's is equal to 1/2.
%C A000002 A weaker problem is to construct a combinatorial bijection between the set of positions of 1's and the set of positions of 2's. - _Gus Wiseman_, Mar 01 2016
%C A000002 The sequence is cubefree and all square subwords have lengths which are one of 2, 4, 6, 18 and 54 (see A294447) [Carpi, 1994].
%C A000002 This is a fractal sequence: replace each run with its length and recover the original sequence. - _Kerry Mitchell_, 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 semirigorous bound |freq_1(K) - 1/2| <= 1/46. - _Jonathan Vos Post_, Sep 16 2008
%C A000002 freq_1(K) is conjectured to be 1/2 + O(log(K)) (see PlanetMath link). - _Jon Perry_, Oct 29 2014
%C A000002 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 A000002 From _Jean-Christophe Hervé_, Oct 04 2014: (Start)
%C A000002 The sequence does not contain words of the form ababa, because this would imply the impossible 111 (1 b, 1 a, 1 b) somewhere before. This demonstrates the conjecture made by _Jon Perry_: more than 6 1's or 6 2's in a word of 10 would necessitate something like aabaabaaba, which would imply the impossible 12121 before (word aabaababaa is also impossible because of ababa). The remark on the sextuplets below even shows that the number of 1's in any 9-tuplet is always 4 or 5.
%C A000002 There are only 6 triples that appear in the sequence (112, 121, 122, 211, 212 and 221); and by the preceding argument, only 18 sextuplets: the 6 double triples (112112, etc.); 112122, 112212, 121122, 121221, 211212, and 211221; and those obtained by reversing the order of the triples (122112, etc.). Regarding the density of 1's in the sequence, these 12 sextuplets all have a density 1/2 of 1's, and the 6 double triples all lead to a word with this exact density after transformation by the Kolakoski rules, for example: 112112 -> 12112122 (4 1's/8); this is because the second triple reverses the numbers of 1's and 2's generated by the first triple. Therefore, the sequence can be split into the double triples on one side, a part whose transformation (which is in the sequence) has a density of 1's of 1/2; and a part with the other sextuplets, which has directly the same density of 1's. (End)
%C A000002 If we map 1 to +1 and 2 to -1, then the mapped sequence would have a [conjectured] mean of 0, since the Kolakoski sequence is [conjectured] to have an equal density (1/2) of 1s and 2s. For the partial sums of this mapped sequence, see A088568. - _Daniel Forgues_, Jul 08 2015
%C A000002 Looking at the plot for A088568, it seems that although the asymptotic densities of 1s and 2s appear to be 1/2, there might be a bias in favor of the 2s. I.e., D(1) = 1/2 - O(log(n)/n), D(2) = 1/2 + O(log(n)/n). - _Daniel Forgues_, Jul 11 2015
%C A000002 From _Michel Dekking_, Jan 31 2018: (Start)
%C A000002 (a(n)) is the unique fixed point of the 2-block substitution beta
%C A000002 11 -> 12
%C A000002 12 -> 122
%C A000002 21 -> 112
%C A000002 22 -> 1122.
%C A000002 A 2-block substitution beta maps a word w(1)...w(2n) to the word
%C A000002 beta(w(1)w(2))...beta(w(2n-1)w(2n)).
%C A000002 If the word has odd length, then the last letter is ignored.
%C A000002 It was noted by me in 1979 in the Bordeaux seminar on number theory that (a(n+1)) is fixed point of the 2-block substitution 11 -> 21, 12 -> 211, 21 -> 221, 22 -> 2211. (End)
%C A000002 Named after the American artist and recreational mathematician William George Kolakoski (1944-1997). - _Amiram Eldar_, Jun 17 2021
%D A000002 Jean-Paul Allouche and Jeffrey Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 337.
%D A000002 Éric 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, 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 Michael 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 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 Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
%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 Ilan Vardi, Computational Recreations in Mathematica. Addison-Wesley, Redwood City, CA, 1991, p. 233.
%H A000002 N. J. A. Sloane, <a href="/A000002/b000002.txt">Table of n, a(n) for n = 1..10502</a>
%H A000002 Jean-Paul Allouche, Michael Baake, Julien Cassaigne and David Damanik, <a href="https://arxiv.org/abs/math/0106121">Palindrome complexity</a>, arXiv:math/0106121 [math.CO], 2001; <a href="https://doi.org/10.1016/S0304-3975(01)00212-2">Theoretical Computer Science</a>, Vol. 292 (2003), pp. 9-31.
%H A000002 Michael Baake and Bernd Sing, <a href="https://arxiv.org/abs/math/0206098">Kolakoski-(3,1) is a (deformed) model set</a>, arXiv:math/0206098 [math.MG], 2002-2003.
%H A000002 Alex Bellos and Brady Haran, <a href="https://www.youtube.com/watch?v=co5sOgZ3XcM">The Kolakoski Sequence</a>, Numberphile video (2017).
%H A000002 Olivier Bordellès and Benoit Cloitre, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Bordelles/bordelles7r.html">Bounds for the Kolakoski Sequence</a>, J. Integer Sequences, Vol. 14 (2011), Article 11.2.1.
%H A000002 Richard P. Brent, <a href="https://maths-people.anu.edu.au/~brent/pd/Kolakoski-UNSW.pdf">Fast algorithms for the Kolakoski sequence</a>, Slides from a talk, 2016.
%H A000002 Éric Brier, Rémi Géraud-Stewart, David Naccache, Alessandro Pacco, and Emanuele Troiani, <a href="https://arxiv.org/abs/2006.07246">The Look-and-Say The Biggest Sequence Eventually Cycles</a>, arXiv:2006.07246 [math.DS], 2020.
%H A000002 Arturo Carpi, <a href="https://doi.org/10.1016/0020-0190(94)00162-6">On repeated factors in C^infinity-words</a>, Information Processing Letters, Vol. 52 (1994), pp. 289-294.
%H A000002 Benoit Cloitre, <a href="/A000002/a000002.pdf">The Kolakoski transform of words</a>.
%H A000002 Benoit Cloitre, <a href="/A000002/a000002.png">Plot of walk on the first 60000 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))</a>.
%H A000002 F. M. Dekking, <a href="https://www.jstor.org/stable/44165352">Regularity and irregularity of sequences generated by automata</a>, Seminar on Number Theory, 1979-1980 (Talence, 1979-1980), Exp. No. 9, 10 pp., Univ. Bordeaux I, Talence, 1980.
%H A000002 F. M. Dekking, <a href="http://www.digizeitschriften.de/dms/resolveppn/?PPN=GDZPPN002544490">On the structure of self-generating sequences</a>, Seminar on Number Theory, 1980-1981 (Talence, 1980-1981), Exp. No. 31, 6 pp., Univ. Bordeaux I, Talence, 1981. Math. Rev. 83e:10075. <a href="https://www.jstor.org/stable/44166389">JSTOR</a>
%H A000002 F. M. Dekking, <a href="http://citeseerx.ist.psu.edu/pdf/7af40df61b38208d1eccca350f4869b6f1a6a18f">What Is the Long Range Order in the Kolakoski Sequence?</a>, Report 95-100, Technische Universiteit Delft, 1995.
%H A000002 F. M. Dekking, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Dekking/dek25.html">The Thue-Morse Sequence in Base 3/2</a>, J. Int. Seq., Vol. 26 (2023), Article 23.2.3.
%H A000002 Jörg Endrullis, Dimitri Hendriks and Jan Willem Klop, <a href="http://math.colgate.edu/~integers/a6num/a6num.pdf">Degrees of Streams</a>, Integers, Vol. 11B (2011), A6.
%H A000002 David Eppstein, <a href="https://11011110.github.io/blog/2016/10/13/kolakoski-tree.html">The Kolakoski tree</a> and <a href="https://11011110.github.io/blog/2016/10/14/kolakoski-sequence-via.html">The Kolakoski sequence via bit tricks instead of recursion</a>.
%H A000002 Jean-Marc Fédou and Gabriele Fici, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Fici/fici.html">Some remarks on differentiable sequences and recursivity</a>, Journal of Integer Sequences, Vol. 13 (2010), Article 10.3.2.
%H A000002 Abdallah Hammam, <a href="http://pubs.sciepub.com/tjant/4/3/1/">Some new Formulas for the Kolakoski Sequence A000002</a>, Turkish Journal of Analysis and Number Theory, Vol. 4, No. 3 (2016), pp. 54-59.
%H A000002 Mari Huova and Juhani Karhumäki, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Huova/huova2.html">On Unavoidability of k-abelian Squares in Pure Morphic Words</a>, Journal of Integer Sequences, Vol. 16 (2013), #13.2.9.
%H A000002 Clark Kimberling, Integer Sequences and Arrays, <a href="http://faculty.evansville.edu/ck6/integer/index.html">Illustration of the Kolakoski sequence</a>.
%H A000002 William Kolakoski, <a href="https://www.jstor.org/stable/2313883">Problem 5304</a>, Amer. Math. Monthly, Vol. 72, No. 8 (1965), p. 674; <a href="https://www.jstor.org/stable/2314839">Self Generating Runs</a>, Solution to Problem 5304 by Necdet Üçoluk, Vol. 73, No. 6 (1966), pp. 681-682.
%H A000002 Leonid V. Kovalev, <a href="https://web.archive.org/web/20130606153459 /http://calculus7.org/2012/04/14/kolakoski-sequence-ii/">Kolakoski sequence II</a>.
%H A000002 Elizabeth J. Kupin and Eric S. Rowland, <a href="https://arxiv.org/abs/0809.2776">Bounds on the frequency of 1 in the Kolakoski word</a>, arXiv:0809.2776 [math.CO], Sep 16, 2008.
%H A000002 Rabie A. Mahmoud, <a href="https://www.researchgate.net/publication/271910838">Hardware Implementation of Binary Kolakoski Sequence</a>, Research Gate, 2015.
%H A000002 Kerry Mitchell, <a href="http://kerrymitchellart.com/articles/Spirolateral-Type_Images_from_Integer_Sequences.pdf">Spirolateral-Type Images from Integer Sequences</a>, 2013.
%H A000002 Johan Nilsson, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Nilsson/nilsson5.html">A Space Efficient Algorithm for the Calculation of the Digit Distribution in the Kolakoski Sequence</a>, J. Int. Seq., Vol. 15 (2012), Article 12.6.7; <a href="https://arxiv.org/abs/1110.4228">arXiv preprint</a>, arXiv:1110.4228 [math.CO], Oct 19, 2011.
%H A000002 J. Nilsson, <a href="https://doi.org/10.12693/APhysPolA.126.549">Letter Frequencies in the Kolakoski Sequence</a>, Acta Physica Polonica A, Vol. 126 (2014), pp. 549-552.
%H A000002 Rufus Oldenburger, <a href="https://doi.org/10.1090/S0002-9947-1939-0000352-9">Exponent trajectories in symbolic dynamics</a>, Trans. Amer. Math. Soc., Vol. 46 (1939), pp. 453-466.
%H A000002 Matthew Parker, <a href="https://oeis.org/A000002/a000002_50K.7z">The first 50K terms (7-Zip compressed file)</a>.
%H A000002 Gheorghe Păun and Arto Salomaa, <a href="https://www.jstor.org/stable/2975113">Self-reading sequences</a>, Amer. Math. Monthly, Vol. 103, No. 2 (1996), pp. 166-168.
%H A000002 Michael Rao, <a href="https://www.arthy.org/kola/kola.php">Trucs et bidules sur la séquence de Kolakoski</a>, 2012, in French.
%H A000002 A. Scolnicov, <a href="http://planetmath.org/kolakoskisequence">Kolakoski sequence</a>, PlanetMath.org.
%H A000002 Bobby Shen, <a href="https://arxiv.org/abs/1703.00180">A uniformness conjecture of the Kolakoski sequence, graph connectivity, and correlations</a>, arXiv:1703.00180 [math.CO], 2017.
%H A000002 Bernd Sing, <a href="https://emis.de/journals/INTEGERS/papers/a14num/a14num.Abstract.html">More Kolakoski Sequences</a>, INTEGERS, Vol. 11B (2011), A14.
%H A000002 N. J. A. Sloane, <a href="/A001149/a001149.pdf">Handwritten notes on Self-Generating Sequences, 1970</a>. (note that A1148 has now become A005282)
%H A000002 N. J. A. Sloane, Coordination Sequences, Planing Numbers, and Other Recent Sequences (II), Experimental Mathematics Seminar, Rutgers University, Jan 31 2019, <a href="https://vimeo.com/314786942">Part I</a>, <a href="https://vimeo.com/314790822">Part 2</a>, <a href="https://oeis.org/A320487/a320487.pdf">Slides</a>. (Mentions this sequence)
%H A000002 Bertran Steinsky, <a href="https://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="https://mathworld.wolfram.com/KolakoskiSequence.html">Kolakoski Sequence</a>
%H A000002 Wikipedia, <a href="https://en.wikipedia.org/wiki/Kolakoski_sequence">Kolakoski sequence</a>.
%H A000002 Gus Wiseman, <a href="https://imgur.com/MqRlpnm">Kolakoski fractal animation for n=40000</a>.
%H A000002 Ed Wynn, <a href="/A000002/a000002.spl.txt">Program to generate A000002 in Shakespeare Programming Language</a>.
%H A000002 <a href="/index/Cor#core">Index entries for "core" sequences</a>
%F A000002 These two formulas 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 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, it is just a consequence of the definition). - _Benoit Cloitre_, Nov 17 2003
%F A000002 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
%F A000002 a(n) = (3 + (-1)^A156253(n))/2. - _Benoit Cloitre_, Sep 17 2013
%F A000002 Conjectures from _Boštjan Gec_, Oct 07 2024: (Start)
%F A000002 a(n)*(a(n-1) + a(n-2) - 3) + a(n-1)*a(n-2) + 7 = 3*a(n-1) + 3*a(n-2).
%F A000002 a(n)*(a(n-1) + a(n-2) - 3) = a(n-3)*(a(n-1) + a(n-2) - 3). (End)
%F A000002 Comment from _Kevin Ryde_, Oct 07 2024: The above formulas are true: The parts identify when terms are same or different and they hold for any sequence of 1's and 2's with run lengths 1 or 2.
%e A000002 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_
%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];
%p A000002 # alternative implementation based on the Cloitre formula:
%p A000002 A000002 := proc(n)
%p A000002 local ksu,k ;
%p A000002 option remember;
%p A000002 if n = 1 then
%p A000002 1;
%p A000002 elif n <=3 then
%p A000002 2;
%p A000002 else
%p A000002 for k from 1 do
%p A000002 ksu := add(procname(i),i=1..k) ;
%p A000002 if n = ksu then
%p A000002 return (3+(-1)^k)/2 ;
%p A000002 elif n = ksu+ 1 then
%p A000002 return (3-(-1)^k)/2 ;
%p A000002 end if;
%p A000002 end do:
%p A000002 end if;
%p A000002 end proc: # _R. J. Mathar_, Nov 15 2014
%t A000002 a[steps_] := Module[{a = {1, 2, 2}}, Do[a = Append[a, 1 + Mod[(n - 1), 2]], {n, 3, steps}, {i, a[[n]]}]; a]
%t A000002 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 A000002 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 *)
%t A000002 KolakoskiSeq[n_Integer] := Block[{a = {1, 2, 2}}, Fold[Join[#1, ConstantArray[Mod[#2, 2, 1], #1[[#2]]]] &, a, Range[3, n]]]; KolakoskiSeq[999] (* _Mikk Heidemaa_, Nov 01 2024 *) (* Corrected by _Giorgos Kalogeropoulos_, May 09 2025 *)
%o A000002 (PARI) my(a=[1,2,2]); for(n=3,80, for(i=1,a[n],a=concat(a,2-n%2))); a
%o A000002 (PARI) {a(n) = local(an=[1, 2, 2], m=3); if( n<1, 0, while( #an < n, an = concat( an, vector(an[m], i, 2-m%2)); m++); an[n])};
%o A000002 (Haskell) a = 1:2: drop 2 (concat . zipWith replicate a . cycle $ [1,2]) -- _John Tromp_, Apr 09 2011
%o A000002 (Python)
%o A000002 # For explanation see link.
%o A000002 def Kolakoski():
%o A000002 x = y = -1
%o A000002 while True:
%o A000002 yield [2,1][x&1]
%o A000002 f = y &~ (y+1)
%o A000002 x ^= f
%o A000002 y = (y+1) | (f & (x>>1))
%o A000002 K = Kolakoski()
%o A000002 print([next(K) for _ in range(100)]) # _David Eppstein_, Oct 15 2016
%Y A000002 Cf. A001083, A006928, A042942, A069864, A010060, A078929, A171899, A054353 (partial sums), A074286, A216345, A294447.
%Y A000002 Cf. A054354, bisections: A100428, A100429.
%Y A000002 Cf. A013947, A156077, A234322 (positions, running total and percentage of 1's).
%Y A000002 Cf. A118270.
%Y A000002 Cf. A049705, A088569 (are either subsequences of A000002? - _Jon Perry_, Oct 30 2014)
%Y A000002 Kolakoski-type sequences using other seeds than (1,2):
%Y A000002 A078880 (2,1), A064353 (1,3), A071820 (2,3), A074804 (3,2), A071907 (1,4), A071928 (2,4), A071942 (3,4), A074803 (4,2), A079729 (1,2,3), A079730 (1,2,3,4).
%Y A000002 Other self-describing: A001462 (Golomb sequence, see also references therein), A005041, A100144.
%Y A000002 Cf. A088568 (partial sums of [3 - 2 * a(n)]).
%K A000002 nonn,core,easy,nice
%O A000002 1,2
%A A000002 _N. J. A. Sloane_
%E A000002 Minor edits to example and PARI code made by _M. F. Hasler_, May 07 2014