login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A102659 List of Lyndon words on {1,2} sorted first by length and then lexicographically. 47
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

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

FORMULA

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

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

PROG

(Haskell) cf. link.

(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

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.

Sequence in context: A235860 A317208 A207778 * A212659 A191895 A047855

Adjacent sequences:  A102656 A102657 A102658 * A102660 A102661 A102662

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane, Feb 03 2005

EXTENSIONS

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

Definition improved by Reinhard Zumkeller, Mar 23 2012

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 14 04:13 EDT 2020. Contains 336477 sequences. (Running on oeis4.)