A296372 -id:A296372 - cp's OEIS frontend

A329312 Length of the co-Lyndon factorization of the binary expansion of n.

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

Offset: 1

Gus Wiseman, Nov 10 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).

Also the length of the Lyndon factorization of the inverted binary expansion of n, where the inverted digits are 1 minus the binary digits.

			The binary indices of 1..20 together with their co-Lyndon factorizations are:
   1:     (1) = (1)
   2:    (10) = (10)
   3:    (11) = (1)(1)
   4:   (100) = (100)
   5:   (101) = (10)(1)
   6:   (110) = (110)
   7:   (111) = (1)(1)(1)
   8:  (1000) = (1000)
   9:  (1001) = (100)(1)
  10:  (1010) = (10)(10)
  11:  (1011) = (10)(1)(1)
  12:  (1100) = (1100)
  13:  (1101) = (110)(1)
  14:  (1110) = (1110)
  15:  (1111) = (1)(1)(1)(1)
  16: (10000) = (10000)
  17: (10001) = (1000)(1)
  18: (10010) = (100)(10)
  19: (10011) = (100)(1)(1)
  20: (10100) = (10100)

The non-"co" version is A211100.
Positions of 1's are A275692.
The reversed version is A329326.
Cf. A000031, A001037, A059966, A060223, A211097, A296372, A296658, A329131, A329314, A329318, A329324, A329325.

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[IntegerDigits[n,2]]],{n,100}]

A329326 Length of the co-Lyndon factorization of the reversed binary expansion of n.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Nov 11 2019

nonn

First differs from A211100 at a(77) = 3, A211100(77) = 2. The reversed binary expansion of 77 is (1011001), with co-Lyndon factorization (10)(1100)(1), while the binary expansion is (1001101), with Lyndon factorization of (1)(001101).

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 certain order, their concatenation is equal to their co-Lyndon product. For example, (1001) has sorted co-Lyndon factorization (1)(100).

			The reversed binary expansion of each positive integer together with their co-Lyndon factorizations begins:
   1:     (1) = (1)
   2:    (01) = (0)(1)
   3:    (11) = (1)(1)
   4:   (001) = (0)(0)(1)
   5:   (101) = (10)(1)
   6:   (011) = (0)(1)(1)
   7:   (111) = (1)(1)(1)
   8:  (0001) = (0)(0)(0)(1)
   9:  (1001) = (100)(1)
  10:  (0101) = (0)(10)(1)
  11:  (1101) = (110)(1)
  12:  (0011) = (0)(0)(1)(1)
  13:  (1011) = (10)(1)(1)
  14:  (0111) = (0)(1)(1)(1)
  15:  (1111) = (1)(1)(1)(1)
  16: (00001) = (0)(0)(0)(0)(1)
  17: (10001) = (1000)(1)
  18: (01001) = (0)(100)(1)
  19: (11001) = (1100)(1)
  20: (00101) = (0)(0)(10)(1)

The non-"co" version is A211100.
Positions of 2's are A329357.
Numbers whose binary expansion is co-Lyndon are A275692.
Length of the co-Lyndon factorization of the binary expansion is A329312.
Cf. A000031, A001037, A059966, A060223, A211097, A296372, A296658, A328596, A329131, A329314, A329318, A329324, A329325.

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[Reverse[IntegerDigits[n,2]]]],{n,100}]

A254040 Number T(n,k) of primitive (= aperiodic) n-bead necklaces with colored beads of exactly k different colors; triangle T(n,k), n >= 0, 0 <= k <= n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 0, 0, 2, 2, 0, 0, 3, 9, 6, 0, 0, 6, 30, 48, 24, 0, 0, 9, 89, 260, 300, 120, 0, 0, 18, 258, 1200, 2400, 2160, 720, 0, 0, 30, 720, 5100, 15750, 23940, 17640, 5040, 0, 0, 56, 2016, 20720, 92680, 211680, 258720, 161280, 40320

Offset: 0

Alois P. Heinz, Jan 23 2015

Turning over the necklaces is not allowed.

