A329399 -id:A329399 - cp's OEIS frontend

A329398 Number of compositions of n with uniform Lyndon factorization and uniform co-Lyndon factorization.

1, 2, 4, 7, 12, 18, 28, 40, 57, 80, 110, 148, 200, 266, 348, 457, 592, 764, 978, 1248, 1580, 2000, 2508, 3142, 3913

Offset: 1

Gus Wiseman, Nov 13 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).
Similarly, the co-Lyndon product is the lexicographically minimal sequence obtainable by shuffling the sequences together, and a co-Lyndon word is a finite sequence that is prime with respect to the co-Lyndon product, or, equivalently, a finite sequence that is lexicographically strictly greater than all of its cyclic rotations. For example, (1001) has sorted co-Lyndon factorization (1)(100).
A sequence of words is uniform if they all have the same length.
Conjecture: Also the number of compositions of n that are either weakly increasing or weakly decreasing. Hence a(n) = 2 * A000041(n) - A000005(n). - Gus Wiseman, Mar 05 2020

			The a(1) = 1 through a(6) = 18 compositions:
  (1)  (2)   (3)    (4)     (5)      (6)
       (11)  (12)   (13)    (14)     (15)
             (21)   (22)    (23)     (24)
             (111)  (31)    (32)     (33)
                    (112)   (41)     (42)
                    (211)   (113)    (51)
                    (1111)  (122)    (114)
                            (221)    (123)
                            (311)    (222)
                            (1112)   (321)
                            (2111)   (411)
                            (11111)  (1113)
                                     (1122)
                                     (2211)
                                     (3111)
                                     (11112)
                                     (21111)
                                     (111111)

