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

%I #33 Nov 15 2019 21:36:29

%S 1,2,12,112,122,1112,1122,1222,11112,11122,11212,11222,12122,12222,

%T 111112,111122,111212,111222,112122,112212,112222,121222,122222,

%U 1111112,1111122,1111212,1111222,1112112,1112122,1112212,1112222,1121122

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

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

%H Reinhard Zumkeller, <a href="/A102659/b102659.txt">Table of n, a(n) for n = 1..10000</a>

%H F. Bassino, J. Clement and C. Nicaud, <a href="http://dx.doi.org/10.1016/j.disc.2004.11.002">The standard factorization of Lyndon words: an average point of view</a>, Discrete Math. 290 (2005), 1-25.

%H Émilie Charlier, Manon Philibert, Manon Stipulanti, <a href="https://arxiv.org/abs/1804.09735">Nyldon words</a>, arXiv:1804.09735 [math.CO], 2018. See Table 1.

%H A. M. Uludag, A. Zeytin and M. Durmus, <a href="http://math.gsu.edu.tr/uludag/CHARKSANDDESSINS.pdf">Binary Quadratic Forms as Dessins</a>, 2012. - From _N. J. A. Sloane_, Dec 31 2012

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Lyndon_word">Lyndon word</a>

%H Reinhard Zumkeller, <a href="/A210585/a210585.hs.txt">Haskell programs for some sequences concerning Lyndon words</a>

%H <a href="/index/Lu#Lyndon">Index entries for sequences related to Lyndon words</a>

%F A102659 = A102660 intersect A007931 = A213969 intersect A239016. - _M. F. Hasler_, Mar 10 2014

%t lynQ[q_]:=Array[Union[{q,RotateRight[q,#]}]=={q,RotateRight[q,#]}&,Length[q]-1,1,And];

%t Join@@Table[FromDigits/@Select[Tuples[{1,2},n],lynQ],{n,5}] (* _Gus Wiseman_, Nov 14 2019 *)

%o (Haskell) cf. link.

%o (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}.

%o 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

%Y Cf. A001037, A074650, A102660, A210584, A210585.

%Y The "co" version is A329318.

%Y A triangular version is A296657.

%Y A sequence listing all Lyndon compositions is A294859.

%Y Numbers whose binary expansion is Lyndon are A328596.

%Y Length of the Lyndon factorization of the binary expansion is A211100.

%Y Cf. A059966, A060223, A275692, A281013, A296373, A329131, A329313.

%K nonn,easy,nice

%O 1,2

%A _N. J. A. Sloane_, Feb 03 2005

%E More terms from _Franklin T. Adams-Watters_, Dec 14 2006

%E Definition improved by _Reinhard Zumkeller_, Mar 23 2012