A088568 -id:A088568 - cp's OEIS frontend

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

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.

A332875 Sizes of maximal weakly increasing subsequences of A000002.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Mar 08 2020

nonn

			The weakly increasing 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).

The number of runs in the first n terms of A000002 is A156253.
The weakly decreasing version is A332273.
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 - 1) + A000002(2*n).

A289323 Number of twos minus number of ones in the first 2^n entries of the Kolakoski sequence, A000002.

Original entry on oeis.org

-1, 0, 0, 0, 0, -2, 0, 0, -2, 0, -2, 0, -6, 6, 0, 6, 44, 26, -20, -48, 52, 58, 104, -82, -250, -270, -474, -1864, -3094, -4588, -2534, -7574, -1522, 1818, 9264, 18082, 8898, -30500, -20586, -3232, -90522, -127446, -231384, -83574, -87364, 267886

Offset: 0

Richard P. Brent, Jul 05 2017

sign

This is equivalent to A289322, since a(n) = (#twos)-(#ones) = 2^n-2*(#ones) in the first 2^n entries of A000002.
For example, a(5)=15-17=(32-17)-17=32-2*17=-2 because there are 15 twos and 17 ones in the first 32=2^5 entries of A000002.
The entries in this sequence appear to be of order 2^(n/2), whereas the entries in A289322 are larger (of order 2^n).

			The first 32 entries of the Kolakoski sequence, A000002, are 12211212212211211221211212211211. From this we see that a(5)=15-17=-2, since among the first 2^5 letters, 15 of them are twos and 17 of them are ones.

See references for A289322.

Richard P. Brent, Table of n, a(n) for n = 0..64

Cf. A000002, A054353, A074286, A088568, A156077, A289322.

a(n) = 2^n - 2*A289322(n) = -A088568(2^n) = 2*A054353(2^n) - 3*2^n = 2^n - 2*A156077(2^n).

A294448 Discrepancy of the Kolakoski sequence A000002.

Original entry on oeis.org

-1, 0, 1, 0, -1, 0, -1, 0, 1, 0, 1, 2, 1, 0, 1, 0, -1, 0, 1, 0, 1, 0, -1, 0, -1, 0, 1, 0, -1, 0, -1, -2, -1, -2, -1, 0, -1, 0, 1, 0, -1, 0, -1, 0, 1, 0, 1, 0, -1, 0, -1, -2, -1, 0, -1, 0, 1, 0, -1, 0, -1, 0, 1, 0, 1, 2, 1, 0, 1, 0, -1, 0, -1, 0, 1, 0, 1, 0, -1, 0, 1, 0, 1, 2, 1, 0, 1, 0, 1, 2

Offset: 1

N. J. A. Sloane, Nov 21 2017

The discrepancy is defined by a(n) = Sum_{i=1..n} (-1)^k(i), where k(i) = A000002(i). The negative of this sequence is already in the OEIS (A088568), but does not seem to be found if one looks up -1, 0, 1, 0, -1, 0, -1, 0, 1, 0, 1, ..., so this version has been added for completeness.

See A088568 for more information and references.

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Richard P. Brent, Fast algorithms for the Kolakoski sequence, Slides from a talk, 2016.

Cf. A000002, A088568.

For records see A294449.

A022327 Least k such that the first k terms of the Kolakoski sequence (A000002) contain n more 1's than 2's.

Original entry on oeis.org

1, 32, 257, 798, 825, 858, 1127, 1398, 1497, 1524, 1533, 193140, 193173, 194036, 194045, 195378, 196371, 196380, 198571, 198634, 199149, 199554, 199861, 200286, 201759, 201786, 201795, 205330, 205687, 205714, 205807, 206032, 206065, 206092

Offset: 1

Clark Kimberling

nonn

A.H.M. Smeets, Table of n, a(n) for n = 1..10169

Cf. A000002, A088568.

Cf. A025503 (2's over 1's).

A025506 Least k such that first k terms of A006928 contain n more 1's than 2's.

Original entry on oeis.org

2, 1, 4, 31, 256, 797, 824, 857, 1126, 1397, 1496, 1523, 1532, 193139, 193172, 194035, 194044, 195377, 196370, 196379, 198570, 198633, 199148, 199553, 199860, 200285, 201758, 201785, 201794, 205329, 205686, 205713, 205806, 206031, 206064, 206091

Offset: 0

David W. Wilson

nonn

a(n)=i => i is the smallest index such that A088568(i)=n. Because the difference between successive elements of A088568 can only be -1 or 1, the sequence is monotonic increasing except for a(1) < a(0). - Paolo Bonzini, Jul 06 2016

			 A088568 begins with 1,0,1,2.. 0 appears first at index 2, 1 appears first at index 1, 2 appears first at index 4. - _Paolo Bonzini_, Jul 06 2016

Paolo Bonzini, Table of n, a(n) for n = 0..64

Cf. A006928, A025507, A088568, A274775.

Edited by N. J. A. Sloane, Aug 11 2016

A025507 Least k such that the first k terms of A006928 contain n more 2's than 1's.

Original entry on oeis.org

11, 92, 377, 470, 6351, 6968, 7175, 7268, 7565, 7970, 20337, 20370, 21981, 22008, 25637, 25664, 25691, 27968, 39183, 39210, 42397, 43128, 43149, 48636, 48729, 48756, 49013, 49040, 49067, 49094, 49863, 50080, 50089, 50386, 50413, 50958, 51343, 52242

Offset: 1

David W. Wilson

nonn

a(n)=i => i is the smallest index such that A088568(i)=-n. - Paolo Bonzini, Jul 06 2016.

Paolo Bonzini, Table of n, a(n) for n = 1..86

Cf. A006928, A088568, A025506, A274775.

A274775 Indices in A006928 where the imbalance between 1's and 2's sets a new record.

Original entry on oeis.org

1, 2, 4, 11, 31, 92, 256, 377, 470, 797, 824, 857, 1126, 1397, 1496, 1523, 1532, 6351, 6968, 7175, 7268, 7565, 7970, 20337, 20370, 21981, 22008, 25637, 25664, 25691, 27968, 39183, 39210, 42397, 43128, 43149, 48636, 48729, 48756, 49013, 49040, 49067, 49094, 49863

Offset: 1

Paolo Bonzini, Jul 06 2016

nonn

Indices in A088568 where new values appear.

Sorted union of A025507 and A025506.

Paolo Bonzini, Table of n, a(n) for n = 1..151

Cf. A006928, A025507, A088568, A025506

A289322 Number of 1s in the first 2^n entries of the Kolakoski sequence, A000002.

Original entry on oeis.org

1, 1, 2, 4, 8, 17, 32, 64, 129, 256, 513, 1024, 2051, 4093, 8192, 16381, 32746, 65523, 131082, 262168, 524262, 1048547, 2097100, 4194345, 8388733, 16777351, 33554669, 67109796, 134219275, 268437750, 536872179

Offset: 0

Richard P. Brent, Jul 05 2017

nonn

			The first 32 entries of the Kolakoski sequence, A000002, are 12211212212211211221211212211211. From this we see that a(5)=17, since among the first 2^5 letters, 17 of them are 1s.

Richard P. Brent, Table of n, a(n) for n = 0..64
Richard P. Brent and Judy-anne H. Osborn, A fast algorithm for the Kolakoski sequence, Dec. 2016
J. Nilsson, A Space Efficient Algorithm for the Calculation of the Digit Distribution in the Kolakoski Sequence, arXiv preprint arXiv:1110.4228 [math.CO], 2011.
M. Rao, Trucs et bidules sur la séquence de Kolakoski, Oct. 2012.

Cf. A000002. Analogous for powers of ten is A195206. Equivalent but with smaller entries is A289323. Closely related are A054353, A074286, A088568, A156077.

a(n) = (2^n + A088568(2^n))/2 = (2^n - A289323(n))/2.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A332273 Sizes of maximal weakly decreasing subsequences of A000002.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A332875 Sizes of maximal weakly increasing subsequences of A000002.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A289323 Number of twos minus number of ones in the first 2^n entries of the Kolakoski sequence, A000002.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A294448 Discrepancy of the Kolakoski sequence A000002.

Views

Author

Keywords

Comments

Links

Crossrefs

A022327 Least k such that the first k terms of the Kolakoski sequence (A000002) contain n more 1's than 2's.

Views

Author

Keywords

Links

Crossrefs

A025506 Least k such that first k terms of A006928 contain n more 1's than 2's.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A025507 Least k such that the first k terms of A006928 contain n more 2's than 1's.

Views

Author

Keywords

Comments

Links

Crossrefs

A274775 Indices in A006928 where the imbalance between 1's and 2's sets a new record.

Views

Author

Keywords

Comments

Links

Crossrefs

A289322 Number of 1s in the first 2^n entries of the Kolakoski sequence, A000002.

Views

Author

Keywords

Examples

Links