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

Author

N. J. A. Sloane, Feb 03 2005

Keywords

• nonn
• easy
• nice

Comments

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

Links

• 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

Crossrefs

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.

Programs

Haskell

cf. link.

Mathematica

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

PARI

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

Formula

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

Extensions

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

Definition improved by Reinhard Zumkeller, Mar 23 2012