With other words: T(n,k) is the number of normal Lyndon words of length n and maximum k, where a finite sequence is normal if it spans an initial interval of positive integers. - Gus Wiseman, Dec 22 2017

			Triangle T(n,k) begins:
  1;
  0, 1;
  0, 0,  1;
  0, 0,  2,   2;
  0, 0,  3,   9,    6;
  0, 0,  6,  30,   48,    24;
  0, 0,  9,  89,  260,   300,   120;
  0, 0, 18, 258, 1200,  2400,  2160,   720;
  0, 0, 30, 720, 5100, 15750, 23940, 17640, 5040;
  ...
The T(4,3) = 9 normal Lyndon words of length 4 with maximum 3 are: 1233, 1323, 1332, 1223, 1232, 1322, 1123, 1132, 1213. - _Gus Wiseman_, Dec 22 2017

Alois P. Heinz, Rows n = 0..140, flattened

Columns k=0-10 give: A000007, A063524, A001037 (for n>1), A056288, A056289, A056290, A056291, A254079, A254080, A254081, A254082.
Row sums give A060223.
Main diagonal and lower diagonal give: A000142, A074143.
T(2n,n) gives A254083.
Cf. A074650, A087854.
Cf. A000670, A000740, A008683, A019536, A059966, A185700, A296372, A296373, A296657.

with(numtheory):
b:= proc(n, k) option remember; `if`(n=0, 1,
      add(mobius(n/d)*k^d, d=divisors(n))/n)
    end:
T:= (n, k)-> add(b(n, k-j)*binomial(k,j)*(-1)^j, j=0..k):
seq(seq(T(n, k), k=0..n), n=0..10);

