A102660 -id:A102660 - 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

A027376 Number of ternary irreducible monic polynomials of degree n; dimensions of free Lie algebras.

Original entry on oeis.org

1, 3, 3, 8, 18, 48, 116, 312, 810, 2184, 5880, 16104, 44220, 122640, 341484, 956576, 2690010, 7596480, 21522228, 61171656, 174336264, 498111952, 1426403748, 4093181688, 11767874940, 33891544368, 97764009000, 282429535752, 817028131140, 2366564736720, 6863037256208, 19924948267224, 57906879556410

Offset: 0

N. J. A. Sloane

Number of Lyndon words of length n on {1,2,3}. A Lyndon word is primitive (not a power of another word) and is earlier in lexicographic order than any of its cyclic shifts. - John W. Layman, Jan 24 2006
Exponents in an expansion of the Hardy-Littlewood constant Product(1 - (3*p - 1)/(p - 1)^3, p prime >= 5), whose decimal expansion is in A065418: the constant equals Product_{n >= 2} (zeta(n)*(1 - 2^(-n))*(1 - 3^(-n)))^(-a(n)). - Michael Somos, Apr 05 2003
Number of aperiodic necklaces with n beads of 3 colors. - Herbert Kociemba, Nov 25 2016
Number of irreducible harmonic polylogarithms, see page 299 of Gehrmann and Remiddi reference and table 1 of Maître article. - F. Chapoton, Aug 09 2021
For n>=2, a(n) is the number of Hesse loops of length 2*n, see Theorem 22 of Dutta, Halbeisen, Hungerbühler link. - Sayan Dutta, Sep 22 2023
For n>=2, a(n) is the number of orbits of size n of isomorphism classes of elliptic curves under the Hesse derivative, see Theorem 2 of Kettinger link. - Jake Kettinger, Aug 07 2024

			For n = 2 the a(2)=3 polynomials are  x^2+1, x^2+x+2, x^2+2*x+2. - _Robert Israel_, Dec 16 2015

E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, NY, 1968, p. 84.
M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA, 1983, p. 79.

Seiichi Manyama, Table of n, a(n) for n = 0..2102 (terms 0..200 from T. D. Noe)
Kam Cheong Au, Evaluation of one-dimensional polylogarithmic integral, with applications to infinite series, arXiv:2007.03957 [math.NT], 2020. See 4th line of Table 1 (p. 6).
Joscha Diehl, Rosa Preiß, and Jeremy Reizenstein, Conjugation, loop and closure invariants of the iterated-integrals signature, arXiv:2412.19670 [math.RA], 2024. See p. 6.
Sayan Dutta, Lorenz Halbeisen, and Norbert Hungerbühler, Properties of Hesse derivatives of cubic curves, arXiv:2309.05048 [math.AG], 2023.
T. Gehrmann and E. Remiddi, Numerical evaluation of harmonic polylogarithms. Comput. Phys. Comm. 141 (2001), no. 2, 296-312.
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
Veronika Irvine, Lace Tessellations: A mathematical model for bobbin lace and an exhaustive combinatorial search for patterns, PhD Dissertation, University of Victoria, 2016. See Table A.2.
Jake Kettinger, The dynamics of the Hesse derivative on the j-invariant, arXiv:2408.04117 [math.AG], 2024.
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
D. Maître, HPL, a Mathematica implementation of the harmonic polylogarithms, Computer Physics Communications, Volume 174, Issue 3, 1 February 2006, Pages 222-240.
G. Niklasch, Some number theoretical constants: 1000-digit values [Cached copy]
G. Viennot, Algèbres de Lie Libres et Monoïdes Libres, Lecture Notes in Mathematics 691, Springer Verlag, 1978.
Index entries for sequences related to Lyndon words

Column 3 of A074650.

Cf. A000031, A001037, A001693, A001867, A027375, A027377, A054718, A102660.

with(numtheory): A027376 := n -> `if`(n = 0, 1,
add(mobius(d)*3^(n/d), d = divisors(n))/n):
seq(A027376(n), n = 0..32);

a[0]=1; a[n_] := Module[{ds=Divisors[n], i}, Sum[MoebiusMu[ds[[i]]]3^(n/ds[[i]]), {i, 1, Length[ds]}]/n]
a[0]=1; a[n_] := DivisorSum[n, MoebiusMu[n/#]*3^#&]/n; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Dec 01 2015 *)
mx=40;f[x_,k_]:=1-Sum[MoebiusMu[i] Log[1-k*x^i]/i,{i,1,mx}];CoefficientList[Series[f[x,3],{x,0,mx}],x] (* Herbert Kociemba, Nov 25 2016 *)

a(n)=if(n<1,n==0,sumdiv(n,d,moebius(n/d)*3^d)/n)

a(n) = (1/n)*Sum_{d|n} mu(d)*3^(n/d).
(1 - 3*x) = Product_{n>0} (1 - x^n)^a(n).
G.f.: k = 3, 1 - Sum_{i >= 1} mu(i)*log(1 - k*x^i)/i. - Herbert Kociemba, Nov 25 2016
a(n) ~ 3^n / n. - Vaclav Kotesovec, Jul 01 2018
a(n) = 2*A046211(n) + A046209(n). - R. J. Mathar, Oct 21 2021

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

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

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.

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

A027376 Number of ternary irreducible monic polynomials of degree n; dimensions of free Lie algebras.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

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

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

Views

Author

Keywords

Links

Crossrefs

Programs

Haskell

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

Views

Author

Keywords

Links

Crossrefs

Programs

Haskell

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

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Formula