A213969 -id:A213969 - cp's OEIS frontend

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

1, 2, 12, 112, 122, 1112, 1122, 1222, 11112, 11122, 11212, 11222, 12122, 12222, 111112, 111122, 111212, 111222, 112122, 112212, 112222, 121222, 122222, 1111112, 1111122, 1111212, 1111222, 1112112, 1112122, 1112212, 1112222, 1121122

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.
Émilie Charlier, Manon Philibert, Manon Stipulanti, Nyldon words, arXiv:1804.09735 [math.CO], 2018. See Table 1.
A. M. Uludag, A. Zeytin and M. Durmus, Binary Quadratic Forms as Dessins, 2012. - From _N. J. A. Sloane_, Dec 31 2012
Wikipedia, Lyndon word
Reinhard Zumkeller, Haskell programs for some sequences concerning Lyndon words
Index entries for sequences related to Lyndon words

Cf. A001037, A074650, A102660, A210584, A210585.
The "co" version is A329318.
A triangular version is A296657.
A sequence listing all Lyndon compositions is A294859.
Numbers whose binary expansion is Lyndon are A328596.
Length of the Lyndon factorization of the binary expansion is A211100.
Cf. A059966, A060223, A275692, A281013, A296373, A329131, A329313.

Haskell
```
cf. link.
```

