A000002 -id:A000002 - cp's OEIS frontend

A054351 Successive generations of the Kolakoski sequence A000002.

1, 12, 1221, 1221121, 12211212212, 122112122122112112, 1221121221221121122121121221, 1221121221221121122121121221121121221221121, 12211212212211211221211212211211212212211212212112112212211212212

Offset: 0

N. J. A. Sloane, May 07 2000

Cf. A054348, A054349, A054350, A054352, A042942, A000002.

Word lengths give A054352.

from itertools import accumulate, groupby, repeat
def K(n, _):
  c, s = "12", ""
  for i, k in enumerate(str(n)): s += c[i%2]*int(k)
  return int(s + c[(i+1)%2])
def aupton(nn): return list(accumulate(repeat(1, nn+1), K))
print(aupton(8)) # Michael S. Branicky, Jan 12 2021

More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Apr 05 2003

A054352 Lengths of successive generations of the Kolakoski sequence A000002.

Original entry on oeis.org

1, 2, 4, 7, 11, 18, 28, 43, 65, 99, 150, 226, 340, 511, 768, 1153, 1728, 2590, 3885, 5826, 8742, 13116, 19674, 29514, 44280, 66431, 99667, 149531, 224306, 336450, 504648, 756961, 1135450, 1703197, 2554846, 3832292, 5748474, 8622646, 12933971, 19400955, 29101203

Offset: 0

N. J. A. Sloane, May 07 2000

Starting with a(0) = 1, the first term of A000002, the n-th generation is the run of figures directly generated from the preceding generation completed with a single last figure which begins the next run. Thus a(0) = 1 -> 1-2 -> 1-22-1 -> 1-2211-2-1 etc. - Jean-Christophe Hervé, Oct 26 2014

It seems that the limit (c =) lim_{n -> oo} a(n)/(3/2)^n exists, with c = 2.63176..., so a(n) ~ (3/2)*a(n-1) ~ c * (3/2)^n, for large n. - A.H.M. Smeets, Apr 12 2024

Michael S. Branicky, Table of n, a(n) for n = 0..61

Cf. A054348, A054349, A054350, A054351, A054353, A042942, A000002.

Partial sums of A329758.

A2 = {1, 2, 2}; Do[If[Mod[n, 10^5] == 0, Print["n = ", n]]; m = 1 + Mod[n - 1, 2]; an = A2[[n]]; A2 = Join[A2, Table[m, {an}]], {n, 3, 10^6}]; A054353 = Accumulate[A2]; Clear[a]; a[0] = 1; a[n_] := a[n] = A054353[[a[n - 1]]] + 1; Table[a[n], {n, 0, 33}] (* Jean-François Alcover, Oct 30 2014, after Jean-Christophe Hervé *)

def aupton(nn):
  alst, A054353, idx = [1], 0, 1
  K = Kolakoski()  # using Kolakoski() in A000002
  for n in range(2, nn+1):
    target = alst[-1]
    while idx <= target:
      A054353 += next(K)
      idx += 1
    alst.append(A054353 + 1)  # a(n) = A054353(a(n-1))+1
  return alst
print(aupton(36))  # Michael S. Branicky, Jan 12 2021

a(0) = 1, and for n > 0, a(n) = A054353(a(n-1))+1. - Jean-Christophe Hervé, Oct 26 2014

a(7)-a(32) from John W. Layman, Aug 20 2002
a(33) from Jean-François Alcover, Oct 30 2014
a(34) and beyond from Michael S. Branicky, Jan 12 2021

A329317 Length of the Lyndon factorization of the reversed first n terms of A000002.

Original entry on oeis.org

1, 2, 3, 2, 2, 3, 3, 4, 5, 4, 5, 6, 5, 3, 4, 4, 2, 3, 4, 3, 4, 3, 3, 4, 4, 5, 6, 5, 4, 5, 5, 2, 3, 3, 4, 5, 4, 5, 6, 5, 3, 4, 4, 5, 6, 5, 6, 5, 3, 4, 4, 2, 3, 4, 3, 4, 5, 4, 3, 4, 4, 5, 6, 5, 6, 7, 6, 4, 5, 5, 3, 4, 4, 5, 6, 5, 6, 5, 4, 5, 6, 5, 6, 7, 6, 5, 6

