cp's OEIS Frontend

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.

Showing 1-5 of 5 results.

A000002 Kolakoski sequence: a(n) is length of n-th run; a(1) = 1; sequence consists just of 1's and 2's.

Original entry on oeis.org

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
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

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
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 1-10, 11-20, etc., then there can only be 4, 5 or 6 1's in each batch. - Jon Perry, Sep 26 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 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.
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)
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 2-block substitution beta
11 -> 12
12 -> 122
21 -> 112
22 -> 1122.
A 2-block substitution beta maps a word w(1)...w(2n) to the word
beta(w(1)w(2))...beta(w(2n-1)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 2-block substitution 11 -> 21, 12 -> 211, 21 -> 221, 22 -> 2211. (End)
Named after the American artist and recreational mathematician William George Kolakoski (1944-1997). - Amiram Eldar, Jun 17 2021

Examples

			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_

References

  • Jean-Paul Allouche and Jeffrey Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 337.
  • Éric 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.
  • 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.
  • 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.
  • 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).
  • Ilan Vardi, Computational Recreations in Mathematica. Addison-Wesley, Redwood City, CA, 1991, p. 233.

Links

Crossrefs

Cf. A001083, A006928, A042942, A069864, A010060, A078929, A171899, A054353 (partial sums), A074286, A216345, A294447.
Cf. A054354, bisections: A100428, A100429.
Cf. A013947, A156077, A234322 (positions, running total and percentage of 1's).
Cf. A118270.
Cf. A049705, A088569 (are either subsequences of A000002? - Jon Perry, Oct 30 2014)
Kolakoski-type 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 self-describing: A001462 (Golomb sequence, see also references therein), A005041, A100144.
Cf. A088568 (partial sums of [3 - 2 * a(n)]).

Programs

  • Haskell
    a = 1:2: drop 2 (concat . zipWith replicate a . cycle $ [1,2]) -- John Tromp, Apr 09 2011
  • 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 *)
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 *)
  • PARI
    my(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])};
  • 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([next(K) for  in range(100)]) # _David Eppstein, Oct 15 2016

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(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
Conjectures from Boštjan Gec, Oct 07 2024: (Start)
a(n)*(a(n-1) + a(n-2) - 3) + a(n-1)*a(n-2) + 7 = 3*a(n-1) + 3*a(n-2).
a(n)*(a(n-1) + a(n-2) - 3) = a(n-3)*(a(n-1) + a(n-2) - 3). (End)
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.

Extensions

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

A078649 Numbers n such that A000002(n)=A000002(n+1) where A000002 is the Kolakoski sequence.

Original entry on oeis.org

2, 4, 8, 11, 13, 16, 18, 22, 26, 28, 31, 35, 38, 40, 44, 48, 51, 53, 56, 58, 62, 65, 67, 70, 74, 78, 80, 83, 85, 89, 92, 94, 97, 99, 103, 107, 110, 112, 115, 119, 121, 124, 126, 130, 133, 135, 138, 140, 144, 148, 150, 153, 157, 160, 162, 165, 167, 171, 175, 178, 180
Offset: 1

Views

Author

Benoit Cloitre, Dec 14 2002

Keywords

Comments

Complement sequence of A054353. - Benoit Cloitre, Feb 07 2009
This sequence is the union of A074262 and A074263. - Nathaniel Johnston, May 02 2011
A054354(a(n)-1) = 0. - Reinhard Zumkeller, Aug 03 2013
This is a subsequence of A216345. In particular, this consists of A216345(i) such that A000002(i) = A216345(i+1)-A216345(i) = 2. A013948 is the sequence of all such i. - Danny Rorabaugh, Mar 13 2015

Links

Crossrefs

Cf. A054353, A074262, A074263, A013948, A216345.

Programs

  • Haskell
    a078649 n = a078649_list !! (n-1)
a078649_list = map (+ 1) $ filter ((== 0) . a054354) [1..]
-- Reinhard Zumkeller, Aug 03 2013
  • Maple
    isA078649 := proc(n)
    if A000002(n) = A000002(n+1) then
        true;
    else
        false;
    end if;
end proc:
A078649 := proc(n)
    option remember;
    if n = 1 then
        2;
    else
        for a from procname(n-1)+1 do
            if isA078649(a) then
                return a;
            end if;
        end do:
    end if;
end proc:
seq(A078649(n),n=1..50) ; # R. J. Mathar, Nov 15 2014
  • Mathematica
    a2 = {1, 2, 2}; Do[ a2 = Join[a2, {1+Mod[n-1, 2]}], {n, 3, 80}, {a2[[n]]}]; a3 = Accumulate[a2]; Complement[ Range[ Last[a3]], a3] (* Jean-François Alcover, Jun 18 2013 *)

Formula

a(n) is probably asymptotic to 3*n.
a(n) = A216345(A013948(n)). - Danny Rorabaugh, Mar 13 2015

A100428 Bisection of Kolakoski sequence A000002.

Original entry on oeis.org

1, 2, 1, 1, 2, 2, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 1, 2, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 1, 2, 2, 1, 1, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 1, 2, 1
Offset: 1

Views

Author

N. J. A. Sloane, Nov 20 2004

Keywords

Comments

Lengths of runs of ones in A000002. - Reinhard Zumkeller, Aug 03 2013
As in the Kolakoski sequence itself, the length of runs in this sequence is 1 or 2 : a run X,X,X is not possible, since it would imply X,Y,X,Y,X in the Kolakoski sequence, which in turn would imply 1, 1, 1 somewhere before (one Y, one X, one Y) which is not possible. - Jean-Christophe Hervé, Oct 04 2014

Links

Crossrefs

Cf. A100429, A216345.

Programs

  • Haskell
    a100428 n = a100428_list !! n
a100428_list = f a000002_list where f (u:_:us) = u : f us
-- Reinhard Zumkeller, Aug 03 2013

Extensions

More terms from Joshua Zucker, May 12 2006
Offset changed by Reinhard Zumkeller, Aug 03 2013

A100429 Bisection of Kolakoski sequence A000002.

Original entry on oeis.org

2, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 1, 2, 1, 2, 1, 1, 2, 2, 1, 2, 1, 2, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 2, 1, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 2
Offset: 1

Views

Author

N. J. A. Sloane, Nov 20 2004

Keywords

Comments

Lengths of runs of twos in A000002. - Reinhard Zumkeller, Aug 03 2013
As in the Kolakoski sequence itself, the length of runs in this sequence is 1 or 2 (see A100428). - Jean-Christophe Hervé, Oct 04 2014

Links

Crossrefs

Cf. A100428, A216345.

Programs

  • Haskell
    a100429 n = a100429_list !! n
a100429_list = g a000002_list where g (_:v:vs) = v : g vs
-- Reinhard Zumkeller, Aug 03 2013

Extensions

More terms from Joshua Zucker, May 12 2006
Offset changed by Reinhard Zumkeller, Aug 03 2013

A249942 Ranks of single 1's in the Kolakoski sequence A000002.

Original entry on oeis.org

7, 10, 20, 25, 34, 37, 43, 46, 55, 61, 64, 73, 76, 82, 88, 91, 101, 106, 109, 118, 128, 137, 143, 146, 152, 155, 164, 170, 173, 182, 187, 196, 199, 205, 211, 214, 223, 233, 236, 241, 251, 260, 263, 268, 277, 280, 286, 289, 298, 301, 307, 313, 316, 326, 331, 334
Offset: 1

Views

Author

Jean-Christophe Hervé, Nov 08 2014

Keywords

Comments

The single 1's whose ranks are given by this sequence are the 1's between two 2's in the OK sequence A000002. They are associated with iterated words of the OK sequence that develop themselves around each single 1 in two branches (for a description of the iterated words, see comments in A249507, which gives their lengths). The first term of A000002, which is indeed a single 1 but not between two 2's, is thus not considered here.
Each such single 1 is generated by a preceding 1 in the OK sequence that could be single or double, but each single 1 has a double 1 in its ancestors since the first 1 of the OK sequence has no descendants except itself. The length of the iterated word around a single 1 is linked to the number of generations between itself and its nearest double 1 ancestor (A249949 gives the number of generations of the n-th single 1).
A249948 gives the gaps between single 1's.

Links

Crossrefs

A000002, A054351, A054352, A249093, A249094, A249507, A249508, A249948, A249949.

Formula

a = {A054353(2k+1), k>1 and A000002(2k+1) = 1}.
Odd values of A216345: A216345(2k+1), k>0, such that A216345(2k+2) =
A216345(2k+1)+1.
Showing 1-5 of 5 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

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