|
%I #23 Mar 24 2017 22:02:57
%S 1,2,12,21,112,121,122,211,212,221,1112,1121,1122,1211,1221,1222,2111,
%T 2112,2122,2211,2212,2221,11112,11121,11122,11211,11212,11221,11222,
%U 12111,12112,12121,12122,12211,12212,12221,12222,21111,21112,21121,21122,21211,21212,21221,21222,22111,22112,22121,22122,22211,22212,22221
%N List of primitive words over the alphabet {1,2}.
%C A word w is primitive if it cannot be written as u^k with k>1; otherwise it is imprimitive.
%C The {0,1} version of this sequence is
%C 0, 1, 01, 10, 001, 010, 011, 100, 101, 110, 0001, 0010, 0011, 0100, 0110, 0111, 1000, 1001, 1011, 1100, 1101, 1110, 00001, 00010, 00011, 00100, 00101, 00110, 00111, 01000, 01001, 01010, 01011, 01100, 01101, 01110, 01111, 10000, 10001, 10010, 10011, 10100, 10101, 10110, 10111, 11000, 11001, 11010, 11011, 11100, 11101, 11110, ...,
%C but this cannot be included as a sequence in the OEIS since it contains nonzero "numbers" beginning with 0.
%C Lyndon words on {1,2}, A102659, are the numbers in this sequence which are also not larger than any of their rotations, i.e., in A239016. - _M. F. Hasler_, Mar 08 2014
%D A. de Luca and S. Varricchio, Finiteness and Regularity in Semigroups and Formal Languages, Monographs in Theoretical Computer Science, Springer-Verlag, Berlin, 1999. See p. 10.
%H Robert Israel, <a href="/A213969/b213969.txt">Table of n, a(n) for n = 1..16222</a> (all terms with up to 13 digits)
%p P:= proc(d) local m,A;
%p A:= map(t -> (10^d-1)/9 + add(10^s, s = t), combinat:-powerset([$0..d-1]));
%p for m in numtheory:-divisors(d) minus {d} do
%p A:= remove(t -> t = (t mod 10^m)*(10^d-1)/(10^m-1), A);
%p od;
%p op(sort(A));
%p end proc:
%p seq(P(d),d=1..6); # _Robert Israel_, Mar 24 2017
%t j[w_, k_] := FromDigits /@ (Flatten[Table[#, {k}]] & /@ w); L[n_] := Complement[ FromDigits /@ Tuples[{1, 2}, n], Union[ Flatten[( j[Tuples[{1, 2}, #1], n/#1] &) /@ Most[ Divisors[n]]]]]; Flatten@ Array[L, 5] (* _Giovanni Resta_, Mar 24 2017 *)
%o (PARI) is_A213969(n)={fordiv(#n=digits(n),L,L<#n&&n==concat(Col(vector(#n/L,i,1)~*vecextract(n,2^L-1))~)&&return);!setminus(Set(n),[1,2])}
%o for(n=1,5,p=vector(n,i,10^(n-i))~;forvec(d=vector(n,i,[1,2]),is_A213969(m=d*p)&&print1(m","))) \\ _M. F. Hasler_, Mar 08 2014
%Y Cf. A213969-A213974.
%K nonn,base
%O 1,2
%A _N. J. A. Sloane_, Jun 30 2012
|
