

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)


206



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

Historical note: the sequence might be better called the OldenburgerKolakoski 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 OldenburgerKolakoski sequence and others to the Kolakoski sequence.  N. J. A. Sloane, Nov 22 2017
It is an unsolved problem to show that the density of 1's is equal to 1/2.
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
The sequence is cubefree and all square subwords have lengths which are one of 2, 4, 6, 18 and 54 (see A294447) [Carpi, 1994].
This is a fractal sequence: replace each run with 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
freq_1(K) is conjectured to be 1/2 + O(log(K)) (see PlanetMath link).  Jon Perry, Oct 29 2014
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
From JeanChristophe Hervé, Oct 04 2014: (Start)
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 9tuplet is always 4 or 5.
There are only 6 triplets that appear in the sequence (112, 121, 122, 211, 212 and 221); and by the preceding argument, only 18 sextuplets: the 6 double triplets (112112, etc.); 112122, 112212, 121122, 121221, 211212, and 211221; and those obtained by reversing the order of the triplets (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 triplets 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 triplet reverses the numbers of 1's and 2's generated by the first triplet. Therefore, the sequence can be split into the double triplets 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)
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
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
From Michel Dekking, Jan 31 2018: (Start)
(a(n)) is the unique fixed point of the 2block substitution beta
11 > 12
12 > 122
21 > 112
22 > 1122.
A 2block substitution beta maps a word w(1)...w(2n) to the word
beta(w(1)w(2))...beta(w(2n1)w(2n)).
If the word has odd length, then the last letter is ignored.
It was noted by me in 1979 in the Bordeaux seminar on number theory that (a(n+1)) is fixed point of the 2block substitution 11 > 21, 12 > 211, 21 > 221, 22 > 2211. (End)


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.
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.
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.
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.
Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence  see "List of Sequences" in Vol. 2.
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).
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, arXiv:math/0106121 [math.CO], 2001; Theoretical Computer Science, 292 (2003), 931.
Michael Baake and Bernd Sing, Kolakoski(3,1) is a (deformed) model set, arXiv:math/0206098 [math.MG], 20022003.
Alex Bellos and Brady Haran, The Kolakoski Sequence , Numberphile video (2017)
O. Bordelles and B. Cloitre, Bounds for the Kolakoski Sequence, J. Integer Sequences, 14 (2011), #11.2.1.
Richard P. Brent, Fast algorithms for the Kolakoski sequence, Slides from a talk, 2016.
Calculus VII, Kolakoski sequence II
A. Carpi, On repeated factors in C^infinitywords, Information Processing Letters 52 (1994), 289294.
Benoit Cloitre, The Kolakoski transform of words
Benoit Cloitre, Plot of 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))
F. M. Dekking, Regularity and irregularity of sequences generated by automata, Seminar on Number Theory, 19791980 (Talence, 19791980), Exp. No. 9, 10 pp., Univ. Bordeaux I, Talence, 1980.
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?, Report 95100, Technische Universiteit Delft, 1995.
J. Endrullis, D. Hendriks and J. W. Klop, Degrees of streams.
David Eppstein, The Kolakoski tree and The Kolakoski sequence via bit tricks instead of recursion.
J. M. Fedou and G. Fici, Some remarks on differentiable sequences and recursivity, Journal of Integer Sequences 13(3): Article 10.3.2 (2010).
Abdallah Hammam, Some new Formulas for the Kolakoski Sequence A000002, Turkish Journal of Analysis and Number Theory, 2016, Vol. 4, No. 3, 5459.
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
C. Kimberling, Integer Sequences and Arrays, Illustration of the Kolakoski sequence
W. Kolakoski and N. Ucoluk, Problem 5304: Self Generating Runs, Amer. Math. Monthly, 72 (1965), 674; 73 (1966), 681682.
Elizabeth J. Kupin and Eric S. Rowland, Bounds on the frequency of 1 in the Kolakoski word, arXiv:0809.2776 [math.CO], Sep 16, 2008.
Rabie A. Mahmoud, Hardware Implementation of Binary Kolakoski Sequence, Research Gate, 2015.
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, arXiv:1110.4228 [math.CO], Oct 19, 2011; J. Int. Seq. 15 (2012) #12.6.7
J. Nilsson, Letter Frequencies in the Kolakoski Sequence, Acta Physica Polonica A, 126 (2014), 549552.
R. Oldenburger, Exponent trajectories in symbolic dynamics, Trans. Amer. Math. Soc., 46 (1939), 453466.
Matthew Parker, The first 50K terms (7Zip compressed file)
G. Paun and A. Salomaa, Selfreading sequences, Amer. Math. Monthly 103 (1996), no. 2, 166168.
Michael Rao, Trucs et bidules sur la séquence de Kolakoski, 2012, in French.
A. Scolnicov, PlanetMath.org, Kolakoski sequence
Bobby Shen, A uniformness conjecture of the Kolakoski sequence, graph connectivity, and correlations, arXiv:1703.00180 [math.CO], 2017.
Bernard Sing, More Kolakoski Sequences, INTEGERS, Volume 11B (2011), A14.
N. J. A. Sloane, Handwritten notes on SelfGenerating Sequences, 1970 (note that A1148 has now become A005282)
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
Wikipedia, Kolakoski sequence
Gus Wiseman, Kolakoski fractal animation for n=40000
Index entries for "core" sequences
Ed Wynn, Program to generate A000002 in Shakespeare Programming Language


FORMULA

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
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) = 3  a(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];
# alternative implementation based on the Cloitre formula:
A000002 := proc(n)
local ksu, k ;
option remember;
if n = 1 then
1;
elif n <=3 then
2;
else
for k from 1 do
ksu := add(procname(i), i=1..k) ;
if n = ksu then
return (3+(1)^k)/2 ;
elif n = ksu+ 1 then
return (3(1)^k)/2 ;
end if;
end do:
end if;
end proc: # R. J. Mathar, Nov 15 2014


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
(Python)
# For explanation see link.
def Kolakoski():
x = y = 1
while True:
yield [2, 1][x&1]
f = y &~ (y+1)
x ^= f
y = (y+1)  (f & (x>>1))
K = Kolakoski()
print [K.next() for _ in range(100)] # David Eppstein, Oct 15 2016


CROSSREFS

Cf. A001083, A006928, A042942, A069864, A010060, A078929, A171899, A054353 (partial sums), A156077, A074286, A216345, A294447.
Cf. A054354, bisections: A100428, A100429.
Cf. A156077, A234322 (number and percent of 1's).
Cf. A118270.
Cf. A049705, A088569 (are either subsequences of A000002?  Jon Perry, Oct 30 2014)
Kolakoskitype sequences using other seeds than (1,2):
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).
Other selfdescribing: A001462 (Golomb sequence, see also references therein), A005041, A100144.
Cf. A088568 Partial sums of [3  2 * A000002(n)].
Sequence in context: A074293 A013949 A078880 * A074295 A236479 A116514
Adjacent sequences: A000001 * A000003 A000004 A000005 A000006


KEYWORD

nonn,core,easy,nice


AUTHOR

N. J. A. Sloane


EXTENSIONS

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


STATUS

approved



