cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Previous Showing 11-20 of 47 results. Next

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

Views

Author

Gus Wiseman, Jan 12 2017

Keywords

Comments

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

Examples

			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.

Crossrefs

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.

Programs

  • Mathematica
    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 *)

Formula

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

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

Views

Author

Gus Wiseman, Dec 18 2017

Keywords

Examples

			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

Links

Crossrefs

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.

Programs

  • Mathematica
    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

Views

Author

Gus Wiseman, Nov 11 2019

Keywords

Comments

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

Examples

			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)

Crossrefs

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.

Programs

  • Mathematica
    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

Views

Author

Gus Wiseman, Nov 11 2019

Keywords

Comments

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.

Examples

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

Crossrefs

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

Programs

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

A329324 Number of Lyndon compositions of n whose reverse is not a co-Lyndon composition.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 2, 7, 16, 37, 76, 166, 328, 669, 1326, 2626, 5138, 10104, 19680, 38442, 74822, 145715, 283424, 551721, 1073224
Offset: 1

Views

Author

Gus Wiseman, Nov 11 2019

Keywords

Comments

A Lyndon composition of n is a finite sequence summing to n that is lexicographically strictly less than all of its cyclic rotations. A co-Lyndon composition of n is a finite sequence summing to n that is lexicographically strictly greater than all of its cyclic rotations.

Examples

			The a(6) = 1 through a(9) = 16 compositions:
  (132)  (142)   (143)    (153)
         (1132)  (152)    (162)
                 (1142)   (243)
                 (1232)   (1143)
                 (1322)   (1152)
                 (11132)  (1242)
                 (11312)  (1332)
                          (1422)
                          (11142)
                          (11232)
                          (11322)
                          (11412)
                          (12132)
                          (111132)
                          (111312)
                          (112212)

Crossrefs

Lyndon and co-Lyndon compositions are counted by A059966.
Numbers whose reversed binary expansion is Lyndon are A328596.
Numbers whose binary expansion is co-Lyndon are A275692.
Lyndon compositions that are not weakly increasing are A329141.
Cf. A000740, A001037, A008965, A060223, A102659, A211100, A329131, A329312, A329313, A329318, A329326.

Programs

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

Extensions

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

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

Views

Author

Gus Wiseman, Nov 11 2019

Keywords

Comments

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

Examples

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

Crossrefs

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.

Programs

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

A294859 Triangle whose n-th row is the concatenated sequence of all Lyndon compositions of n in lexicographic order.

Original entry on oeis.org

1, 2, 1, 2, 3, 1, 1, 2, 1, 3, 4, 1, 1, 1, 2, 1, 1, 3, 1, 2, 2, 1, 4, 2, 3, 5, 1, 1, 1, 1, 2, 1, 1, 1, 3, 1, 1, 2, 2, 1, 1, 4, 1, 2, 3, 1, 3, 2, 1, 5, 2, 4, 6, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 3, 1, 1, 1, 2, 2, 1, 1, 1, 4, 1, 1, 2, 1, 2, 1, 1, 2, 3, 1, 1, 3, 2, 1
Offset: 1

Views

Author

Gus Wiseman, Dec 18 2017

Keywords

Examples

			Triangle of Lyndon compositions begins:
(1),
(2),
(12),(3),
(112),(13),(4),
(1112),(113),(122),(14),(23),(5),
(11112),(1113),(1122),(114),(123),(132),(15),(24),(6),
(111112),(11113),(11122),(1114),(11212),(1123),(1132),(115),(1213),(1222),(124),(133),(142),(16),(223),(25),(34),(7).

Crossrefs

Cf. A000740, A001037, A001045, A008965, A059966, A060223, A066099, A101211, A102659, A124734, A185700, A228369, A281013, A296302, A296373, A296656.

Programs

  • Mathematica
    LyndonQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
Table[Sort[Select[Join@@Permutations/@IntegerPartitions[n],LyndonQ],OrderedQ[PadRight[{#1,#2}]]&],{n,7}]

Formula

Row n is a concatenation of A059966(n) Lyndon words with total length A000740(n).

A213969 List of primitive words over the alphabet {1,2}.

Original entry on oeis.org

1, 2, 12, 21, 112, 121, 122, 211, 212, 221, 1112, 1121, 1122, 1211, 1221, 1222, 2111, 2112, 2122, 2211, 2212, 2221, 11112, 11121, 11122, 11211, 11212, 11221, 11222, 12111, 12112, 12121, 12122, 12211, 12212, 12221, 12222, 21111, 21112, 21121, 21122, 21211, 21212, 21221, 21222, 22111, 22112, 22121, 22122, 22211, 22212, 22221
Offset: 1

Views

Author

N. J. A. Sloane, Jun 30 2012

Keywords

Comments

A word w is primitive if it cannot be written as u^k with k>1; otherwise it is imprimitive.
The {0,1} version of this sequence is
0, 1, 01, 10, 001, 010, 011, 100, 101, 110, 0001, 0010, 0011, 0100, 0110, 0111, 1000, 1001, 1011, 1100, 1101, 1110, 00001, 00010, 00011, 00100, 00101, 00110, 00111, 01000, 01001, 01010, 01011, 01100, 01101, 01110, 01111, 10000, 10001, 10010, 10011, 10100, 10101, 10110, 10111, 11000, 11001, 11010, 11011, 11100, 11101, 11110, ...,
but this cannot be included as a sequence in the OEIS since it contains nonzero "numbers" beginning with 0.
Lyndon words on {1,2}, A102659, are the numbers in this sequence which are also not larger than any of their rotations, i.e., in A239016. - M. F. Hasler, Mar 08 2014

References

  • A. de Luca and S. Varricchio, Finiteness and Regularity in Semigroups and Formal Languages, Monographs in Theoretical Computer Science, Springer-Verlag, Berlin, 1999. See p. 10.

Links

Crossrefs

Cf. A213969-A213974.

Programs

  • Maple
    P:= proc(d) local m,A;
    A:= map(t -> (10^d-1)/9 + add(10^s, s = t), combinat:-powerset([$0..d-1]));
    for m in numtheory:-divisors(d) minus {d} do
      A:= remove(t -> t = (t mod 10^m)*(10^d-1)/(10^m-1), A);
    od;
    op(sort(A));
end proc:
seq(P(d),d=1..6); # Robert Israel, Mar 24 2017
  • Mathematica
    j[w_, k_] := FromDigits /@ (Flatten[Table[#, {k}]] & /@ w); L[n_] := Complement[ FromDigits /@ Tuples[{1, 2}, n], Union[ Flatten[( j[Tuples[{1, 2}, #1], n/#1] &) /@ Most[ Divisors[n]]]]]; Flatten@ Array[L, 5] (* Giovanni Resta, Mar 24 2017 *)
  • PARI
    is_A213969(n)={fordiv(#n=digits(n),L,L<#n&&n==concat(Col(vector(#n/L,i,1)~*vecextract(n,2^L-1))~)&&return);!setminus(Set(n),[1,2])}
for(n=1,5,p=vector(n,i,10^(n-i))~;forvec(d=vector(n,i,[1,2]),is_A213969(m=d*p)&&print1(m","))) \\ M. F. Hasler, Mar 08 2014

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

Views

Author

Gus Wiseman, Nov 11 2019

Keywords

Comments

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

Examples

			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.

Crossrefs

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.

Programs

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

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

Views

Author

Gus Wiseman, Apr 14 2020

Keywords

Comments

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.

Examples

			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.

Crossrefs

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.

Programs

  • Mathematica
    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}]
Previous Showing 11-20 of 47 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.