Offset: 1

Gus Wiseman, Nov 11 2019

nonn

We define the Lyndon product of two or more finite sequences to be the lexicographically maximal sequence obtainable by shuffling the sequences together. For example, the Lyndon product of (231) with (213) is (232131), the product of (221) with (213) is (222131), and the product of (122) with (2121) is (2122121). A Lyndon word is a finite sequence that is prime with respect to the Lyndon product. Equivalently, a Lyndon word is a finite sequence that is lexicographically strictly less than all of its cyclic rotations. Every finite sequence has a unique (orderless) factorization into Lyndon words, and if these factors are arranged in lexicographically decreasing order, their concatenation is equal to their Lyndon product. For example, (1001) has sorted Lyndon factorization (001)(1).

			The sequence of Lyndon factorizations of the reversed initial terms of A000002 begins:
   1: (1)
   2: (2)(1)
   3: (2)(2)(1)
   4: (122)(1)
   5: (1122)(1)
   6: (2)(1122)(1)
   7: (12)(1122)(1)
   8: (2)(12)(1122)(1)
   9: (2)(2)(12)(1122)(1)
  10: (122)(12)(1122)(1)
  11: (2)(122)(12)(1122)(1)
  12: (2)(2)(122)(12)(1122)(1)
  13: (122)(122)(12)(1122)(1)
  14: (112212212)(1122)(1)
  15: (2)(112212212)(1122)(1)
  16: (12)(112212212)(1122)(1)
  17: (1121122122121122)(1)
  18: (2)(1121122122121122)(1)
  19: (2)(2)(1121122122121122)(1)
  20: (122)(1121122122121122)(1)
For example, the reversed first 13 terms of A000002 are (1221221211221), with Lyndon factorization (122)(122)(12)(1122)(1), so a(13) = 5.

Row-lengths of A329316.
The non-reversed version is A329315.
Cf. A000002, A000031, A001037, A027375, A059966, A060223, A088568, A102659, A211100, A288605, A296372, A296658, A329314, A329325.