Lyndon and co-Lyndon compositions are (both) counted by A059966.
Lyndon compositions that are not weakly increasing are A329141.
Lyndon compositions whose reverse is not co-Lyndon are A329324.
Cf. A000740, A001037, A001523, A008965, A059204, A060223, A211100, A328596, A329312, A329318, A329396, A329397, A329399, A332578, A332669, A332834.

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,#]]&]]]];
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[Select[Join@@Permutations/@IntegerPartitions[n],SameQ@@Length/@lynfac[#]&&SameQ@@Length/@colynfac[#]&]],{n,10}]

a(19)-a(25) from Robert Price, Jun 20 2021

A329395 Numbers whose binary expansion without the most significant (first) digit has Lyndon and co-Lyndon factorizations of equal lengths.

Original entry on oeis.org

1, 2, 3, 4, 7, 8, 10, 13, 15, 16, 22, 25, 31, 32, 36, 42, 46, 49, 53, 59, 63, 64, 76, 82, 94, 97, 109, 115, 127, 128, 136, 148, 156, 162, 166, 169, 170, 172, 181, 182, 190, 193, 201, 202, 211, 213, 214, 217, 221, 227, 235, 247, 255, 256, 280, 292, 306, 308

Offset: 1

Gus Wiseman, Nov 13 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).
Similarly, the co-Lyndon product is the lexicographically minimal sequence obtainable by shuffling the sequences together, and a co-Lyndon word is a finite sequence that is prime with respect to the co-Lyndon product, or, equivalently, a finite sequence that is lexicographically strictly greater than all of its cyclic rotations. For example, (1001) has sorted co-Lyndon factorization (1)(100).
Conjecture: also numbers k such that the k-th composition in standard order (A066099) is a palindrome, cf. A025065, A242414, A317085, A317086, A317087, A335373. - Gus Wiseman, Jun 06 2020

			The sequence of terms together with their trimmed binary expansions and their co-Lyndon and Lyndon factorizations begins:
   1:      () =               0 = 0
   2:     (0) =             (0) = (0)
   3:     (1) =             (1) = (1)
   4:    (00) =          (0)(0) = (0)(0)
   7:    (11) =          (1)(1) = (1)(1)
   8:   (000) =       (0)(0)(0) = (0)(0)(0)
  10:   (010) =         (0)(10) = (01)(0)
  13:   (101) =         (10)(1) = (1)(01)
  15:   (111) =       (1)(1)(1) = (1)(1)(1)
  16:  (0000) =    (0)(0)(0)(0) = (0)(0)(0)(0)
  22:  (0110) =        (0)(110) = (011)(0)
  25:  (1001) =        (100)(1) = (1)(001)
  31:  (1111) =    (1)(1)(1)(1) = (1)(1)(1)(1)
  32: (00000) = (0)(0)(0)(0)(0) = (0)(0)(0)(0)(0)
  36: (00100) =     (0)(0)(100) = (001)(0)(0)
  42: (01010) =     (0)(10)(10) = (01)(01)(0)
  46: (01110) =       (0)(1110) = (0111)(0)
  49: (10001) =       (1000)(1) = (1)(0001)
  53: (10101) =     (10)(10)(1) = (1)(01)(01)
  59: (11011) =     (110)(1)(1) = (1)(1)(011)
  63: (11111) = (1)(1)(1)(1)(1) = (1)(1)(1)(1)(1)

Lyndon and co-Lyndon compositions are (both) counted by A059966.
Numbers whose reversed binary expansion is Lyndon are A328596.
Numbers whose binary expansion is co-Lyndon are A275692.
Cf. A001037, A060223, A102659, A211100, A329131, A329312, A329313, A329318, A329326, A329394, A329398.
Cf. A329358, A329399, A329400, A329401.

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

A348268 Mapping between Lyndon factorization and prime factorization.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 11, 10, 9, 12, 13, 14, 17, 16, 19, 22, 15, 20, 29, 18, 21, 24, 23, 26, 37, 28, 31, 34, 41, 32, 43, 38, 33, 44, 25, 30, 35, 40, 53, 58, 27, 36, 67, 42, 51, 48, 47, 46, 39, 52, 61, 74, 49, 56, 59, 62, 73, 68, 71, 82, 79, 64, 83, 86, 57, 76, 55, 66, 77

Offset: 0

Thomas Scheuerle, Oct 09 2021

A Lyndon word is a finite sequence that is lexicographically strictly less than all of its cyclic rotations.
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).
We use Lyndon factorization on the reversed order binary expansion of n, then we use the mapping from Lyndon words (A328596(k) reversed binary expansion) to positive integers that have no divisors other than 1 and itself (A008578(k+1)). a(n) has factors in A008578 as the binary expansion of n has in A328596.

			We map Lyndon-words to positive integers that have no divisors other than 1 and itself: [] -> 1, 1 -> 2, 01 -> 3, 001 -> 5, 011 -> 7, 0001 -> 11, ...
9 is in reversed order binary: 1001, has the factors (1)(001) -> a(9) = 2*5 = 10.
10 is in reversed order binary: 0101, has the factors (01)(01) -> a(10) = 3*3 = 9.

Thomas Scheuerle, Table of n, a(n) for n = 0..5000
Thomas Scheuerle, Program (MATLAB)
Index entries for sequences that are permutations of the natural numbers

Cf. A329313, A328596, A008578, A329399, A000961, A328595, A328595.

MATLAB
```
% See Scheuerle link.
```

a(Lyndonproduct(n,m)) = a(n)*a(m).
a(1 + 2*n)/a(n) = 2.
all a(A329399(n)) are in A000961 (powers of primes).
all a(A328595(n)) (reversed binary expansion is a necklace) are in A329131 (prime signature is a Lyndon word).

A329397 Number of compositions of n whose Lyndon factorization is uniform.

Original entry on oeis.org

1, 2, 4, 7, 12, 20, 33, 55, 92, 156, 267, 466, 822, 1473, 2668, 4886, 9021, 16786, 31413, 59101, 111654, 211722, 402697, 768025, 1468170, 2812471, 5397602, 10376418, 19978238, 38519537, 74365161, 143742338, 278156642, 538831403, 1044830113, 2027879831

Offset: 1

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

A sequence of words is uniform if they all have the same length.

			The a(1) = 1 through a(6) = 20 Lyndon factorizations:
  (1)  (2)     (3)        (4)           (5)              (6)
       (1)(1)  (12)       (13)          (14)             (15)
               (2)(1)     (112)         (23)             (24)
               (1)(1)(1)  (2)(2)        (113)            (114)
                          (3)(1)        (122)            (123)
                          (2)(1)(1)     (1112)           (132)
                          (1)(1)(1)(1)  (3)(2)           (1113)
                                        (4)(1)           (1122)
                                        (2)(2)(1)        (3)(3)
                                        (3)(1)(1)        (4)(2)
                                        (2)(1)(1)(1)     (5)(1)
                                        (1)(1)(1)(1)(1)  (11112)
                                                         (12)(12)
                                                         (2)(2)(2)
                                                         (3)(2)(1)
                                                         (4)(1)(1)
                                                         (2)(2)(1)(1)
                                                         (3)(1)(1)(1)
                                                         (2)(1)(1)(1)(1)
                                                         (1)(1)(1)(1)(1)(1)

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

Lyndon and co-Lyndon compositions are (both) counted by A059966.
Lyndon compositions that are not weakly increasing are A329141.
Lyndon compositions whose reverse is not co-Lyndon are A329324.
Cf. A000740, A001037, A008965, A060223, A102659, A211100, A275692, A328596, A329312, A329318, A329395, A329396, A329398, A329399.

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,#]]&]]]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],SameQ@@Length/@lynfac[#]&]],{n,10}]

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
B(n,k) = {sumdiv(n, d, moebius(d)/(1-x^d)^(n/d) + O(x*x^k))/n}
seq(n) = {sum(d=1, n-1, my(v=Vec(B(d,n-d),-n)); EulerT(v))} \\ Andrew Howroyd, Feb 03 2022

G.f.: Sum_{r>=1} (exp(Sum_{k>=1} B(r, x^k)/k) - 1) where B(r, x) = (Sum_{d|r} mu(d)/(1 - x^d)^(r/d))*x^r/r. - Andrew Howroyd, Feb 03 2022

a(19)-a(25) from Robert Price, Jun 20 2021

Terms a(26) and beyond from Andrew Howroyd, Feb 03 2022

cp's OEIS Frontend

A329398 Number of compositions of n with uniform Lyndon factorization and uniform co-Lyndon factorization.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A329395 Numbers whose binary expansion without the most significant (first) digit has Lyndon and co-Lyndon factorizations of equal lengths.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A348268 Mapping between Lyndon factorization and prime factorization.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

MATLAB

Formula

A329397 Number of compositions of n whose Lyndon factorization is uniform.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions