A296372 -id:A296372 - cp's OEIS frontend

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

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

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

A334272 Number of sequences of length n that cover an initial interval of positive integers and are both a reversed necklace and a co-necklace.

Original entry on oeis.org

1, 1, 2, 4, 12, 43, 229, 1506, 12392, 120443

Offset: 0

Gus Wiseman, Apr 25 2020

A necklace is a finite sequence of positive integers that is lexicographically strictly less than or equal to any cyclic rotation. Co-necklace is defined similarly, except with strictly greater instead of strictly less.

			The a(1) = 1 through a(4) = 12 normal sequences:
  (1)  (1,1)  (1,1,1)  (1,1,1,1)
       (2,1)  (2,1,1)  (2,1,1,1)
              (2,2,1)  (2,1,2,1)
              (3,2,1)  (2,2,1,1)
                       (2,2,2,1)
                       (3,1,2,1)
                       (3,2,1,1)
                       (3,2,2,1)
                       (3,2,3,1)
                       (3,3,2,1)
                       (4,2,3,1)
                       (4,3,2,1)

Dominates A334270 (the aperiodic case).
Compositions of this type are counted by A334271.
These compositions are ranked by A334273 (standard) and A334274 (binary).
Binary (or reversed binary) necklaces are counted by A000031.
Normal sequences are counted by A000670.
Necklace compositions are counted by A008965.
Normal Lyndon words are counted by A060223.
Normal necklaces are counted by A019536.
All of the following pertain to compositions in standard order (A066099):
- Necklaces are A065609.
- Reversed necklaces are A333943.
- Co-necklaces are A333764.
- Reversed co-necklaces are A328595.
- Lyndon words are A275692.
- Co-Lyndon words are A326774.
- Reversed Lyndon words are A334265.
- Reversed co-Lyndon words are A328596.
- Reversed Lyndon co-Lyndon compositions are A334266.
- Aperiodic compositions are A328594.
Cf. A034691, A059966, A296372, A296975, A329138, A334269.

neckQ[q_]:=Length[q]==0||Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
coneckQ[q_]:=Length[q]==0||Array[OrderedQ[{RotateRight[q,#],q}]&,Length[q]-1,1,And];
allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
Table[Length[Select[Join@@Permutations/@allnorm[n],neckQ[Reverse[#]]&&coneckQ[#]&]],{n,0,8}]

A334270 Number of sequences of length n that cover an initial interval of positive integers and are both a reversed Lyndon word and a co-Lyndon word.

Original entry on oeis.org

1, 1, 1, 3, 10, 42, 224, 1505, 12380, 120439

Offset: 0

Gus Wiseman, Apr 24 2020

Also the number of sequences of length n that cover an initial interval of positive integers and are both a Lyndon word and a reversed co-Lyndon word.

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(4) = 10 normal sequences:
  (1)  (2,1)  (2,1,1)  (2,1,1,1)
              (2,2,1)  (2,2,1,1)
              (3,2,1)  (2,2,2,1)
                       (3,1,2,1)
                       (3,2,1,1)
                       (3,2,2,1)
                       (3,2,3,1)
                       (3,3,2,1)
                       (4,2,3,1)
                       (4,3,2,1)

These compositions are ranked by A334266 (standard) and A334267 (binary).
Compositions of this type are counted by A334269.
Necklace compositions of this type are counted by A334271.
Dominated by A334272 (the necklace version).
Normal sequences are counted by A000670.
Binary (or reversed binary) Lyndon words are counted by A001037.
Lyndon compositions are counted by A059966.
Normal Lyndon words are counted by A060223.
Normal sequences by length and Lyndon factorization length are A296372.
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.
Cf. A008965, A034691, A329324, A329398, A334273.

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];
allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
Table[Length[Select[Join@@Permutations/@allnorm[n],lynQ[Reverse[#]]&&colynQ[#]&]],{n,0,6}]

A334297 Length of the Lyndon factorization of the reversed n-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, 2, 1, 2, 1, 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, 2, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2

Offset: 0

Gus Wiseman, Apr 25 2020

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. 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 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 12345th composition is (1,7,1,1,3,1), with reverse (1,3,1,1,7,1), with Lyndon factorization ((1),(1,3),(1,1,7)), so a(12345) = 3.

The non-reversed version is A329312.
The version for binary indices is A329313 (also the "co-" version).
Positions of 1's are A334265 (reversed Lyndon words).
Binary Lyndon words are counted by A001037 and ranked by A102659.
Lyndon compositions are counted by A059966 and ranked by A275692.
Normal Lyndon sequences are counted by A060223 (row sums of A296372).
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.
- Co-Lyndon words are A326774.
- Reversed co-Lyndon words are A328596.
- Aperiodic compositions are A328594.
- Distinct rotations are counted by A333632.
- Lyndon factorizations are counted by A333940.
- Length of co-Lyndon factorization is A334029.
Cf. A027375, A211097, A211100, A328595, A329314, A329317.

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

A296976 List of normal Lyndon sequences ordered first by length and then reverse-lexicographically, where a finite sequence is normal if it spans an initial interval of positive integers.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Dec 22 2017

Row n is formed by A060223(n) sequences and has length A296975(n).

			Triangle of normal Lyndon sequences begins:
1,
12,
132,123,122,112,
1432,1423,1342,1332,1324,1323,1322,1243,1234,1233,1232,1223,1222,1213,1132,1123,1122,1112.

Cf. A000670, A019536, A060223, A095684, A185700, A281013, A294859, A296372, A296656, A296818, A296975-A296978.

LyndonQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
normseqs[n_]:=Union@@Permutations/@Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1];
Table[Select[Reverse@normseqs@n,LyndonQ],{n,5}]

A318808 Number of Lyndon permutations of a multiset whose multiplicities are the prime indices of n > 1.

Original entry on oeis.org

1, 1, 0, 1, 0, 1, 0, 2, 1, 1, 0, 3, 0, 1, 2, 6, 0, 6, 0, 4, 2, 1, 0, 12, 3, 1, 14, 5, 0, 10, 0, 24, 3, 1, 5, 30, 0, 1, 3, 20, 0, 15, 0, 6, 30, 1, 0, 60, 8, 20, 4, 7, 0, 90, 7, 30, 4, 1, 0, 60, 0, 1, 51, 120, 9, 21, 0, 8, 5, 35, 0, 180, 0, 1, 70, 9, 14, 28, 0, 120

Offset: 1

Gus Wiseman, Sep 04 2018

nonn

This multiset is generally not the same as the multiset of prime indices of n. For example, the prime indices of 12 are {1,1,2}, while a multiset whose multiplicities are {1,1,2} is {1,1,2,3}.
The Lyndon product of two or more finite sequences is defined 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.
a(1) = 1 by convention.

			The a(30) = 10 Lyndon permutations of {1,1,1,2,2,3}:
  (111223)
  (111232)
  (111322)
  (112123)
  (112132)
  (112213)
  (112312)
  (113122)
  (113212)
  (121213)

Andrew Howroyd, Table of n, a(n) for n = 1..1000
Wikipedia, Lyndon word

Cf. A000670, A005651, A008480, A019536, A056239, A060223, A112798, A296372, A298941, A305936, A318762, A318810.

nrmptn[n_]:=Join@@MapIndexed[Table[#2[[1]],{#1}]&,If[n==1,{},Flatten[Cases[FactorInteger[n]//Reverse,{p_,k_}:>Table[PrimePi[p],{k}]]]]];
LyndonQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
Table[Length[Select[Permutations[nrmptn[n]],LyndonQ]],{n,2,100}]

sig(n)={my(f=factor(n)); concat(vector(#f~, i, vector(f[i,2], j, primepi(f[i,1]))))}
count(sig)={my(n=vecsum(sig)); sumdiv(gcd(sig), d, moebius(d)*(n/d)!/prod(i=1, #sig, (sig[i]/d)!))/n}
a(n)={if(n==1, 1, count(sig(n)))} \\ Andrew Howroyd, Dec 08 2018

a(p) = 0 for prime p. - Andrew Howroyd, Dec 08 2018

A329359 Irregular triangle read by rows where row n gives the lengths of the factors in the co-Lyndon factorization of the binary expansion of n.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Nov 12 2019

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

			Triangle begins:
   1: (1)       21: (221)      41: (51)       61: (51)
   2: (2)       22: (23)       42: (222)      62: (6)
   3: (11)      23: (2111)     43: (2211)     63: (111111)
   4: (3)       24: (5)        44: (24)       64: (7)
   5: (21)      25: (41)       45: (231)      65: (61)
   6: (3)       26: (5)        46: (24)       66: (52)
   7: (111)     27: (311)      47: (21111)    67: (511)
   8: (4)       28: (5)        48: (6)        68: (43)
   9: (31)      29: (41)       49: (51)       69: (421)
  10: (22)      30: (5)        50: (6)        70: (43)
  11: (211)     31: (11111)    51: (411)      71: (4111)
  12: (4)       32: (6)        52: (6)        72: (7)
  13: (31)      33: (51)       53: (51)       73: (331)
  14: (4)       34: (42)       54: (33)       74: (322)
  15: (1111)    35: (411)      55: (3111)     75: (3211)
  16: (5)       36: (33)       56: (6)        76: (34)
  17: (41)      37: (321)      57: (51)       77: (331)
  18: (32)      38: (33)       58: (6)        78: (34)
  19: (311)     39: (3111)     59: (411)      79: (31111)
  20: (5)       40: (6)        60: (6)        80: (7)
For example, 45 has binary expansion (101101), with co-Lyndon factorization (10)(110)(1), so row n = 45 is (2,3,1).

Row lengths are A329312.
Row sums are A070939.
Positions of rows of length 1 are A275692.
The non-"co" version is A329314.
Binary co-Lyndon words are counted by A001037 and ranked by A329318.
Cf. A059966, A211097, A211100, A328596, A296372, A329313, A329315, A329325, A329357.

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[If[n==0,{},IntegerDigits[n,2]]],{n,30}]

A296977 List of normal Lyndon sequences ordered first by length and then lexicographically, where a finite sequence is normal if it spans an initial interval of positive integers.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Dec 22 2017

Row n is formed by A060223(n) sequences and has length A296975(n).

			Triangle of normal Lyndon sequences begins:
1,
12,
112,122,123,132,
1112,1122,1123,1132,1213,1222,1223,1232,1233,1234,1243,1322,1323,1324,1332,1342,1423,1432.

Cf. A000670, A019536, A060223, A095684, A185700, A281013, A294859, A296372, A296656, A296818, A296975, A296976.

LyndonQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
normseqs[n_]:=Union@@Permutations/@Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1];
Table[Select[normseqs[n],LyndonQ],{n,5}]

A296659 Length of the final word in the standard Lyndon word factorization of the first n terms of A000002.

Original entry on oeis.org

1, 2, 3, 1, 1, 3, 1, 5, 6, 1, 8, 9, 1, 1, 3, 1, 1, 3, 7, 1, 9, 1, 1, 3, 1, 14, 15, 1, 1, 3, 1, 1, 3, 1, 8, 9, 1, 11, 12, 1, 1, 3, 1, 17, 18, 1, 20, 1, 1, 3, 1, 1, 3, 27, 1, 29, 30, 1, 1, 3, 1, 35, 36, 1, 38, 39, 1, 1, 3, 1, 1, 3, 1, 8, 9, 1, 11, 1, 1, 3, 15, 1

Offset: 1

Gus Wiseman, Dec 18 2017

nonn

			The sequence of final words begins: 1, 12, 122, 1, 1, 112, 1, 11212, 112122, 1, 11212212, 112122122, 1, 1, 112, 1, 1, 112, 1121122, 1, 112112212, 1, 1, 112, 1, 11211221211212, 112112212112122, 1, 1, 112.

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.

Cf. A000002, A027375, A088568, A102659, A228369, A281013, A288605, A296372, A296657, A296658.

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[Last[qit[Nest[kolagrow,1,n]]]],{n,150}]

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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

A334272 Number of sequences of length n that cover an initial interval of positive integers and are both a reversed necklace and a co-necklace.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A334270 Number of sequences of length n that cover an initial interval of positive integers and are both a reversed Lyndon word and a co-Lyndon word.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A334297 Length of the Lyndon factorization of the reversed n-th composition in standard order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A296976 List of normal Lyndon sequences ordered first by length and then reverse-lexicographically, where a finite sequence is normal if it spans an initial interval of positive integers.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A318808 Number of Lyndon permutations of a multiset whose multiplicities are the prime indices of n > 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A329359 Irregular triangle read by rows where row n gives the lengths of the factors in the co-Lyndon factorization of the binary expansion of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A296977 List of normal Lyndon sequences ordered first by length and then lexicographically, where a finite sequence is normal if it spans an initial interval of positive integers.

Views

Author

Keywords