login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000002 Kolakoski sequence: a(n) is length of n-th run; a(1) = 1; sequence consists just of 1's and 2's.
(Formerly M0190 N0070)
155
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

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 1-10, 11-20, 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 Oldenburger-Kolakoski sequence, since it was discussed by Rufus Oldenburger in 1939; see links. - Clark Kimberling, Dec 06 2012

From Jean-Christophe 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 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.

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)

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. 32-35, 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 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.

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. 35-72 of S. A. Burr, ed., The Unreasonable Effectiveness of Number Theory, Proc. Sympos. Appl. Math., 46 (1992). Amer. Math. Soc.

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. Addison-Wesley, 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), 9-31, arXiv:math/0106121.

J.-P. Allouche, M. Baake, J. Cassaigns and D. Damanik, Palindrome complexity, Theoretical Computer Science, 292 (2003), 9-31.

Michael Baake and Bernd Sing, Kolakoski-(3,1) is a (deformed) model set

O. Bordelles and B. Cloitre, Bounds for the Kolakoski Sequence, J. Integer Sequences, 14 (2011), #11.2.1.

Calculus VII, Kolakoski sequence II

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))

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.

J. Endrullis, D. Hendriks and J. W. Klop, Degrees of streams.

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]

Mari Huova and Juhani Karhumäki, On Unavoidability of k-abelian 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), 681-682.

Elizabeth J. Kupin and Eric S. Rowland, Bounds on the frequency of 1 in the Kolakoski word, Sep 16, 2008.

Kerry Mitchell, Spirolateral-Type 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.

R. Oldenburger, Exponent trajectories in symbolic dynamics, Trans. Amer. Math. Soc., 46 (1939), 453-466.

G. Paun and A. Salomaa, Self-reading sequences, Amer. Math. Monthly 103 (1996), no. 2, 166-168.

A. Scolnicov, PlanetMath.org, Kolakoski sequence

Bernard Sing, More Kolakoski Sequences

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) = 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

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+((n-1)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, 2-n%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, 2-m%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 (partial sums), A156077, A074286, A216345.

Cf. A054354, bisections: A100428, A100429.

Cf. A156077, A234322 (number and percent of 1's).

Similarly self-describing: A005041, A100144.

Cf. A118270.

Cf. A049705, A088569 (are either subsequences of A000002? - Jon Perry, Oct 30 2014)

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified November 20 21:20 EST 2014. Contains 249754 sequences.