A102659 -id:A102659 - cp's OEIS frontend

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.

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

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

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Nov 12 2019

nonn

The co-Lyndon product of two or more finite sequences is defined to be the lexicographically minimal sequence obtainable by shuffling the sequences together. For example, the co-Lyndon product of (231) and (213) is (212313), the product of (221) and (213) is (212213), and the product of (122) and (2121) is (1212122). A co-Lyndon word is a finite sequence that is prime with respect to the co-Lyndon product. Equivalently, a co-Lyndon word is a finite sequence that is lexicographically strictly greater than all of its cyclic rotations. Every finite sequence has a unique (orderless) factorization into co-Lyndon words, and if these factors are arranged in a certain order, their concatenation is equal to their co-Lyndon product. For example, (1001) has sorted co-Lyndon factorization (1)(100).

			The co-Lyndon factorizations of the initial terms of A000002:
                      () = 0
                     (1) = (1)
                    (12) = (1)(2)
                   (122) = (1)(2)(2)
                  (1221) = (1)(221)
                 (12211) = (1)(2211)
                (122112) = (1)(2211)(2)
               (1221121) = (1)(221121)
              (12211212) = (1)(221121)(2)
             (122112122) = (1)(221121)(2)(2)
            (1221121221) = (1)(221121)(221)
           (12211212212) = (1)(221121)(221)(2)
          (122112122122) = (1)(221121)(221)(2)(2)
         (1221121221221) = (1)(221121)(221)(221)
        (12211212212211) = (1)(221121)(2212211)
       (122112122122112) = (1)(221121)(2212211)(2)
      (1221121221221121) = (1)(221121)(221221121)
     (12211212212211211) = (1)(221121)(2212211211)
    (122112122122112112) = (1)(221121)(2212211211)(2)
   (1221121221221121122) = (1)(221121)(2212211211)(2)(2)
  (12211212212211211221) = (1)(221121)(2212211211)(221)

The non-"co" version is A296658.

Cf. A000002, A001037, A060223, A088568, A102659, A275692, A329312, A329315, A329317, A329318.

