A206284 Numbers that match irreducible polynomials over the nonnegative integers.

3, 6, 9, 10, 12, 18, 20, 22, 24, 27, 28, 30, 36, 40, 42, 44, 46, 48, 50, 52, 54, 56, 60, 66, 68, 70, 72, 76, 80, 81, 88, 92, 96, 98, 100, 102, 104, 108, 112, 114, 116, 118, 120, 124, 126, 130, 132, 136, 140, 144, 148, 150, 152, 154, 160, 162, 164, 168, 170

Offset

1,1

Comments

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.

Identities:

p(m*n,x) = p(m,x) + p(n,x),

p(m*n,x) = p(gcd(m,n),x) + p(lcm(m,n),x),

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

p(A003057,x) = p(A003989,x) + p(A106448,x).

Apart from powers of 3, all terms are even. - Charles R Greathouse IV, Feb 11 2012

Contains 2*p^m and p*2^m if p is an odd prime and m is in A052485. - Robert Israel, Oct 09 2016

Links

Antti Karttunen, Table of n, a(n) for n = 1..10566

Example

Polynomials having nonnegative integer coefficients are matched to the positive integers as follows:
   m    p(m,x)    irreducible
  ---------------------------
   1    0         no
   2    1         no
   3    x         yes
   4    2         no
   5    x^2       no
   6    1+x       yes
   7    x^3       no
   8    3         no
   9    2x        yes
  10    1+x^2     yes

Maple

P:= n -> add(f[2]*x^(numtheory:-pi(f[1])-1), f =  ifactors(n)[2]):
select(irreduc @ P, [$1..200]); # Robert Israel, Oct 09 2016

Mathematica

b[n_] := Table[x^k, {k, 0, n}];
f[n_] := f[n] = FactorInteger[n]; z = 400;
t[n_, m_, k_] := If[PrimeQ[f[n][[m, 1]]] && f[n][[m, 1]]
== Prime[k], f[n][[m, 2]], 0];
u = Table[Apply[Plus,
    Table[Table[t[n, m, k], {k, 1, PrimePi[n]}], {m, 1,
      Length[f[n]]}]], {n, 1, z}];
p[n_, x_] := u[[n]].b[-1 + Length[u[[n]]]]
Table[p[n, x], {n, 1, z/4}]
v = {}; Do[n++; If[IrreduciblePolynomialQ[p[n, x]],
AppendTo[v, n]], {n, z/2}]; v  (* A206284 *)
Complement[Range[200], v]      (* A206285 *)

Prog

(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

Crossrefs

Cf. A052485, A206285 (complement), A206296.

Positions of ones in A277322.

Terms of A277318 form a proper subset of this sequence. Cf. also A277316.

Other sequences about factorization in the same polynomial ring: A206442, A284010.

Polynomial multiplication using the same encoding: A297845.

Sequence in context: A229307 A356453 A061904 * A363950 A268328 A247575

Adjacent sequences: A206281 A206282 A206283 * A206285 A206286 A206287

Keyword

nonn

Author

Clark Kimberling, Feb 05 2012

Extensions

Introductory comments edited by Antti Karttunen, Oct 09 2016 and Peter Munn, Aug 13 2022

Status

approved