lynQ[q_]:=Array[Union[{q,RotateRight[q,#]}]=={q,RotateRight[q,#]}&,Length[q]-1,1,And];
lynfac[q_]:=If[Length[q]==0,{},Function[i,Prepend[lynfac[Drop[q,i]],Take[q,i]]][Last[Select[Range[Length[q]],lynQ[Take[q,#]]&]]]];
kolagrow[q_]:=If[Length[q]<2,Take[{1,2},Length[q]+1],Append[q,Switch[{q[[Length[Split[q]]]],q[[-2]],Last[q]},{1,1,1},0,{1,1,2},1,{1,2,1},2,{1,2,2},0,{2,1,1},2,{2,1,2},2,{2,2,1},1,{2,2,2},1]]]
kol[n_Integer]:=Nest[kolagrow,{1},n-1];
Table[Length[lynfac[Reverse[kol[n]]]],{n,100}]

A013947 Positions of 1's in Kolakoski sequence (A000002).

Original entry on oeis.org

1, 4, 5, 7, 10, 13, 14, 16, 17, 20, 22, 23, 25, 28, 29, 31, 32, 34, 37, 40, 41, 43, 46, 48, 49, 51, 52, 55, 58, 59, 61, 64, 67, 68, 70, 71, 73, 76, 78, 79, 82, 85, 86, 88, 91, 94, 95, 97, 98, 101, 103, 104, 106, 109, 112, 113, 115, 116, 118, 121, 122, 124, 125, 128, 130, 131, 133

Offset: 1

Clark Kimberling

Complement: A013948.

Cf. A000002, A022297, A156077.

For n > 1, a(n) = A022297(n)+1.

A074286 Partial sum of the Kolakoski sequence (A000002) minus n.

Original entry on oeis.org

0, 1, 2, 2, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8, 8, 9, 10, 10, 11, 11, 11, 12, 12, 13, 14, 14, 14, 15, 15, 15, 16, 16, 17, 18, 18, 19, 20, 20, 20, 21, 21, 22, 23, 23, 24, 24, 24, 25, 25, 25, 26, 27, 27, 28, 29, 29, 29, 30, 30, 31, 32, 32, 33, 34, 34, 34, 35, 35

Offset: 1

Jon Perry, Sep 21 2002

a(n) is the number of 2's in the Kolakoski word of length n (see first formula below). - Jean-Christophe Hervé, Oct 05 2014

			The Kolakoski sequence is 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, ...; the partial sums are 1, 3, 5, 6, 7, 9, ..., so the sequence is 1-1=0, 3-2=1, 5-3=2, 6-4=2, 7-5=2, 9-6=3, ... .

Nathaniel Johnston, Table of n, a(n) for n = 1..10000
O. Bordelles and B. Cloitre, Bounds for the Kolakoski Sequence, J. Integer Sequences, 14 (2011), #11.2.1.
Bertran Steinsky, A Recursive Formula for the Kolakoski Sequence A000002, J. Integer Sequences, Vol. 9 (2006), Article 06.3.7.

Cf. A000002 (Kolakoski sequence), A054353 (partial sums of K. sequence), A156077 (number of 1's in K. sequence).

Essentially partial sums of A157686.

a2 = {1, 2, 2}; Do[ a2 = Join[a2, {1 + Mod[n - 1, 2]}], {n, 3, 50}, {a2[[n]]}]; a3 = Accumulate[a2]; a3 - Range[Length[a3]] (* Jean-François Alcover, Jun 18 2013 *)

a(n)=#{1<=k<=n : A000002(k)=2}. - Benoit Cloitre, Feb 03 2009
a(n) = A054353(n) - n. - Nathaniel Johnston, May 02 2011
a(n) = n - A156077(n). - Jean-Christophe Hervé, Oct 05 2014

Corrected offset from Nathaniel Johnston, May 02 2011

A119493 Determinant of n X n matrix of first n^2 terms of Kolakoski sequence (A000002).

Original entry on oeis.org

0, 1, -3, 0, -2, -3, 0, 0, 0, 0, 0, 0, 0, 17, 0, 0, 140, 0, 0, 0, 0, 0, -205, 0, -44, 0, 0, 0, 0, 0, 0, 91050, 0, -1350, 8570, 65392, 0, 187556, 61650, 0, -226, 0, 1402800, -4810213, 0, 0, 0, 46764576, 122333784, 0, 0, -82777822, -11359122, 0, 54911379, 0, 0

Offset: 0

Jonathan Vos Post, May 25 2006

When is next nonzero value, for n>11?

			a(3) = 0 because for instance, first row = 3rd row = (1,2,2).
a(6) = 0 because for instance, 3rd column = 6th column = (2,2,2,2,2,2).
a(7) = 0 because for instance, first column = 4th column.
a(9) = 0 because for instance, 9th column = 2 * 4th column.

Cf. A000002.

From R. J. Mathar, Oct 15 2010: (Start)
read("transforms3") ; L := BFILETOLIST("b000002.txt") ;
for s from 1 to floor(sqrt(nops(L))) do m := Matrix(1..s,1..s) ; for r from 0 to s-1 do for c from 0 to s-1 do m[r+1,c+1] := op(1+c+r*s,L) ; end do: end do: printf("%a,\n", LinearAlgebra[Determinant](m) ) ; end do: (End)

nmax = 56; a2 = {1, 2, 2}; Do[ a2 = Join[a2, {1 + Mod[n-1, 2]}], {n, 3, nmax^2}, {a2[[n]]}]; a[0] = 0; a[n_] := Det[ Partition[ Take[a2, n^2], n]]; Table[a[n], {n, 0, nmax}] (* Jean-François Alcover, Jun 18 2013 *)

More terms from R. J. Mathar, Oct 15 2010

A329316 Irregular triangle read by rows where row n gives the sequence of lengths of components of the Lyndon factorization of the reversed first n terms of A000002.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 3, 1, 4, 1, 1, 4, 1, 2, 4, 1, 1, 2, 4, 1, 1, 1, 2, 4, 1, 3, 2, 4, 1, 1, 3, 2, 4, 1, 1, 1, 3, 2, 4, 1, 3, 3, 2, 4, 1, 9, 4, 1, 1, 9, 4, 1, 2, 9, 4, 1, 16, 1, 1, 16, 1, 1, 1, 16, 1, 3, 16, 1, 1, 3, 16, 1, 5, 16, 1, 6, 16, 1, 1, 6, 16, 1, 2, 6

Offset: 0

Gus Wiseman, Nov 11 2019

There are no repeated rows, as row n has sum n.
We define the Lyndon product of two or more finite sequences to be the lexicographically maximal sequence obtainable by shuffling the sequences together. For example, the Lyndon product of (231) with (213) is (232131), the product of (221) with (213) is (222131), and the product of (122) with (2121) is (2122121). A Lyndon word is a finite sequence that is prime with respect to the Lyndon product. Equivalently, a Lyndon word is a finite sequence that is lexicographically strictly less than all of its cyclic rotations. Every finite sequence has a unique (orderless) factorization into Lyndon words, and if these factors are arranged in lexicographically decreasing order, their concatenation is equal to their Lyndon product. For example, (1001) has sorted Lyndon factorization (001)(1).
It appears that some numbers (such as 10) never appear in the sequence.

			Triangle begins:
   1: (1)
   2: (1,1)
   3: (1,1,1)
   4: (3,1)
   5: (4,1)
   6: (1,4,1)
   7: (2,4,1)
   8: (1,2,4,1)
   9: (1,1,2,4,1)
  10: (3,2,4,1)
  11: (1,3,2,4,1)
  12: (1,1,3,2,4,1)
  13: (3,3,2,4,1)
  14: (9,4,1)
  15: (1,9,4,1)
  16: (2,9,4,1)
  17: (16,1)
  18: (1,16,1)
  19: (1,1,16,1)
  20: (3,16,1)
For example, the reversed first 13 terms of A000002 are (1221221211221), with Lyndon factorization (122)(122)(12)(1122)(1), so row 13 is (3,3,2,4,1).

Row lengths are A329317.
The non-reversed version is A329315.
Cf. A000002, A000031, A001037, A027375, A059966, A060223, A088568, A102659, A211100, A288605, A296372, A296658, A329314, A329325.

lynQ[q_]:=Array[Union[{q,RotateRight[q,#]}]=={q,RotateRight[q,#]}&,Length[q]-1,1,And];
lynfac[q_]:=If[Length[q]==0,{},Function[i,Prepend[lynfac[Drop[q,i]],Take[q,i]]][Last[Select[Range[Length[q]],lynQ[Take[q,#]]&]]]];
kolagrow[q_]:=If[Length[q]<2,Take[{1,2},Length[q]+1],Append[q,Switch[{q[[Length[Split[q]]]],q[[-2]],Last[q]},{1,1,1},0,{1,1,2},1,{1,2,1},2,{1,2,2},0,{2,1,1},2,{2,1,2},2,{2,2,1},1,{2,2,2},1]]]
kol[n_Integer]:=Nest[kolagrow,{1},n-1];
Table[Length/@lynfac[Reverse[kol[n]]],{n,100}]

A022292 Exactly half of first a(n) terms of Kolakoski sequence A000002 are 1's (not known to be infinite).

Original entry on oeis.org

0, 2, 4, 6, 8, 10, 14, 16, 18, 20, 22, 24, 26, 28, 30, 36, 38, 40, 42, 44, 46, 48, 50, 54, 56, 58, 60, 62, 64, 68, 70, 72, 74, 76, 78, 80, 82, 86, 88, 98, 104, 106, 116, 118, 122, 124, 126, 128, 130, 132, 136, 138, 140, 142, 144, 146, 148, 150, 152, 158

Offset: 0

Clark Kimberling

nonn

The sequences A022292, A074261, and A342799 partition the nonnegative integers. - Clark Kimberling, May 10 2021

Joerg Arndt, Table of n, a(n) for n = 0..8739

Cf. A000002, A074261, A022293, A342799.

a=new Array();
a[1]=1; a[2]=2; a[3]=2; cd=1; ap=3;
for (i=4; i<1000; i++)
{
    if (a[ap]==1) a[i]=cd;
    else {a[i]=cd; a[i+1]=cd; i++}
    ap++;
    cd=3-cd;
}
oc=0; tc=0;
for (i=1; i<1000; i++)
{
    if (oc==tc) document.write(i-1+", ");
    if (a[i]==1) oc++;
    else tc++;
}
// Jon Perry, Sep 11 2012

k = 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}, 14], 1]; (* A000002 *)
Select[Range[400], Count[Take[k, #], 1] < #/2 &]   (* A074261 *)
Select[Range[400], Count[Take[k, #], 1] == #/2 &]  (* A022292 *)
Select[Range[400], Count[Take[k, #], 1] > #/2 &]   (* A342799 *)
(* Clark Kimberling, May 10 2021 *)

Conjecture: a(n) is asymptotic to c*n*log(n) for some constant c <= 1. - Benoit Cloitre, Nov 17 2003

0 prepended by Jon Perry, Sep 11 2012

A329362 Length of the co-Lyndon factorization of the first n terms of A000002.

Original entry on oeis.org

0, 1, 2, 3, 2, 2, 3, 2, 3, 4, 3, 4, 5, 4, 3, 4, 3, 3, 4, 5, 4, 5, 3, 3, 4, 3, 4, 5, 4, 3, 4, 3, 3, 4, 3, 4, 5, 4, 5, 6, 5, 4, 5, 4, 5, 6, 5, 6, 4, 4, 5, 4, 4, 5, 6, 5, 6, 7, 6, 5, 6, 5, 6, 7, 6, 7, 8, 7, 6, 7, 6, 5, 6, 5, 6, 7, 6, 7, 5, 5, 6, 7, 6, 7, 8, 7, 6, 7

Offset: 0

Gus Wiseman, Nov 12 2019

nonn

The co-Lyndon product of two or more finite sequences is defined to be the lexicographically minimal sequence obtainable by shuffling the sequences together. For example, the co-Lyndon product of (231) and (213) is (212313), the product of (221) and (213) is (212213), and the product of (122) and (2121) is (1212122). A co-Lyndon word is a finite sequence that is prime with respect to the co-Lyndon product. Equivalently, a co-Lyndon word is a finite sequence that is lexicographically strictly greater than all of its cyclic rotations. Every finite sequence has a unique (orderless) factorization into co-Lyndon words, and if these factors are arranged in a certain order, their concatenation is equal to their co-Lyndon product. For example, (1001) has sorted co-Lyndon factorization (1)(100).

			The co-Lyndon factorizations of the initial terms of A000002:
                      () = 0
                     (1) = (1)
                    (12) = (1)(2)
                   (122) = (1)(2)(2)
                  (1221) = (1)(221)
                 (12211) = (1)(2211)
                (122112) = (1)(2211)(2)
               (1221121) = (1)(221121)
              (12211212) = (1)(221121)(2)
             (122112122) = (1)(221121)(2)(2)
            (1221121221) = (1)(221121)(221)
           (12211212212) = (1)(221121)(221)(2)
          (122112122122) = (1)(221121)(221)(2)(2)
         (1221121221221) = (1)(221121)(221)(221)
        (12211212212211) = (1)(221121)(2212211)
       (122112122122112) = (1)(221121)(2212211)(2)
      (1221121221221121) = (1)(221121)(221221121)
     (12211212212211211) = (1)(221121)(2212211211)
    (122112122122112112) = (1)(221121)(2212211211)(2)
   (1221121221221121122) = (1)(221121)(2212211211)(2)(2)
  (12211212212211211221) = (1)(221121)(2212211211)(221)

The non-"co" version is A296658.

Cf. A000002, A001037, A060223, A088568, A102659, A275692, A329312, A329315, A329317, A329318.

kolagrow[q_]:=If[Length[q]<2,Take[{1,2},Length[q]+1],Append[q,Switch[{q[[Length[Split[q]]]],q[[-2]],Last[q]},{1,1,1},0,{1,1,2},1,{1,2,1},2,{1,2,2},0,{2,1,1},2,{2,1,2},2,{2,2,1},1,{2,2,2},1]]]
kol[n_Integer]:=If[n==0,{},Nest[kolagrow,{1},n-1]];
colynQ[q_]:=Array[Union[{RotateRight[q,#],q}]=={RotateRight[q,#],q}&,Length[q]-1,1,And];
colynfac[q_]:=If[Length[q]==0,{},Function[i,Prepend[colynfac[Drop[q,i]],Take[q,i]]]@Last[Select[Range[Length[q]],colynQ[Take[q,#]]&]]];
Table[Length[colynfac[kol[n]]],{n,0,100}]

A332273 Sizes of maximal weakly decreasing subsequences of A000002.

Original entry on oeis.org

1, 4, 2, 3, 4, 3, 3, 3, 2, 4, 3, 2, 3, 4, 2, 3, 3, 3, 3, 4, 2, 3, 4, 3, 2, 3, 3, 3, 4, 2, 3, 4, 3, 3, 3, 2, 3, 4, 3, 2, 4, 3, 3, 3, 3, 3, 4, 2, 3, 3, 3, 3, 3, 3, 3, 4, 2, 3, 3, 3, 3, 3, 2, 4, 3, 2, 3, 3, 3, 4, 2, 3, 4, 3, 2, 4, 3, 3, 3, 3, 2, 4, 3, 3, 3, 3, 3

Offset: 1

Gus Wiseman, Mar 08 2020

nonn

			The weakly decreasing subsequences begin: (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).

The number of runs in the first n terms of A000002 is A156253.
The weakly increasing version is A332875.
Cf. A000002, A001462, A013947, A013948, A088568, A288605, A296658, A329315, A329316, A329317, A329362.

kolagrow[q_]:=If[Length[q]<2,Take[{1,2},Length[q]+1],Append[q,Switch[{q[[Length[Split[q]]]],q[[-2]],Last[q]},{1,1,1},0,{1,1,2},1,{1,2,1},2,{1,2,2},0,{2,1,1},2,{2,1,2},2,{2,2,1},1,{2,2,2},1]]]
kol[n_Integer]:=Nest[kolagrow,{1},n-1];
Length/@Split[kol[40],#1>=#2&]

a(n) = A000002(2*n - 2) + A000002(2*n - 1) for n > 1.

cp's OEIS Frontend

A054351 Successive generations of the Kolakoski sequence A000002.

Views

Author

Keywords

Crossrefs

Programs

Python

Extensions

A054352 Lengths of successive generations of the Kolakoski sequence A000002.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A329317 Length of the Lyndon factorization of the reversed first n terms of A000002.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A013947 Positions of 1's in Kolakoski sequence (A000002).

Views

Author

Keywords

Crossrefs

Formula

A074286 Partial sum of the Kolakoski sequence (A000002) minus n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A119493 Determinant of n X n matrix of first n^2 terms of Kolakoski sequence (A000002).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Extensions

A329316 Irregular triangle read by rows where row n gives the sequence of lengths of components of the Lyndon factorization of the reversed first n terms of A000002.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A022292 Exactly half of first a(n) terms of Kolakoski sequence A000002 are 1's (not known to be infinite).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

JavaScript

Mathematica

Formula

Extensions