A329312 -id:A329312 - cp's OEIS frontend

A333765 Number of co-Lyndon factorizations of the k-th composition in standard order.

1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 2, 1, 2, 2, 4, 5, 1, 1, 1, 1, 2, 1, 2, 1, 2, 2, 4, 2, 4, 4, 7, 7, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 3, 1, 2, 2, 2, 1, 2, 2, 2, 2, 5, 2, 5, 2, 4, 4, 9, 4, 7, 7, 12, 11, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 2, 2, 2, 4, 1

Offset: 0

Gus Wiseman, Apr 13 2020

nonn

We define the co-Lyndon product of two or more finite sequences to be the lexicographically minimal sequence obtainable by shuffling the sequences together. For example, the co-Lyndon product of (2,3,1) with (2,1,3) is (2,1,2,3,1,3), the product of (2,2,1) with (2,1,3) is (2,1,2,2,1,3), and the product of (1,2,2) with (2,1,2,1) is (1,2,1,2,1,2,2). A co-Lyndon factorization of a composition c is a multiset of compositions whose co-Lyndon product is c.
A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.
Also the number of multiset partitions of the co-Lyndon-word factorization of the n-th composition in standard order.

			The a(54) = 5, a(61) = 7, and a(237) = 9 factorizations:
  ((1,2,1,2))      ((1,1,1,2,1))        ((1,1,2,1,2,1))
  ((1),(2,1,2))    ((1),(1,1,2,1))      ((1),(1,2,1,2,1))
  ((1,2),(2,1))    ((1,1),(1,2,1))      ((1,1),(2,1,2,1))
  ((2),(1,2,1))    ((2,1),(1,1,1))      ((1,2,1),(1,2,1))
  ((1),(2),(2,1))  ((1),(1),(1,2,1))    ((2,1),(1,1,2,1))
                   ((1),(1,1),(2,1))    ((1),(1),(2,1,2,1))
                   ((1),(1),(1),(2,1))  ((1,1),(2,1),(2,1))
                                        ((1),(2,1),(1,2,1))
                                        ((1),(1),(2,1),(2,1))

