cp's OEIS Frontend

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

%I A206442 #27 Sep 09 2017 19:36:32
%S A206442 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,
%T A206442 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,
%U A206442 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
%N A206442 Number of distinct irreducible factors of the polynomial p(n,x) defined at A206284.
%C A206442 The factorization is over the ring of polynomials having integer coefficients.
%C A206442 From _Robert Israel_, Oct 09 2016: (Start)
%C A206442 a(n) = 0 iff n is a power of 2.
%C A206442 a(n) <= A061395(n)-1 for n > 1. (End)
%H A206442 Antti Karttunen, <a href="/A206442/b206442.txt">Table of n, a(n) for n = 1..10000</a>
%e A206442 From _Antti Karttunen_, Oct 09 2016: (Start)
%e A206442 For n = 1, the corresponding polynomial is zero-polynomial, thus a(1) = 0.
%e A206442 For n = 2, the corresponding polynomial is constant 1, thus a(2) = 0.
%e A206442 For n = 3 = prime(2), the corresponding polynomial is x, thus a(3) = 1.
%e A206442 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).
%e A206442 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.
%e A206442 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.
%e A206442 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.
%e A206442 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.
%e A206442 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.
%e A206442 (End)
%p A206442 P:= n -> add(f[2]*x^(numtheory:-pi(f[1])-1), f =  ifactors(n)[2]):
%p A206442 seq(nops(factors(P(n))[2]),n=1..200); # _Robert Israel_, Oct 09 2016
%t A206442 b[n_] := Table[x^k, {k, 0, n}];
%t A206442 f[n_] := f[n] = FactorInteger[n]; z = 1000;
%t A206442 t[n_, m_, k_] := If[PrimeQ[f[n][[m, 1]]] && f[n][[m, 1]] == Prime[k], f[n][[m, 2]], 0];
%t A206442 u = Table[Apply[Plus,
%t A206442     Table[Table[t[n, m, k], {k, 1, PrimePi[n]}], {m, 1,
%t A206442       Length[f[n]]}]], {n, 1, z}];
%t A206442 p[n_, x_] := u[[n]].b[-1 + Length[u[[n]]]]
%t A206442 TableForm[Table[{n, FactorInteger[n],
%t A206442    p[n, x], -1 + Length[FactorList[p[n, x]]]},
%t A206442 {n, 1, z/4}]]
%t A206442 Table[-1 + Length[FactorList[p[n, x]]], {n, 1, z/4}]
%t A206442 (* A206442 *)
%o A206442 (PARI)
%o 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)};
%o A206442 pfps(n) = if(1==n, 0, if(!(n%2), 1 + pfps(n/2), 'x*pfps(A064989(n))));
%o A206442 A206442 = n -> if(!bitand(n,(n-1)), 0, #(factor(pfps(n))~));
%o A206442 \\ Alternatively, one may use the version of pfps given by _Charles R Greathouse IV_ in A277322:
%o A206442 pfps(n)=my(f=factor(n)); sum(i=1, #f~, f[i, 2] * 'x^(primepi(f[i, 1])-1));
%o A206442 \\ In which case this version of the "main function" should suffice:
%o A206442 A206442 = n -> if(1==n, 0, #(factor(pfps(n))~));
%o A206442 \\ _Antti Karttunen_, Oct 09 2016
%Y A206442 Cf. A061395, A064989, A206284, A206285.
%Y A206442 Cf. also A277322 (gives the number of irreducible polynomial factors with multiplicity).
%K A206442 nonn
%O A206442 1,14
%A A206442 _Clark Kimberling_, Feb 07 2012
%E A206442 Example section rewritten by _Antti Karttunen_, Oct 09 2016