b[n_, k_] := b[n, k] = If[n == 0, 1, Sum[MoebiusMu[n/d]*k^d, {d, Divisors[n]}]/n]; T[n_, k_] := Sum[b[n, k-j]*Binomial[k, j]*(-1)^j, {j, 0, k}]; Table[Table[T[n, k], {k, 0, n}], {n, 0, 10}] // Flatten (* Jean-François Alcover, Jan 27 2015, after Alois P. Heinz *)
LyndonQ[q_]:=q==={}||Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
allnorm[n_,k_]:=If[k===0,If[n===0,{{}}, {}],Join@@Permutations/@Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Select[Subsets[Range[n-1]+1],Length[#]===k-1&]];
Table[Length[Select[allnorm[n,k],LyndonQ]],{n,0,7},{k,0,n}] (* Gus Wiseman, Dec 22 2017 *)

T(n,k) = Sum_{j=0..k} (-1)^j * C(k,j) * A074650(n,k-j).

T(n,k) = Sum_{d|n} mu(d) * A087854(n/d, k) for n >= 1 and 1 <= k <= n. - Petros Hadjicostas, Aug 20 2019

A281013 Tetrangle T(n,k,i) = i-th part of k-th prime composition of n.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Jan 12 2017

The *-product of two or more finite sequences is defined to be the lexicographically minimal sequence obtainable by shuffling them together. Every finite positive integer sequence has a unique *-factorization using prime compositions P = {(1), (2), (21), (3), (211), ...}. See A060223 and A228369 for details.

These are co-Lyndon compositions, ordered first by sum and then lexicographically. - Gus Wiseman, Nov 15 2019

			The prime factorization of (1, 1, 4, 2, 3, 1, 5, 5) is: (11423155) = (1)*(1)*(5)*(5)*(4231). The prime factorizations of the initial terms of A000002 are:
             (1) = (1)
            (12) = (1)*(2)
           (122) = (1)*(2)*(2)
          (1221) = (1)*(221)
         (12211) = (1)*(2211)
        (122112) = (1)*(2)*(2211)
       (1221121) = (1)*(221121)
      (12211212) = (1)*(2)*(221121)
     (122112122) = (1)*(2)*(2)*(221121)
    (1221121221) = (1)*(221)*(221121)
   (12211212212) = (1)*(2)*(221)*(221121)
  (122112122122) = (1)*(2)*(2)*(221)*(221121).
Read as a sequence:
(1), (2), (21), (3), (211), (31), (4), (2111), (221), (311), (32), (41), (5).
Read as a triangle:
(1)
(2)
(21), (3)
(211), (31), (4)
(2111), (221), (311), (32), (41), (5).
Read as a sequence of triangles:
1    2    2 1    2 1 1    2 1 1 1    2 1 1 1 1    2 1 1 1 1 1
          3      3 1      2 2 1      2 2 1 1      2 1 2 1 1
                 4        3 1 1      3 1 1 1      2 2 1 1 1
                          3 2        3 1 2        2 2 2 1
                          4 1        3 2 1        3 1 1 1 1
                          5          4 1 1        3 1 1 2
                                     4 2          3 1 2 1
                                     5 1          3 2 1 1
                                     6            3 2 2
                                                  3 3 1
                                                  4 1 1 1
                                                  4 1 2
                                                  4 2 1
                                                  4 3
                                                  5 1 1
                                                  5 2
                                                  6 1
                                                  7.

Cf. A000740, A215474, A228369, A277427.
The binary version is A329318.
The binary non-"co" version is A102659.
A sequence listing all Lyndon compositions is A294859.
Numbers whose binary expansion is co-Lyndon are A328596.
Numbers whose binary expansion is co-Lyndon are A275692.
Binary Lyndon words are A001037.
Lyndon compositions are A059966.
Normal Lyndon words are A060223.
Cf. A211097, A211100, A296372, A296373, A298941, A329131, A329312, A329313, A329314, A329324, A329326.

colynQ[q_]:=Array[Union[{RotateRight[q,#],q}]=={RotateRight[q,#],q}&,Length[q]-1,1,And];
lexsort[f_,c_]:=OrderedQ[PadRight[{f,c}]];
Table[Sort[Select[Join@@Permutations/@IntegerPartitions[n],colynQ],lexsort],{n,5}] (* Gus Wiseman, Nov 15 2019 *)

Row lengths are A059966(n) = number of prime compositions of n.

A296373 Triangle T(n,k) = number of compositions of n whose factorization into Lyndon words (aperiodic necklaces) is of length k.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 6, 5, 3, 1, 1, 9, 12, 6, 3, 1, 1, 18, 21, 14, 6, 3, 1, 1, 30, 45, 27, 15, 6, 3, 1, 1, 56, 84, 61, 29, 15, 6, 3, 1, 1, 99, 170, 120, 67, 30, 15, 6, 3, 1, 1, 186, 323, 254, 136, 69, 30, 15, 6, 3, 1, 1, 335, 640, 510, 295, 142, 70, 30, 15, 6, 3, 1, 1

Offset: 1

Gus Wiseman, Dec 11 2017

			Triangle begins:
    1;
    1,   1;
    2,   1,   1;
    3,   3,   1,   1;
    6,   5,   3,   1,   1;
    9,  12,   6,   3,   1,   1;
   18,  21,  14,   6,   3,   1,   1;
   30,  45,  27,  15,   6,   3,   1,   1;
   56,  84,  61,  29,  15,   6,   3,   1,   1;
   99, 170, 120,  67,  30,  15,   6,   3,   1,   1;
  186, 323, 254, 136,  69,  30,  15,   6,   3,   1,   1;
  335, 640, 510, 295, 142,  70,  30,  15,   6,   3,   1,   1;

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Wikipedia, Lyndon word: Standard factorization

Cf. A000740, A001045, A008965, A019536, A059966, A060223, A185700, A228369, A232472, A277427, A281013, A296302, A296372.

neckQ[q_]:=Array[OrderedQ[{RotateRight[q,#],q}]&,Length[q]-1,1,And];
aperQ[q_]:=UnsameQ@@Table[RotateRight[q,k],{k,Length[q]}];
qit[q_]:=If[#===Length[q],{q},Prepend[qit[Drop[q,#]],Take[q,#]]]&[Max@@Select[Range[Length[q]],neckQ[Take[q,#]]&&aperQ[Take[q,#]]&]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Length[qit[#]]===k&]],{n,12},{k,n}]

EulerMT(u)={my(n=#u, p=x*Ser(u), vars=variables(p)); Vec(exp( sum(i=1, n, substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i ))-1)}
A(n)=[Vecrev(p/y) | p<-EulerMT(y*vector(n, n, sumdiv(n, d, moebius(n/d) * (2^d-1))/n))]
{ my(T=A(12)); for(n=1, #T, print(T[n])) } \\ Andrew Howroyd, Dec 01 2018

First column is A059966.

A296658 Length of the standard Lyndon word factorization of the first n terms of A000002.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Dec 18 2017

nonn

			The standard Lyndon word factorization of (12211212212211211) is (122)(112122122)(112)(1)(1), so a(17) = 5.
The standard factorizations of initial terms of A000002:
1
12
122
122,1
122,1,1
122,112
122,112,1
122,11212
122,112122
122,112122,1
122,11212212
122,112122122
122,112122122,1
122,112122122,1,1
122,112122122,112
122,112122122,112,1
122,112122122,112,1,1
122,112122122,112,112
122,112122122,1121122
122,112122122,1121122,1

Frédérique Bassino, Julien Clement, and Cyril Nicaud, The standard factorization of Lyndon words: an average point of view, Discrete Mathematics, 290-1 (2005), 1-25.

Row lengths of A329315.
The "co-" version is A329362.
Cf. A000002, A001037, A027375, A060223, A088568, A102659, A211100, A281013, A288605, A296372, A296657, A296659, A328596, A329312, A329316, A329317.

LyndonQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
qit[q_]:=If[#===Length[q],{q},Prepend[qit[Drop[q,#]],Take[q,#]]]&[Max@@Select[Range[Length[q]],LyndonQ[Take[q,#]]&]];
kolagrow[q_]:=If[Length[q]<2,Take[{1,2},Length[q]+1],Append[q,Switch[{q[[Length[Split[q]]]],Part[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]]];
Table[Length[qit[Nest[kolagrow,1,n]]],{n,150}]

A329314 Irregular triangle read by rows where row n gives the lengths of the components in the Lyndon factorization of the binary expansion of n.

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Nov 11 2019

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

			Triangle begins:
   0: ()         20: (1211)      40: (12111)     60: (111111)
   1: (1)        21: (122)       41: (123)       61: (11112)
   2: (11)       22: (131)       42: (1221)      62: (111111)
   3: (11)       23: (14)        43: (15)        63: (111111)
   4: (111)      24: (11111)     44: (1311)      64: (1111111)
   5: (12)       25: (113)       45: (132)       65: (16)
   6: (111)      26: (1121)      46: (141)       66: (151)
   7: (111)      27: (113)       47: (15)        67: (16)
   8: (1111)     28: (11111)     48: (111111)    68: (1411)
   9: (13)       29: (1112)      49: (114)       69: (16)
  10: (121)      30: (11111)     50: (1131)      70: (151)
  11: (13)       31: (11111)     51: (114)       71: (16)
  12: (1111)     32: (111111)    52: (11211)     72: (13111)
  13: (112)      33: (15)        53: (1122)      73: (133)
  14: (1111)     34: (141)       54: (1131)      74: (151)
  15: (1111)     35: (15)        55: (114)       75: (16)
  16: (11111)    36: (1311)      56: (111111)    76: (1411)
  17: (14)       37: (15)        57: (1113)      77: (16)
  18: (131)      38: (141)       58: (11121)     78: (151)
  19: (14)       39: (15)        59: (1113)      79: (16)

Row lengths are A211100.
Row sums are A029837, or, if the first term is 1, A070939.
Ignoring the first digit gives A329325.
Positions of rows of length 2 are A329327.
Binary Lyndon words are counted by A001037 and ranked by A102659.
Numbers whose reversed binary expansion is a Lyndon word are A328596.
Length of the co-Lyndon factorization of the binary expansion is A329312.
Cf. A059966, A211097, A275692, A296372, A329313, A329315, A329318.

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]]&]]]];
Table[Length/@lynfac[If[n==0,{},IntegerDigits[n,2]]],{n,0,50}]

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

Original entry on oeis.org

1, 2, 3, 3, 1, 3, 1, 1, 3, 3, 3, 3, 1, 3, 5, 3, 6, 3, 6, 1, 3, 8, 3, 9, 3, 9, 1, 3, 9, 1, 1, 3, 9, 3, 3, 9, 3, 1, 3, 9, 3, 1, 1, 3, 9, 3, 3, 3, 9, 7, 3, 9, 7, 1, 3, 9, 9, 3, 9, 9, 1, 3, 9, 9, 1, 1, 3, 9, 9, 3, 3, 9, 9, 3, 1, 3, 9, 14, 3, 9, 15, 3, 9, 15, 1, 3

Offset: 1

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 4) never appear in the sequence.

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

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

lynQ[q_]:=Array[Union[{q,RotateRight[q,#1]}]=={q,RotateRight[q,#1]}&,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]]&]]]];
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[kol[n]],{n,100}]

A329325 Irregular triangle read by rows where row n gives the lengths of the components in the Lyndon factorization of the binary expansion of n with first digit removed.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Nov 11 2019

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

			Triangle begins:
   1: ()        21: (22)       41: (23)       61: (1112)
   2: (1)       22: (31)       42: (221)      62: (11111)
   3: (1)       23: (4)        43: (5)        63: (11111)
   4: (11)      24: (1111)     44: (311)      64: (111111)
   5: (2)       25: (13)       45: (32)       65: (6)
   6: (11)      26: (121)      46: (41)       66: (51)
   7: (11)      27: (13)       47: (5)        67: (6)
   8: (111)     28: (1111)     48: (11111)    68: (411)
   9: (3)       29: (112)      49: (14)       69: (6)
  10: (21)      30: (1111)     50: (131)      70: (51)
  11: (3)       31: (1111)     51: (14)       71: (6)
  12: (111)     32: (11111)    52: (1211)     72: (3111)
  13: (12)      33: (5)        53: (122)      73: (33)
  14: (111)     34: (41)       54: (131)      74: (51)
  15: (111)     35: (5)        55: (14)       75: (6)
  16: (1111)    36: (311)      56: (11111)    76: (411)
  17: (4)       37: (5)        57: (113)      77: (6)
  18: (31)      38: (41)       58: (1121)     78: (51)
  19: (4)       39: (5)        59: (113)      79: (6)
  20: (211)     40: (2111)     60: (11111)    80: (21111)
For example, the trimmed binary expansion of 41 is (01001), with Lyndon factorization (01)(001), so row 41 is {2,3}.

Row lengths are A211097.
Row sums are A000523.
Keeping the first digit gives A329314.
Positions of singleton rows are A329327.
Binary Lyndon words are counted by A001037 and ranked by A102659.
Numbers whose reversed binary expansion is a Lyndon word are A328596.
Length of the co-Lyndon factorization of the binary expansion is A329312.
Cf. A059966, A211097, A257250, A275692, A296372, A328594, A329313, A329315, A329318.

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]]&]]]];
Table[Length/@lynfac[Rest[IntegerDigits[n,2]]],{n,100}]

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

cp's OEIS Frontend

A329312 Length of the co-Lyndon factorization of the binary expansion of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A329326 Length of the co-Lyndon factorization of the reversed binary expansion of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A254040 Number T(n,k) of primitive (= aperiodic) n-bead necklaces with colored beads of exactly k different colors; triangle T(n,k), n >= 0, 0 <= k <= n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A281013 Tetrangle T(n,k,i) = i-th part of k-th prime composition of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A296373 Triangle T(n,k) = number of compositions of n whose factorization into Lyndon words (aperiodic necklaces) is of length k.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A296658 Length of the standard Lyndon word factorization of the first n terms of A000002.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A329314 Irregular triangle read by rows where row n gives the lengths of the components in the Lyndon factorization of the binary expansion of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A329325 Irregular triangle read by rows where row n gives the lengths of the components in the Lyndon factorization of the binary expansion of n with first digit removed.