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

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

Author

Clark Kimberling, Feb 07 2012

Keywords

• nonn

Comments

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)

Examples

			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)
		

Links

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

Crossrefs

Cf. A061395, A064989, A206284, A206285.

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

Programs

Maple

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

Mathematica

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

PARI

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

Extensions

Example section rewritten by Antti Karttunen, Oct 09 2016