lynQ[q_]:=Array[Union[{q,RotateRight[q,#]}]=={q,RotateRight[q,#]}&,Length[q]-1,1,And];
Join@@Table[FromDigits/@Select[Tuples[{1,2},n],lynQ],{n,5}] (* Gus Wiseman, Nov 14 2019 *)

is_A102659(n)={ vecsort(d=digits(n))!=d&&for(i=1,#d-1, n>[1,10^(#d-i)]*divrem(n,10^i)&&return); fordiv(#d,L,L<#d && d==concat(Col(vector(#d/L,i,1)~*vecextract(d,2^L-1))~)&&return); !setminus(Set(d),[1,2])} \\ The last check is the least expensive one, but not useful if we test only numbers with digits {1,2}.
for(n=1,6,p=vector(n,i,10^(n-i))~;forvec(d=vector(n,i,[1,2]),is_A102659(m=d*p)&&print1(m","))) \\ One could use is_A102660 instead of is_A102659 here. - M. F. Hasler, Mar 08 2014

A102659 = A102660 intersect A007931 = A213969 intersect A239016. - M. F. Hasler, Mar 10 2014

More terms from Franklin T. Adams-Watters, Dec 14 2006

Definition improved by Reinhard Zumkeller, Mar 23 2012

A213974 List of imprimitive words over the alphabet {2,3}.

Original entry on oeis.org

22, 33, 222, 333, 2222, 2323, 3232, 3333, 22222, 33333, 222222, 223223, 232232, 232323, 233233, 322322, 323232, 323323, 332332, 333333, 2222222, 3333333, 22222222, 22232223, 22322232, 22332233, 23222322, 23232323, 23322332, 23332333, 32223222, 32233223, 32323232, 32333233, 33223322, 33233323, 33323332, 33333333

Offset: 1

N. J. A. Sloane, Jun 30 2012

nonn

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 00, 11, 000, 111, 0000, 0101, 1010, 1111, 00000, 11111, 000000, 001001, 010010, 010101, 011011, 100100, 101010, 101101, 110110, 111111 but this cannot be included as a sequence in the OEIS since it contains nonzero "numbers" beginning with 0.
This sequence results from A213973 by replacing each digit 1 by 2, and from A213972 by replacing all digits 2 by 3 and all digits 1 by 2. - M. F. Hasler, Mar 10 2014

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.

Cf. A213969, A213970, A213971, A213972, A213973.

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

Equals A032810 intersect A239018. - M. F. Hasler, Mar 10 2014

More terms from M. F. Hasler, Mar 10 2014

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

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

A213972 List of imprimitive words over the alphabet {1,2}.

Original entry on oeis.org

11, 22, 111, 222, 1111, 1212, 2121, 2222, 11111, 22222, 111111, 112112, 121121, 121212, 122122, 211211, 212121, 212212, 221221, 222222, 1111111, 2222222, 11111111, 11121112, 11211121, 11221122, 12111211, 12121212, 12211221, 12221222, 21112111, 21122112, 21212121

Offset: 1

N. J. A. Sloane, Jun 30 2012

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
00, 11, 000, 111, 0000, 0101, 1010, 1111, 00000, 11111, 000000, 001001, 010010, 010101, 011011, 100100, 101010, 101101, 110110, 111111
but this cannot be included as a sequence in the OEIS since it contains nonzero "numbers" beginning with 0.
This sequence results from A213973 by replacing all digits 3 by 2 and from A213974 by replacing digits 2 by 1 and digits 3 by 2. - M. F. Hasler, Mar 10 2014

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.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A213969-A213974.

See A239018 for the analog over the alphabet {1,2,3}.

P:= proc(d) option remember;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;
    sort(A);
end proc:
IP:= proc(d)
   sort([seq(seq(s*(10^d-1)/(10^m-1), s = P(m)), m=numtheory:-divisors(d) minus {d})]);
end proc:
seq(op(IP(d)), d=1..10); # Robert Israel, Mar 24 2017

j[w_, k_] := FromDigits /@ (Flatten[Table[#, {k}]] & /@ w); Flatten@ Table[ Union@ Flatten[ j[Tuples [{1, 2}, #], n/#] & /@ Most@ Divisors@ n], {n, 9}] (* Giovanni Resta, Mar 24 2017 *)

for(n=1, 10, p=vector(n, i, 10^(n-i))~; forvec(d=vector(n, i, [1, 2]), is_A239017(m=d*p)||print1(m", "))) \\ M. F. Hasler, Mar 10 2014

A213972 = A007931 intersect A239018. - M. F. Hasler, Mar 10 2014

More terms from M. F. Hasler, Mar 10 2014

A213973 List of imprimitive words over the alphabet {1,3}.

Original entry on oeis.org

11, 33, 111, 333, 1111, 1313, 3131, 3333, 11111, 33333, 111111, 113113, 131131, 131313, 133133, 311311, 313131, 313313, 331331, 333333, 1111111, 3333333, 11111111, 11131113, 11311131, 11331133, 13111311, 13131313, 13311331, 13331333, 31113111, 31133113, 31313131

Offset: 1

N. J. A. Sloane, Jun 30 2012

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
00, 11, 000, 111, 0000, 0101, 1010, 1111, 00000, 11111, 000000, 001001, 010010, 010101, 011011, 100100, 101010, 101101, 110110, 111111
but this cannot be included as a sequence in the OEIS since it contains nonzero "numbers" beginning with 0.
This sequence results from A213972 by replacing all digits 2 by 3, and from A213974 by replacing all digits 2 by 1. - M. F. Hasler, Mar 10 2014

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.

Cf. A213969-A213974.

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

A213973 = A032917 intersect A239018. - M. F. Hasler, Mar 10 2014

More terms from M. F. Hasler, Mar 10 2014

A211029 Triangle read by rows in which row n lists the binary words of length n over the alphabet {1,2} with no initial repeats.

Original entry on oeis.org

1, 2, 12, 21, 121, 122, 211, 212, 1211, 1221, 1222, 2111, 2112, 2122, 12111, 12112, 12211, 12212, 12221, 12222, 21111, 21112, 21121, 21122, 21221, 21222, 121111, 121112, 121122, 122111, 122112, 122121, 122211, 122212, 122221, 122222, 211111, 211112

Offset: 1

Omar E. Pol, Nov 29 2012

As usual in the OEIS, binary alphabets are encoded with {1,2} over the alphabet {0,1} the entries contain nonzero "numbers" beginning with 0.

			The fourth row of triangle of binary sequences is
0100, 0110, 0111, 1000, 1001, 1011 (see section example of A122536) therefore the fourth row of this triangle is
1211, 1221, 1222, 2111, 2112, 2122.
The first six rows of triangle are:
1, 2;
12, 21;
121, 122, 211, 212;
1211, 1221, 1222, 2111, 2112, 2122;
12111, 12112, 12211, 12212, 12221, 12222, 21111, 21112, 21121, 21122, 21221, 21222;
121111, 121112, 121122, 122111, 122112, 122121, 122211, 122212, 122221, 122222, 211111, 211112, 211121, 211122, 211212, 211221, 211222, 212211, 212221, 212222;

Alois P. Heinz, Rows n = 1..14, flattened
Index entries for sequences related to curling numbers

Row n has length A122536(n).

Cf. A093371, A211027, A213969, A216955.

s:= proc(n) s(n):= `if`(n=0, [[]], map(x->
      [[x[], 1], [x[], 2]][], s(n-1))) end:
T:= proc(n) map(x-> parse(cat(x[])), select(proc(l) local i;
      for i to iquo(nops(l), 2) do if l[1..i]=l[i+1..2*i]
      then return false fi od; true end, s(n)))[] end:
seq(T(n), n=1..7);  # Alois P. Heinz, Dec 02 2012

More terms and name improved by R. J. Mathar, Nov 30 2012

A239017 List of primitive words on {1,2,3}.

Original entry on oeis.org

1, 2, 3, 12, 13, 21, 23, 31, 32, 112, 113, 121, 122, 123, 131, 132, 133, 211, 212, 213, 221, 223, 231, 232, 233, 311, 312, 313, 321, 322, 323, 331, 332, 1112, 1113, 1121, 1122, 1123, 1131, 1132, 1133, 1211, 1213, 1221, 1222, 1223, 1231, 1232, 1233, 1311, 1312, 1321, 1322, 1323, 1331, 1332, 1333, 2111, 2112, 2113, 2122, 2123

Offset: 1

M. F. Hasler, Mar 08 2014

A word is primitive if it is not a power (i.e., repetition) of a subword. The non-primitive words 11, 22, 33, 111, 222, 333, 1111, 1212, 1313, 2121, 2222, ... (cf. A239018) are excluded here.
This sequence is the complement of A239018 in A007932.
It is the analog for {1,2,3} of A213969 for {1,2}.
The Lyndon words on {1,2,3}, A102660, are the subsequence of these primitive words not larger than any of their "rotations", i.e., in A239016.

Cf. A213969 - A213974.

is_A239017(n)={fordiv(#d=digits(n),L,L<#d&&d==concat(Col(vector(#d/L,i,1)~*vecextract(d,2^L-1))~)&&return);!setminus(Set(d),[1,2,3])}
for(n=1,5,p=vector(n,i,10^(n-i))~;forvec(d=vector(n,i,[1,3]),is_A239017(m=d*p)&&print1(m",")))

A239017 = A007932 \ A239018.

A213970 List of primitive words over the alphabet {1,3}.

Original entry on oeis.org

1, 3, 13, 31, 113, 131, 133, 311, 313, 331, 1113, 1131, 1133, 1311, 1331, 1333, 3111, 3113, 3133, 3311, 3313, 3331, 11113, 11131, 11133, 11311, 11313, 11331, 11333, 13111, 13113, 13131, 13133, 13311, 13313, 13331, 13333, 31111, 31113, 31131, 31133, 31311, 31313, 31331, 31333, 33111, 33113, 33131, 33133, 33311, 33313, 33331

Offset: 1

N. J. A. Sloane, Jun 30 2012

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.

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.

Cf. A213969-A213974.

A213971 List of primitive words over the alphabet {2,3}.

Original entry on oeis.org

2, 3, 23, 32, 223, 232, 233, 322, 323, 332, 2223, 2232, 2233, 2322, 2332, 2333, 3222, 3223, 3233, 3322, 3323, 3332, 22223, 22232, 22233, 22322, 22323, 22332, 22333, 23222, 23223, 23232, 23233, 23322, 23323, 23332, 23333, 32222, 32223, 32232, 32233, 32322, 32323, 32332, 32333, 33222, 33223, 33232, 33233, 33322, 33323, 33332

Offset: 1

N. J. A. Sloane, Jun 30 2012

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.
The Lyndon words over {2,3} are the intersection of this sequence with A239016. - M. F. Hasler, Mar 10 2014
This sequence results from A213970 by replacing all digits 1 by 2, and from A213969 by replacing all digits 2 by 3 and digits 1 by 2. - M. F. Hasler, Mar 10 2014

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.

Cf. A213969-A213974.

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

A213971 = A032810 intersect A239017. - M. F. Hasler, Mar 10 2014

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

Extensions

A213974 List of imprimitive words over the alphabet {2,3}.

Views

Author

Keywords

Comments

References

Crossrefs

Programs

PARI

Formula

Extensions

A239016 Numbers not larger than any rotation of their digits.

Views

Author

Keywords

Comments

Examples

Programs

PARI

Python

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Python

A213972 List of imprimitive words over the alphabet {1,2}.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A213973 List of imprimitive words over the alphabet {1,3}.

Views

Author

Keywords

Comments

References

Crossrefs

Programs

PARI

Formula

Extensions

A211029 Triangle read by rows in which row n lists the binary words of length n over the alphabet {1,2} with no initial repeats.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Extensions