A213972 List of imprimitive words over the alphabet {1,2}.

11, 22, 111, 222, 1111, 1212, 2121, 2222, 11111, 22222, 111111, 112112, 121121, 121212, 122122, 211211, 212121, 212212, 221221, 222222, 1111111, 2222222, 11111111, 11121112, 11211121, 11221122, 12111211, 12121212, 12211221, 12221222, 21112111, 21122112, 21212121

Offset: 1

Author

N. J. A. Sloane, Jun 30 2012

Keywords

• nonn
• base

Comments

A word w is primitive if it cannot be written as u^k with k>1; otherwise it is imprimitive.

The {0,1} version of this sequence is

00, 11, 000, 111, 0000, 0101, 1010, 1111, 00000, 11111, 000000, 001001, 010010, 010101, 011011, 100100, 101010, 101101, 110110, 111111

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

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

References

• 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.

Links

• Robert Israel, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A213969-A213974.

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

Programs

Maple

P:= proc(d) option remember;local m,A;
    A:= map(t -> (10^d-1)/9 + add(10^s, s = t), combinat:-powerset([$0..d-1]));
    for m in numtheory:-divisors(d) minus {d} do
      A:= remove(t -> t = (t mod 10^m)*(10^d-1)/(10^m-1), A);
    od;
    sort(A);
end proc:
IP:= proc(d)
   sort([seq(seq(s*(10^d-1)/(10^m-1), s = P(m)), m=numtheory:-divisors(d) minus {d})]);
end proc:
seq(op(IP(d)), d=1..10); # Robert Israel, Mar 24 2017

Mathematica

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 *)

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

Formula

A213972 = A007931 intersect A239018. - M. F. Hasler, Mar 10 2014

Extensions

More terms from M. F. Hasler, Mar 10 2014