A213972 - OEIS

%I #21 Mar 24 2017 22:03:03

%S 11,22,111,222,1111,1212,2121,2222,11111,22222,111111,112112,121121,

%T 121212,122122,211211,212121,212212,221221,222222,1111111,2222222,

%U 11111111,11121112,11211121,11221122,12111211,12121212,12211221,12221222,21112111,21122112,21212121

%N List of imprimitive 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 00, 11, 000, 111, 0000, 0101, 1010, 1111, 00000, 11111, 000000, 001001, 010010, 010101, 011011, 100100, 101010, 101101, 110110, 111111

%C but this cannot be included as a sequence in the OEIS since it contains nonzero "numbers" beginning with 0.

%C This sequence results from A213973 by replacing all digits 3 by 2 and from A213974 by replacing digits 2 by 1 and digits 3 by 2. - _M. F. Hasler_, Mar 10 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="/A213972/b213972.txt">Table of n, a(n) for n = 1..10000</a>

%F A213972 = A007931 intersect A239018. - _M. F. Hasler_, Mar 10 2014

%p P:= proc(d) option remember;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     sort(A);

%p end proc:

%p IP:= proc(d)

%p    sort([seq(seq(s*(10^d-1)/(10^m-1), s = P(m)), m=numtheory:-divisors(d) minus {d})]);

%p end proc:

%p seq(op(IP(d)), d=1..10); # _Robert Israel_, Mar 24 2017

%t j[w_, k_] := FromDigits /@ (Flatten[Table[#, {k}]] & /@ w); Flatten@ Table[ Union@ Flatten[ j[Tuples [{1, 2}, #], n/#] & /@ Most@ Divisors@ n], {n, 9}] (* _Giovanni Resta_, Mar 24 2017 *)

%o (PARI) for(n=1, 10, p=vector(n, i, 10^(n-i))~; forvec(d=vector(n, i, [1, 2]), is_A239017(m=d*p)||print1(m", "))) \\ _M. F. Hasler_, Mar 10 2014

%Y Cf. A213969-A213974.

%Y See A239018 for the analog over the alphabet {1,2,3}.

%K nonn,base

%O 1,1

%A _N. J. A. Sloane_, Jun 30 2012

%E More terms from _M. F. Hasler_, Mar 10 2014