kolagrow[q_]:=If[Length[q]<2,Take[{1,2},Length[q]+1],Append[q,Switch[{q[[Length[Split[q]]]],q[[-2]],Last[q]},{1,1,1},0,{1,1,2},1,{1,2,1},2,{1,2,2},0,{2,1,1},2,{2,1,2},2,{2,2,1},1,{2,2,2},1]]]
kol[n_Integer]:=If[n==0,{},Nest[kolagrow,{1},n-1]];
colynQ[q_]:=Array[Union[{RotateRight[q,#],q}]=={RotateRight[q,#],q}&,Length[q]-1,1,And];
colynfac[q_]:=If[Length[q]==0,{},Function[i,Prepend[colynfac[Drop[q,i]],Take[q,i]]]@Last[Select[Range[Length[q]],colynQ[Take[q,#]]&]]];
Table[Length[colynfac[kol[n]]],{n,0,100}]

A102660 List of Lyndon words on {1,2,3} sorted first by length and then lexicographically.

Original entry on oeis.org

1, 2, 3, 12, 13, 23, 112, 113, 122, 123, 132, 133, 223, 233, 1112, 1113, 1122, 1123, 1132, 1133, 1213, 1222, 1223, 1232, 1233, 1322, 1323, 1332, 1333, 2223, 2233, 2333, 11112, 11113, 11122, 11123, 11132, 11133, 11212, 11213, 11222, 11223, 11232

Offset: 1

N. J. A. Sloane, Feb 03 2005

A Lyndon word is primitive (not a power of another word) and is earlier in lexicographic order than any of its cyclic shifts.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
F. Bassino, J. Clement and C. Nicaud, The standard factorization of Lyndon words: an average point of view, Discrete Math. 290 (2005), 1-25.
Reinhard Zumkeller, Haskell programs for some sequences concerning Lyndon words
Wikipedia, Lyndon word
Index entries for sequences related to Lyndon words

Cf. A074650, A001037, A102659, A210584, A210585.

Cf. A027376.

Haskell
```
cf. link.
```

is_A102660(n)=is_A239016(n)&&is_A239017(n)
for(n=1, 5, p=vector(n, i, 10^(n-i))~; forvec(d=vector(n, i, [1, 3]), is_A102660(m=d*p)&&print1(m", "))) \\ M. F. Hasler, Mar 09 2014

Equals A239016 intersect A239017. - M. F. Hasler, Mar 09 2014

More terms from John W. Layman, Jan 24 2006

Definition improved by Reinhard Zumkeller, Mar 23 2012

A239016 Numbers not larger than any rotation of their digits.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 22, 23, 24, 25, 26, 27, 28, 29, 33, 34, 35, 36, 37, 38, 39, 44, 45, 46, 47, 48, 49, 55, 56, 57, 58, 59, 66, 67, 68, 69, 77, 78, 79, 88, 89, 99, 111, 112, 113, 114, 115, 116, 117, 118, 119, 122, 123, 124, 125, 126, 127, 128, 129, 132

Offset: 1

M. F. Hasler, Mar 08 2014

The numbers with nonincreasing digits, A009994, form a subsequence which first differs at a(73)=132 (not in A009994) from this one.
This sequence is a subsequence of A072544: numbers whose smallest decimal digit is also the initial digit. A072544(65)=121 is the first such number not in this sequence.
This criterion involving "rotation" is part of the characterization of Lyndon words, see e.g. A102659, A102660, A210584, A210585. All of these are subsequences of this sequence. For example, A102659 = A213969 intersect A239016.

			The number 10 is excluded from this sequence because its "rotation" 01 is smaller than the number itself.
The same is the case for any number whose first digit is not the smallest one: rotating a smaller digit to the front will always yield a smaller number, independently of the other digits. For this reason, all terms must be in A072544.
a(73)=132 is in the sequence because the nontrivial rotations of its digits are 321 and 213, both larger than 132.

is_A239016(n)=vecsort(d=digits(n))==d||!for(i=1,#d-1,n>[1,10^(#d-i)]*divrem(n,10^i)&&return)

def ok(n):
    s = str(n)
    if "".join(sorted(s)) == s: return True
    return all(n <= int(s[i:] + s[:i]) for i in range(1, len(s)))
print(list(filter(ok, range(133)))) # Michael S. Branicky, Aug 21 2021

A211099 Largest (i.e., leftmost) Lyndon word in Lyndon factorization of binary vectors of lengths 1, 2, 3, ... (written using 1's and 2's rather than 0's and 1's, since numbers > 0 in the OEIS cannot begin with 0).

Original entry on oeis.org

1, 2, 1, 12, 2, 2, 1, 112, 12, 122, 2, 2, 2, 2, 1, 1112, 112, 1122, 12, 12, 122, 1222, 2, 2, 2, 2, 2, 2, 2, 2, 1, 11112, 1112, 11122, 112, 11212, 1122, 11222, 12, 12, 12, 12122, 122, 122, 1222, 12222, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 111112, 11112, 111122, 1112, 111212, 11122, 111222, 112, 112, 11212, 112122, 1122, 112212, 11222, 112222, 12

Offset: 1

N. J. A. Sloane, Apr 01 2012

nonn

Any binary word has a unique factorization as a product of nonincreasing Lyndon words (see Lothaire). Here we look at the Lyndon factorizations of the binary vectors 0,1, 00,01,10,11, 000,001,010,011,100,101,110,111, 0000,...
See A211097, A211099, A211100 for further information, including Maple code.
The smallest (or rightmost) factors are given by A211095 and A211096, offset by 2.

			Here are the Lyndon factorizations of the first few binary vectors:
.0.
.1.
.0.0.
.01.
.1.0.
.1.1.
.0.0.0.
.001.
.01.0.
.011.
.1.0.0.
.1.01.
.1.1.0.
.1.1.1.
.0.0.0.0.
...
The real sequence (written with 0's and 1's rather than 1's and 2's) is:
0, 1, 0, 01, 1, 1, 0, 001, 01, 011, 1, 1, 1, 1, 0, 0001, 001, 0011, 01, 01, 011, 0111, 1, 1, 1, 1, 1, 1, 1, 1, 0, 00001, 0001, 00011, 001, 00101, 0011, 00111, 01, 01, 01, 01011, 011, 011, 0111, 01111, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 000001, 00001, ...

M. Lothaire, Combinatorics on Words, Addison-Wesley, Reading, MA, 1983. See Theorem 5.1.5, p. 67.
G. Melançon, Factorizing infinite words using Maple, MapleTech Journal, vol. 4, no. 1, 1997, pp. 34-42

N. J. A. Sloane, Maple programs for A211097 etc.

Cf. A001037 (number of Lyndon words of length m); A102659 (list thereof), A211100.

Cf. A211095-A211099.

A239018 Non-primitive words on {1,2,3}.

Original entry on oeis.org

11, 22, 33, 111, 222, 333, 1111, 1212, 1313, 2121, 2222, 2323, 3131, 3232, 3333, 11111, 22222, 33333, 111111, 112112, 113113, 121121, 121212, 122122, 123123, 131131, 131313, 132132, 133133, 211211, 212121, 212212, 213213, 221221, 222222, 223223, 231231, 232232, 232323, 233233, 311311, 312312, 313131, 313313

Offset: 1

M. F. Hasler, Mar 08 2014

nonn

A word is non-primitive if it is a nontrivial power (i.e., repetition) of a subword. Therefore, for a prime number of digits, only the repdigit numbers are primitive. For words with 6 letters, there is also 112^2,113^2,121^2,12^3,... where w^n means n concatenations of w.
Lyndon words on {1,2,3}, A102660, are the terms in A007932 which are primitive (i.e., in the complement A239017 of this sequence) and not larger than any of their rotation, i.e., in A239016.
This is the complement of A239017 in A007932.
This is for {1,2,3} what A213972 is for {1,2} (and A213973 for {1,3}, A213974 for {2,3}).

Michael S. Branicky, Table of n, a(n) for n = 1..10239 (all terms with <= 16 digits)

Cf. A102659, A213969 - A213974.

Cf. A007932, A239017.

for(n=1,7,p=vector(n,i,10^(n-i))~;forvec(d=vector(n,i,[1,3]),is_A239017(m=d*p)||print1(m",")))

from sympy import divisors
from itertools import product
def agentod(maxd):
    for d in range(2, maxd+1):
        divs, alld = divisors(d)[:-1], set()
        for div in divs:
            for t in product("123", repeat=div):
                alld.add(int("".join(t*(d//div))))
        yield from sorted(alld)
print([an for an in agentod(6)]) # Michael S. Branicky, Nov 22 2021

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

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Dec 18 2017

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

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

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[{#2,#1}]]&],{n,7}]

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

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

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Nov 12 2019

nonn

First differs from A329357 in having 77 and lacking 83.

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

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

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

lynQ[q_]:=Array[Union[{q,RotateRight[q,#]}]=={q,RotateRight[q,#]}&,Length[q]-1,1,And];
lynfac[q_]:=If[Length[q]==0,{},Function[i,Prepend[lynfac[Drop[q,i]],Take[q,i]]][Last[Select[Range[Length[q]],lynQ[Take[q,#1]]&]]]];
Select[Range[100],Length[lynfac[IntegerDigits[#,2]]]==2&]

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

A210584 List of Lyndon words on {1,2,3,4} sorted first by length and then lexicographically.

Original entry on oeis.org

1, 2, 3, 4, 12, 13, 14, 23, 24, 34, 112, 113, 114, 122, 123, 124, 132, 133, 134, 142, 143, 144, 223, 224, 233, 234, 243, 244, 334, 344, 1112, 1113, 1114, 1122, 1123, 1124, 1132, 1133, 1134, 1142, 1143, 1144, 1213, 1214, 1222, 1223, 1224, 1232, 1233, 1234

Offset: 1

Reinhard Zumkeller, Mar 23 2012

nonn

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Reinhard Zumkeller, Haskell programs for some sequences concerning Lyndon words
Wikipedia, Lyndon word
Index entries for sequences related to Lyndon words

Cf. A102659, A102660, A210585.

Haskell
```
cf. link.
```

A210585 List of Lyndon words on {1,...,8} sorted first by length and then lexicographically.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 12, 13, 14, 15, 16, 17, 18, 23, 24, 25, 26, 27, 28, 34, 35, 36, 37, 38, 45, 46, 47, 48, 56, 57, 58, 67, 68, 78, 112, 113, 114, 115, 116, 117, 118, 122, 123, 124, 125, 126, 127, 128, 132, 133, 134, 135, 136, 137, 138, 142, 143, 144

Offset: 1

Reinhard Zumkeller, Mar 23 2012

nonn

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Reinhard Zumkeller, Haskell programs for some sequences concerning Lyndon words
Wikipedia, Lyndon word
Index entries for sequences related to Lyndon words

Cf. A102659, A102660, A210584.

Haskell
```
cf. link.
```

cp's OEIS Frontend

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

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A102660 List of Lyndon words on {1,2,3} sorted first by length and then lexicographically.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

PARI

Formula

Extensions

A239016 Numbers not larger than any rotation of their digits.

Views

Author

Keywords

Comments

Examples

Programs

PARI

Python

A211099 Largest (i.e., leftmost) Lyndon word in Lyndon factorization of binary vectors of lengths 1, 2, 3, ... (written using 1's and 2's rather than 0's and 1's, since numbers > 0 in the OEIS cannot begin with 0).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A239018 Non-primitive words on {1,2,3}.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Python

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

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A210584 List of Lyndon words on {1,2,3,4} sorted first by length and then lexicographically.

Views