cp's OEIS Frontend

A213969 List of primitive words over the alphabet {1,2}.

%I A213969 #23 Mar 24 2017 22:02:57
%S A213969 1,2,12,21,112,121,122,211,212,221,1112,1121,1122,1211,1221,1222,2111,
%T A213969 2112,2122,2211,2212,2221,11112,11121,11122,11211,11212,11221,11222,
%U A213969 12111,12112,12121,12122,12211,12212,12221,12222,21111,21112,21121,21122,21211,21212,21221,21222,22111,22112,22121,22122,22211,22212,22221
%N A213969 List of primitive words over the alphabet {1,2}.
%C A213969 A word w is primitive if it cannot be written as u^k with k>1; otherwise it is imprimitive.
%C A213969 The {0,1} version of this sequence is
%C A213969 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 A213969 but this cannot be included as a sequence in the OEIS since it contains nonzero "numbers" beginning with 0.
%C A213969 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 A213969 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 A213969 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 A213969 P:= proc(d) local m,A;
%p A213969     A:= map(t -> (10^d-1)/9 + add(10^s, s = t), combinat:-powerset([$0..d-1]));
%p A213969     for m in numtheory:-divisors(d) minus {d} do
%p A213969       A:= remove(t -> t = (t mod 10^m)*(10^d-1)/(10^m-1), A);
%p A213969     od;
%p A213969     op(sort(A));
%p A213969 end proc:
%p A213969 seq(P(d),d=1..6); # _Robert Israel_, Mar 24 2017
%t A213969 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 A213969 (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 A213969 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 A213969 Cf. A213969-A213974.
%K A213969 nonn,base
%O A213969 1,2
%A A213969 _N. J. A. Sloane_, Jun 30 2012