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