login
A213969
List of primitive words over the alphabet {1,2}.
11
1, 2, 12, 21, 112, 121, 122, 211, 212, 221, 1112, 1121, 1122, 1211, 1221, 1222, 2111, 2112, 2122, 2211, 2212, 2221, 11112, 11121, 11122, 11211, 11212, 11221, 11222, 12111, 12112, 12121, 12122, 12211, 12212, 12221, 12222, 21111, 21112, 21121, 21122, 21211, 21212, 21221, 21222, 22111, 22112, 22121, 22122, 22211, 22212, 22221
OFFSET
1,2
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
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, ...,
but this cannot be included as a sequence in the OEIS since it contains nonzero "numbers" beginning with 0.
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
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..16222 (all terms with up to 13 digits)
MAPLE
P:= proc(d) 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;
op(sort(A));
end proc:
seq(P(d), d=1..6); # Robert Israel, Mar 24 2017
MATHEMATICA
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 *)
PROG
(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])}
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
CROSSREFS
KEYWORD
nonn,base
AUTHOR
N. J. A. Sloane, Jun 30 2012
STATUS
approved