A206285 -id:A206285 - cp's OEIS frontend

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

Clark Kimberling, Feb 05 2012

nonn

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

			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

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

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.

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

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

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

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

A206442 Number of distinct irreducible factors of the polynomial p(n,x) defined at A206284.

Original entry on oeis.org

0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 2, 2, 0, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 0, 3, 2, 2, 1, 1, 2, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 3, 1, 1, 1, 2, 1, 3, 3, 1, 1, 1, 2, 2, 0, 3, 1, 1, 1, 3, 1, 1, 1, 1, 2, 2, 1, 2, 2, 1, 1, 1, 2, 1, 2, 2, 2, 2, 1, 1, 1, 2, 1, 4, 2, 3, 1, 1, 1, 2

Offset: 1

Clark Kimberling, Feb 07 2012

nonn

The factorization is over the ring of polynomials having integer coefficients.
From Robert Israel, Oct 09 2016: (Start)
a(n) = 0 iff n is a power of 2.
a(n) <= A061395(n)-1 for n > 1. (End)

			From _Antti Karttunen_, Oct 09 2016: (Start)
For n = 1, the corresponding polynomial is zero-polynomial, thus a(1) = 0.
For n = 2, the corresponding polynomial is constant 1, thus a(2) = 0.
For n = 3 = prime(2), the corresponding polynomial is x, thus a(3) = 1.
For n = 11 = prime(5), the corresponding polynomial is x^4 which factorizes as (x)(x)(x)(x), thus a(11) = 1. (Only distinct factors are counted by this sequence).
For n = 14 = prime(4) * prime(1), the corresponding polynomial is x^3 + 1, which factorizes as (x + 1)(x^2 - x + 1), thus a(14) = 2.
For n = 33 = prime(5) * prime(2), the corresponding polynomial is x^4 + x, which factorizes as x(x+1)(x^2 - x + 1), thus a(33) = 3.
For n = 90 = prime(3) * prime(2)^2 * prime(1), the corresponding polynomial is x^2 + 2x + 1, which factorizes as (x + 1)^2, thus a(90) = 1.
For n = 93 = prime(11) * prime(2), the corresponding polynomial is x^10 + x, which factorizes as x(x+1)(x^2 - x + 1)(x^6 - x^3 + 1), thus a(93) = 4.
For n = 177 = prime(17) * prime(2), the corresponding polynomial is x^16 + x, which factorizes as x(x + 1)(x^2 - x + 1)(x^4 - x^3 + x^2 - x + 1)(x^8 + x^7 - x^5 - x^4 - x^3 + x + 1), thus a(177) = 5.
(End)

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

Cf. A061395, A064989, A206284, A206285.

Cf. also A277322 (gives the number of irreducible polynomial factors with multiplicity).

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

b[n_] := Table[x^k, {k, 0, n}];
f[n_] := f[n] = FactorInteger[n]; z = 1000;
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]]]]
TableForm[Table[{n, FactorInteger[n],
   p[n, x], -1 + Length[FactorList[p[n, x]]]},
{n, 1, z/4}]]
Table[-1 + Length[FactorList[p[n, x]]], {n, 1, z/4}]
(* A206442 *)

A064989(n) = {my(f); f = factor(n); if((n>1 && f[1,1]==2), f[1,2] = 0); for (i=1, #f~, f[i,1] = precprime(f[i,1]-1)); factorback(f)};
pfps(n) = if(1==n, 0, if(!(n%2), 1 + pfps(n/2), 'x*pfps(A064989(n))));
A206442 = n -> if(!bitand(n,(n-1)), 0, #(factor(pfps(n))~));
\\ Alternatively, one may use the version of pfps given by Charles R Greathouse IV in A277322:
pfps(n)=my(f=factor(n)); sum(i=1, #f~, f[i, 2] * 'x^(primepi(f[i, 1])-1));
\\ In which case this version of the "main function" should suffice:
A206442 = n -> if(1==n, 0, #(factor(pfps(n))~));
\\ Antti Karttunen, Oct 09 2016

Example section rewritten by Antti Karttunen, Oct 09 2016

cp's OEIS Frontend

A206284 Numbers that match irreducible polynomials over the nonnegative integers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions