%I #50 Aug 13 2022 18:00:22
%S 3,6,9,10,12,18,20,22,24,27,28,30,36,40,42,44,46,48,50,52,54,56,60,66,
%T 68,70,72,76,80,81,88,92,96,98,100,102,104,108,112,114,116,118,120,
%U 124,126,130,132,136,140,144,148,150,152,154,160,162,164,168,170
%N Numbers that match irreducible polynomials over the nonnegative integers.
%C Starting with 1, which encodes 0-polynomial, each integer m encodes (or "matches") a polynomial p(m,x) with nonnegative integer coefficients determined by the prime factorization of m. Write m = prime(1)^e(1) * prime(2)^e(2) * ... * prime(k)^e(k); then p(m,x) = e(1) + e(2)x + e(3)x^2 + ... + e(k)x^k.
%C Identities:
%C p(m*n,x) = p(m,x) + p(n,x),
%C p(m*n,x) = p(gcd(m,n),x) + p(lcm(m,n),x),
%C p(m+n,x) = p(gcd(m,n),x) + p((m+n)/gcd(m,n),x), so that if A003057 is read as a square matrix, then
%C p(A003057,x) = p(A003989,x) + p(A106448,x).
%C Apart from powers of 3, all terms are even. - _Charles R Greathouse IV_, Feb 11 2012
%C Contains 2*p^m and p*2^m if p is an odd prime and m is in A052485. - _Robert Israel_, Oct 09 2016
%H Antti Karttunen, <a href="/A206284/b206284.txt">Table of n, a(n) for n = 1..10566</a>
%e Polynomials having nonnegative integer coefficients are matched to the positive integers as follows:
%e m p(m,x) irreducible
%e ---------------------------
%e 1 0 no
%e 2 1 no
%e 3 x yes
%e 4 2 no
%e 5 x^2 no
%e 6 1+x yes
%e 7 x^3 no
%e 8 3 no
%e 9 2x yes
%e 10 1+x^2 yes
%p P:= n -> add(f[2]*x^(numtheory:-pi(f[1])-1), f = ifactors(n)[2]):
%p select(irreduc @ P, [$1..200]); # _Robert Israel_, Oct 09 2016
%t b[n_] := Table[x^k, {k, 0, n}];
%t f[n_] := f[n] = FactorInteger[n]; z = 400;
%t t[n_, m_, k_] := If[PrimeQ[f[n][[m, 1]]] && f[n][[m, 1]]
%t == Prime[k], f[n][[m, 2]], 0];
%t u = Table[Apply[Plus,
%t Table[Table[t[n, m, k], {k, 1, PrimePi[n]}], {m, 1,
%t Length[f[n]]}]], {n, 1, z}];
%t p[n_, x_] := u[[n]].b[-1 + Length[u[[n]]]]
%t Table[p[n, x], {n, 1, z/4}]
%t v = {}; Do[n++; If[IrreduciblePolynomialQ[p[n, x]],
%t AppendTo[v, n]], {n, z/2}]; v (* A206284 *)
%t Complement[Range[200], v] (* A206285 *)
%o (PARI) is(n)=my(f=factor(n));polisirreducible(sum(i=1, #f[,1], f[i,2]*'x^primepi(f[i,1]-1))) \\ _Charles R Greathouse IV_, Feb 12 2012
%Y Cf. A052485, A206285 (complement), A206296.
%Y Positions of ones in A277322.
%Y Terms of A277318 form a proper subset of this sequence. Cf. also A277316.
%Y Other sequences about factorization in the same polynomial ring: A206442, A284010.
%Y Polynomial multiplication using the same encoding: A297845.
%K nonn
%O 1,1
%A _Clark Kimberling_, Feb 05 2012
%E Introductory comments edited by _Antti Karttunen_, Oct 09 2016 and _Peter Munn_, Aug 13 2022
|