The dual version is A333940.
Binary necklaces are counted by A000031.
Necklace compositions are counted by A008965.
Necklaces covering an initial interval are counted by A019536.
Lyndon compositions are counted by A059966.
Numbers whose reversed binary expansion is a necklace are A328595.
Numbers whose prime signature is a necklace are A329138.
Length of Lyndon factorization of binary expansion is A211100.
Length of co-Lyndon factorization of binary expansion is A329312.
Length of co-Lyndon factorization of reversed binary expansion is A329326.
Length of Lyndon factorization of reversed binary expansion is A329313.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Necklaces are A065609.
- Sum is A070939.
- Runs are counted by A124767.
- Rotational symmetries are counted by A138904.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Lyndon compositions are A275692.
- Co-Lyndon compositions are A326774.
- Aperiodic compositions are A328594.
- Reversed co-necklaces are A328595.
- Length of Lyndon factorization is A329312.
- Rotational period is A333632.
- Co-necklaces are A333764.
- Dealings are counted by A333939.
- Reversed necklaces are A333943.
- Length of co-Lyndon factorization is A334029.
- Combinatory separations are A334030.
Cf. A000740, A001037, A034691, A060223, A211100, A269134, A292884, A328596.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
colynprod[]:={};colynprod[{},b_List]:=b;colynprod[a_List,{}]:=a;colynprod[a_List]:=a;
colynprod[{x_,a___},{y_,b___}]:=Switch[Ordering[If[x=!=y,{x,y},{colynprod[{a},{x,b}],colynprod[{x,a},{b}]}]],{1,2},Prepend[colynprod[{a},{y,b}],x],{2,1},Prepend[colynprod[{x,a},{b}],y]];
colynprod[a_List,b_List,c__List]:=colynprod[a,colynprod[b,c]];
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
dealings[q_]:=Union[Function[ptn,Sort[q[[#]]&/@ptn]]/@sps[Range[Length[q]]]];
Table[Length[Select[dealings[stc[n]],colynprod@@#==stc[n]&]],{n,0,100}]

For n > 0, Sum_{k = 2^(n-1)..2^n-1} a(k) = A034691(n).

A334029 Length of the co-Lyndon factorization of the k-th composition in standard order.

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Apr 14 2020

nonn

We define the co-Lyndon product of two or more finite sequences to be the lexicographically minimal sequence obtainable by shuffling the sequences together. For example, the co-Lyndon product of (2,3,1) with (2,1,3) is (2,1,2,3,1,3), the product of (2,2,1) with (2,1,3) is (2,1,2,2,1,3), and the product of (1,2,2) with (2,1,2,1) is (1,2,1,2,1,2,2). 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, (1,0,0,1) has co-Lyndon factorization {(1),(1,0,0)}.

A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The 441st composition in standard order is (1,2,1,1,3,1), with co-Lyndon factorization {(1),(3,1),(2,1,1)}, so a(441) = 3.

The dual version is A329312.
The version for binary expansion is (also) A329312.
The version for reversed binary expansion is A329326.
Binary Lyndon/co-Lyndon words are counted by A001037.
Necklaces covering an initial interval are A019536.
Lyndon/co-Lyndon compositions are counted by A059966
Length of Lyndon factorization of binomial expansion is A211100.
Numbers whose prime signature is a necklace are A329138.
Length of Lyndon factorization of reversed binary expansion is A329313.
A list of all binary co-Lyndon words is A329318.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Necklaces are A065609.
- Sum is A070939.
- Runs are counted by A124767.
- Rotational symmetries are counted by A138904.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Lyndon compositions are A275692.
- Co-Lyndon compositions are A326774.
- Aperiodic compositions are A328594.
- Reversed co-necklaces are A328595.
- Rotational period is A333632.
- Co-necklaces are A333764.
- Co-Lyndon factorizations are counted by A333765.
- Lyndon factorizations are counted by A333940.
- Reversed necklaces are A333943.
- Co-necklaces are A334028.
Cf. A034691, A060223, A102659, A211097, A292884, A296372, A328596, A329358, A329359, A329362, A329400, A329401, A333939.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
colynQ[q_]:=Length[q]==0||Array[Union[{RotateRight[q,#1],q}]=={RotateRight[q,#1],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,#1]]&]]]]
Table[Length[colynfac[stc[n]]],{n,0,100}]

A334265 Numbers k such that the k-th composition in standard order is a reversed Lyndon word.

Original entry on oeis.org

0, 1, 2, 4, 5, 8, 9, 11, 16, 17, 18, 19, 21, 23, 32, 33, 34, 35, 37, 39, 41, 43, 47, 64, 65, 66, 67, 68, 69, 71, 73, 74, 75, 77, 79, 81, 83, 85, 87, 91, 95, 128, 129, 130, 131, 132, 133, 135, 137, 138, 139, 141, 143, 145, 146, 147, 149, 151, 155, 159, 161, 163

Offset: 1

Gus Wiseman, Apr 22 2020

nonn

Reversed Lyndon words are different from co-Lyndon words (A326774).
A Lyndon word is a finite sequence of positive integers that is lexicographically strictly less than all of its cyclic rotations.
The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The sequence of all reversed Lyndon words begins:
    0: ()            37: (3,2,1)         83: (2,3,1,1)
    1: (1)           39: (3,1,1,1)       85: (2,2,2,1)
    2: (2)           41: (2,3,1)         87: (2,2,1,1,1)
    4: (3)           43: (2,2,1,1)       91: (2,1,2,1,1)
    5: (2,1)         47: (2,1,1,1,1)     95: (2,1,1,1,1,1)
    8: (4)           64: (7)            128: (8)
    9: (3,1)         65: (6,1)          129: (7,1)
   11: (2,1,1)       66: (5,2)          130: (6,2)
   16: (5)           67: (5,1,1)        131: (6,1,1)
   17: (4,1)         68: (4,3)          132: (5,3)
   18: (3,2)         69: (4,2,1)        133: (5,2,1)
   19: (3,1,1)       71: (4,1,1,1)      135: (5,1,1,1)
   21: (2,2,1)       73: (3,3,1)        137: (4,3,1)
   23: (2,1,1,1)     74: (3,2,2)        138: (4,2,2)
   32: (6)           75: (3,2,1,1)      139: (4,2,1,1)
   33: (5,1)         77: (3,1,2,1)      141: (4,1,2,1)
   34: (4,2)         79: (3,1,1,1,1)    143: (4,1,1,1,1)
   35: (4,1,1)       81: (2,4,1)        145: (3,4,1)

The non-reversed version is A275692.
The generalization to necklaces is A333943.
The dual version (reversed co-Lyndon words) is A328596.
The case that is also co-Lyndon is A334266.
Binary Lyndon words are counted by A001037.
Lyndon compositions are counted by A059966.
Normal Lyndon words are counted by A060223.
Numbers whose prime signature is a reversed Lyndon word are A334298.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Necklaces are A065609.
- Sum is A070939.
- Reverse is A228351 (triangle).
- Strict compositions are A233564.
- Constant compositions are A272919.
- Lyndon words are A275692.
- Reversed Lyndon words are A334265 (this sequence).
- Co-Lyndon words are A326774.
- Reversed co-Lyndon words are A328596.
- Length of Lyndon factorization is A329312.
- Distinct rotations are counted by A333632.
- Lyndon factorizations are counted by A333940.
- Length of Lyndon factorization of reverse is A334297.
Cf. A000031, A027375, A138904, A211100, A328595, A329131, A329313, A333764, A334028, A334267.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
lynQ[q_]:=Length[q]==0||Array[Union[{q,RotateRight[q,#1]}]=={q,RotateRight[q,#1]}&,Length[q]-1,1,And];
Select[Range[0,100],lynQ[Reverse[stc[#]]]&]

A302291 a(n) is the period of the binary expansion of n.

Original entry on oeis.org

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

Offset: 0

Rémy Sigrist, Apr 04 2018

Zero is assumed to be represented as 0; otherwise, leading zeros are ignored.

See A302295 for the variant where leading zeros are allowed.

			The first terms, alongside the binary expansion of n with periodic part in parentheses, are:
  n  a(n)    bin(n)
  -- ----    ------
   0    1    (0)
   1    1    (1)
   2    2    (10)
   3    1    (1)(1)
   4    3    (100)
   5    3    (101)
   6    3    (110)
   7    1    (1)(1)(1)
   8    4    (1000)
   9    4    (1001)
  10    2    (10)(10)
  11    4    (1011)
  12    4    (1100)
  13    4    (1101)
  14    4    (1110)
  15    1    (1)(1)(1)(1)
  16    5    (10000)
  17    5    (10001)
  18    5    (10010)
  19    5    (10011)
  20    5    (10100)

Rémy Sigrist, Table of n, a(n) for n = 0..10000
Index entries for sequences related to binary expansion of n

Aperiodic compositions are counted by A000740.
Aperiodic binary words are counted by A027375.
The orderless period of prime indices is A052409.
Numbers whose binary expansion is periodic are A121016.
Periodic compositions are counted by A178472.
Numbers whose prime signature is aperiodic are A329139.
Compositions by number of distinct rotations are A333941.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Necklaces are A065609.
- Sum is A070939.
- Runs are counted by A124767.
- Rotational symmetries are counted by A138904.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Lyndon compositions are A275692.
- Co-Lyndon compositions are A326774.
- Aperiodic compositions are A328594.
- Rotational period is A333632.
- Co-necklaces are A333764.
- Reversed necklaces are A333943.
Cf. A000031, A001037, A008965, A019536, A020330, A211100, A302295, A328595, A328596, A329312, A329313, A329326.

Table[If[n==0,1,Length[Union[Array[RotateRight[IntegerDigits[n,2],#]&,IntegerLength[n,2]]]]],{n,0,50}] (* Gus Wiseman, Apr 19 2020 *)

a(n) = my (l=max(1, #binary(n))); fordiv (l, w, if (#Set(digits(n, 2^w))<=1, return (w)))

a(n) = A070939(n) / A138904(n).
a(2^n) = n + 1 for any n >= 0.
a(2^n - 1) = 1 for any n >= 0.
a(A020330(n)) = a(n) for any n > 0.

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}]

A333939 Number of multisets of compositions that can be shuffled together to obtain the k-th composition in standard order.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 4, 2, 5, 4, 5, 1, 2, 2, 4, 2, 4, 5, 7, 2, 5, 4, 10, 4, 10, 7, 7, 1, 2, 2, 4, 2, 5, 5, 7, 2, 5, 3, 9, 5, 13, 11, 12, 2, 5, 5, 10, 5, 11, 13, 18, 4, 10, 9, 20, 7, 18, 12, 11, 1, 2, 2, 4, 2, 5, 5, 7, 2, 4, 4, 11, 5, 14, 11, 12, 2

Offset: 0

Gus Wiseman, Apr 15 2020

nonn

Number of ways to deal out the k-th composition in standard order to form a multiset of hands.

A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The dealings for n = 1, 3, 7, 11, 13, 23, 43:
  (1)  (11)    (111)      (211)      (121)      (2111)        (2211)
       (1)(1)  (1)(11)    (1)(21)    (1)(12)    (11)(21)      (11)(22)
               (1)(1)(1)  (2)(11)    (1)(21)    (1)(211)      (1)(221)
                          (1)(1)(2)  (2)(11)    (2)(111)      (21)(21)
                                     (1)(1)(2)  (1)(1)(21)    (2)(211)
                                                (1)(2)(11)    (1)(1)(22)
                                                (1)(1)(1)(2)  (1)(2)(21)
                                                              (2)(2)(11)
                                                              (1)(1)(2)(2)

Multisets of compositions are counted by A034691.
Combinatory separations of normal multisets are counted by A269134.
Dealings with total sum n are counted by A292884.
Length of co-Lyndon factorization of binary expansion is A329312.
Length of Lyndon factorization of reversed binary expansion is A329313.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Necklaces are A065609.
- Sum is A070939.
- Runs are counted by A124767.
- Rotational symmetries are counted by A138904.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Lyndon words are A275692.
- Co-Lyndon words are A326774.
- Aperiodic compositions are A328594.
- Length of Lyndon factorization is A329312.
- Distinct rotations are counted by A333632.
- Co-Lyndon factorizations are counted by A333765.
- Lyndon factorizations are counted by A333940.
- Length of co-Lyndon factorization is A334029.
- Combinatory separations are A334030.
Cf. A000031, A000740, A001037, A008965, A027375, A059966, A060223, A211100, A328595, A328596, A333764, A333943.

nn=100;
comps[0]:={{}};comps[n_]:=Join@@Table[Prepend[#,i]&/@comps[n-i],{i,n}];
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
dealings[q_]:=Union[Function[ptn,Sort[q[[#]]&/@ptn]]/@sps[Range[Length[q]]]];
Table[Length[dealings[stc[n]]],{n,0,nn}]

For n > 0, Sum_{k = 2^(n-1)..2^n-1} a(k) = A292884(n).

A334266 Numbers k such that the k-th composition in standard order is both a reversed Lyndon word and a co-Lyndon word.

Original entry on oeis.org

0, 1, 2, 4, 5, 8, 9, 11, 16, 17, 18, 19, 21, 23, 32, 33, 34, 35, 37, 39, 43, 47, 64, 65, 66, 67, 68, 69, 71, 73, 74, 75, 77, 79, 85, 87, 91, 95, 128, 129, 130, 131, 132, 133, 135, 137, 138, 139, 141, 143, 146, 147, 149, 151, 155, 159, 171, 173, 175, 183, 191

Offset: 1

Gus Wiseman, Apr 22 2020

nonn

A Lyndon word is a finite sequence of positive integers that is lexicographically strictly less than all of its cyclic rotations. Co-Lyndon is defined similarly, except with strictly greater instead of strictly less.

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The sequence of all reversed Lyndon co-Lyndon words begins:
    0: ()            37: (3,2,1)         91: (2,1,2,1,1)
    1: (1)           39: (3,1,1,1)       95: (2,1,1,1,1,1)
    2: (2)           43: (2,2,1,1)      128: (8)
    4: (3)           47: (2,1,1,1,1)    129: (7,1)
    5: (2,1)         64: (7)            130: (6,2)
    8: (4)           65: (6,1)          131: (6,1,1)
    9: (3,1)         66: (5,2)          132: (5,3)
   11: (2,1,1)       67: (5,1,1)        133: (5,2,1)
   16: (5)           68: (4,3)          135: (5,1,1,1)
   17: (4,1)         69: (4,2,1)        137: (4,3,1)
   18: (3,2)         71: (4,1,1,1)      138: (4,2,2)
   19: (3,1,1)       73: (3,3,1)        139: (4,2,1,1)
   21: (2,2,1)       74: (3,2,2)        141: (4,1,2,1)
   23: (2,1,1,1)     75: (3,2,1,1)      143: (4,1,1,1,1)
   32: (6)           77: (3,1,2,1)      146: (3,3,2)
   33: (5,1)         79: (3,1,1,1,1)    147: (3,3,1,1)
   34: (4,2)         85: (2,2,2,1)      149: (3,2,2,1)
   35: (4,1,1)       87: (2,2,1,1,1)    151: (3,2,1,1,1)

The version for binary expansion is A334267.
Compositions of this type are counted by A334269.
Normal sequences of this type are counted by A334270.
Necklace compositions of this type are counted by A334271.
Binary Lyndon words are counted by A001037.
Lyndon compositions are counted by A059966.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Necklaces are A065609.
- Sum is A070939.
- Reverse is A228351 (triangle).
- Strict compositions are A233564.
- Constant compositions are A272919.
- Lyndon words are A275692.
- Reversed Lyndon words are A334265.
- Co-Lyndon words are A326774.
- Reversed co-Lyndon words are A328596.
- Length of Lyndon factorization is A329312.
- Length of Lyndon factorization of reverse is A334297.
- Length of co-Lyndon factorization is A334029.
- Length of co-Lyndon factorization of reverse is A329313.
- Distinct rotations are counted by A333632.
- Co-Lyndon factorizations are counted by A333765.
- Lyndon factorizations are counted by A333940.
Cf. A000740, A008965, A065609, A329324, A333764, A333943, A334272, A334297.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
lynQ[q_]:=Length[q]==0||Array[Union[{q,RotateRight[q,#1]}]=={q,RotateRight[q,#1]}&,Length[q]-1,1,And];
colynQ[q_]:=Length[q]==0||Array[Union[{RotateRight[q,#],q}]=={RotateRight[q,#],q}&,Length[q]-1,1,And];
Select[Range[0,100],lynQ[Reverse[stc[#]]]&&colynQ[stc[#]]&]

Intersection of A334265 and A326774.

A334269 Number of compositions of n that are both a reversed Lyndon word and a co-Lyndon word.

Original entry on oeis.org

1, 1, 2, 3, 6, 8, 16, 23, 40, 62, 110, 169, 302, 492, 856, 1454, 2572, 4428, 7914, 13935, 25036, 44842, 81298, 147149, 268952, 491746, 904594, 1667091, 3085950, 5723367, 10652544, 19865887, 37150314, 69608939, 130723184, 245935633, 463590444, 875306913, 1655451592, 3135613649, 5948011978, 11298215516

Offset: 1

Gus Wiseman, Apr 24 2020

nonn

Also the number of compositions of n that are both a Lyndon word and a reversed co-Lyndon word.
A composition of n is a finite sequence of positive integers summing to n.
A Lyndon word is a finite sequence of positive integers that is lexicographically strictly less than all of its cyclic rotations. Co-Lyndon is defined similarly, except with strictly greater instead of strictly less.

			The a(1) = 1 through a(7) = 16 compositions:
  (1)  (2)  (3)   (4)    (5)     (6)      (7)
            (21)  (31)   (32)    (42)     (43)
                  (211)  (41)    (51)     (52)
                         (221)   (321)    (61)
                         (311)   (411)    (322)
                         (2111)  (2211)   (331)
                                 (3111)   (421)
                                 (21111)  (511)
                                          (2221)
                                          (3121)
                                          (3211)
                                          (4111)
                                          (21211)
                                          (22111)
                                          (31111)
                                          (211111)

The version for binary expansion is A334267.
Compositions of this type are ranked by A334266.
Normal sequences of this type are counted by A334270.
Necklace compositions of this type are counted by A334271.
Aperiodic compositions are counted by A000740.
Binary Lyndon words are counted by A001037.
Necklace compositions are counted by A008965.
Normal Lyndon words are counted by A060223.
Lyndon compositions are counted by A059966.
All of the following pertain to compositions in standard order (A066099):
- Lyndon words are A275692.
- Co-Lyndon words are A326774.
- Reversed Lyndon words are A334265.
- Reversed co-Lyndon words are A328596.
- Length of Lyndon factorization is A329312.
- Length of co-Lyndon factorization is A334029.
- Length of Lyndon factorization of reverse is A334297.
- Length of co-Lyndon factorization of reverse is A329313.
- Lyndon factorizations are counted by A333940.
- Co-Lyndon factorizations are counted by A333765.
- Aperiodic compositions are A328594.
- Distinct rotations are counted by A333632.
Cf. A034691, A065609, A275692, A328596, A329141, A329324, A329326, A334266, A334272, A334273, A334274.

lynQ[q_]:=Length[q]==0||Array[Union[{q,RotateRight[q,#1]}]=={q,RotateRight[q,#1]}&,Length[q]-1,1,And];
colynQ[q_]:=Length[q]==0||Array[Union[{RotateRight[q,#],q}]=={RotateRight[q,#],q}&,Length[q]-1,1,And];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],lynQ[Reverse[#]]&&colynQ[#]&]],{n,0,15}]

Offset corrected and a(21)-a(42) from Bert Dobbelaere, Apr 26 2020

A329327 Numbers whose binary expansion has Lyndon factorization of length 2 (the minimum for n > 1).

Original entry on oeis.org

2, 3, 5, 9, 11, 17, 19, 23, 33, 35, 37, 39, 43, 47, 65, 67, 69, 71, 75, 77, 79, 87, 95, 129, 131, 133, 135, 137, 139, 141, 143, 147, 149, 151, 155, 157, 159, 171, 175, 183, 191, 257, 259, 261, 263, 265, 267, 269, 271, 275, 277, 279, 281, 283, 285, 287, 293

Offset: 1

Gus Wiseman, Nov 12 2019

nonn

First differs from A329357 in having 77 and lacking 83.

Also numbers whose decapitated binary expansion is a Lyndon word (see also A329401).

			The binary expansion of each term together with its Lyndon factorization begins:
   2:      (10) = (1)(0)
   3:      (11) = (1)(1)
   5:     (101) = (1)(01)
   9:    (1001) = (1)(001)
  11:    (1011) = (1)(011)
  17:   (10001) = (1)(0001)
  19:   (10011) = (1)(0011)
  23:   (10111) = (1)(0111)
  33:  (100001) = (1)(00001)
  35:  (100011) = (1)(00011)
  37:  (100101) = (1)(00101)
  39:  (100111) = (1)(00111)
  43:  (101011) = (1)(01011)
  47:  (101111) = (1)(01111)
  65: (1000001) = (1)(000001)
  67: (1000011) = (1)(000011)
  69: (1000101) = (1)(000101)
  71: (1000111) = (1)(000111)
  75: (1001011) = (1)(001011)
  77: (1001101) = (1)(001101)

Positions of 2's in A211100.
Positions of rows of length 2 in A329314.
The "co-" and reversed version is A329357.
Binary Lyndon words are counted by A001037 and ranked by A102659.
Length of the co-Lyndon factorization of the binary expansion is A329312.
Cf. A059966, A060223, A211097, A275692, A328594, A328595, A328596, A329131, A329313, A329325, A329326, A339608.

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,#1]]&]]]];
Select[Range[100],Length[lynfac[IntegerDigits[#,2]]]==2&]

a(n) = A339608(n) + 1. - Harald Korneliussen, Mar 12 2020

A333941 Triangle read by rows where T(n,k) is the number of compositions of n with rotational period k.

Original entry on oeis.org

1, 0, 1, 0, 2, 0, 0, 2, 2, 0, 0, 3, 2, 3, 0, 0, 2, 4, 6, 4, 0, 0, 4, 6, 9, 8, 5, 0, 0, 2, 6, 15, 20, 15, 6, 0, 0, 4, 8, 24, 32, 35, 18, 7, 0, 0, 3, 10, 27, 56, 70, 54, 28, 8, 0, 0, 4, 12, 42, 84, 125, 120, 84, 32, 9, 0, 0, 2, 10, 45, 120, 210, 252, 210, 120, 45, 10, 0

Offset: 0

Gus Wiseman, Apr 16 2020

A composition of n is a finite sequence of positive integers summing to n.

			Triangle begins:
   1
   0   1
   0   2   0
   0   2   2   0
   0   3   2   3   0
   0   2   4   6   4   0
   0   4   6   9   8   5   0
   0   2   6  15  20  15   6   0
   0   4   8  24  32  35  18   7   0
   0   3  10  27  56  70  54  28   8   0
   0   4  12  42  84 125 120  84  32   9   0
   0   2  10  45 120 210 252 210 120  45  10   0
   0   6  18  66 168 335 450 462 320 162  50  11   0
Row n = 6 counts the following compositions (empty columns indicated by dots):
  .  (6)       (15)    (114)  (1113)  (11112)  .
     (33)      (24)    (123)  (1122)  (11121)
     (222)     (42)    (132)  (1131)  (11211)
     (111111)  (51)    (141)  (1221)  (12111)
               (1212)  (213)  (1311)  (21111)
               (2121)  (231)  (2112)
                       (312)  (2211)
                       (321)  (3111)
                       (411)

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)

Column k = 1 is A000005.
Row sums are A011782.
Diagonal T(2n,n) is A045630(n).
The strict version is A072574.
A version counting runs is A238279.
Column k = n - 1 is A254667.
Aperiodic compositions are counted by A000740.
Aperiodic binary words are counted by A027375.
The orderless period of prime indices is A052409.
Numbers whose binary expansion is periodic are A121016.
Periodic compositions are counted by A178472.
Period of binary expansion is A302291.
Numbers whose prime signature is aperiodic are A329139.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Necklaces are A065609.
- Sum is A070939.
- Rotational symmetries are counted by A138904.
- Constant compositions are A272919.
- Lyndon compositions are A275692.
- Co-Lyndon compositions are A326774.
- Aperiodic compositions are A328594.
- Rotational period is A333632.
- Co-necklaces are A333764.
- Reversed necklaces are A333943.
Cf. A000031, A001037, A008965, A019536, A211100, A291166, A328595, A328596, A329312, A329313, A329326.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Function[c,Length[Union[Array[RotateRight[c,#]&,Length[c]]]]==k]]],{n,0,10},{k,0,n}]

T(n,k)=if(n==0, k==0, sumdiv(n, m, sumdiv(gcd(k,m), d, moebius(d)*binomial(m/d-1, k/d-1)))) \\ Andrew Howroyd, Jan 19 2023

T(n,k) = Sum_{m|n} Sum_{d|gcd(k,m)} mu(d)*binomial(m/d-1, k/d-1) for n > 0. - Andrew Howroyd, Jan 19 2023

cp's OEIS Frontend

A333765 Number of co-Lyndon factorizations of the k-th composition in standard order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A334029 Length of the co-Lyndon factorization of the k-th composition in standard order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A334265 Numbers k such that the k-th composition in standard order is a reversed Lyndon word.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A302291 a(n) is the period of the binary expansion of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A333939 Number of multisets of compositions that can be shuffled together to obtain the k-th composition in standard order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A334266 Numbers k such that the k-th composition in standard order is both a reversed Lyndon word and a co-Lyndon word.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A334269 Number of compositions of n that are both a reversed Lyndon word and a co-Lyndon word.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions