A206442 - OEIS

%I #27 Sep 09 2017 19:36:32

%S 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 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 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 Number of distinct irreducible factors of the polynomial p(n,x) defined at A206284.

%C The factorization is over the ring of polynomials having integer coefficients.

%C From _Robert Israel_, Oct 09 2016: (Start)

%C a(n) = 0 iff n is a power of 2.

%C a(n) <= A061395(n)-1 for n > 1. (End)

%H Antti Karttunen, <a href="/A206442/b206442.txt">Table of n, a(n) for n = 1..10000</a>

%e From _Antti Karttunen_, Oct 09 2016: (Start)

%e For n = 1, the corresponding polynomial is zero-polynomial, thus a(1) = 0.

%e For n = 2, the corresponding polynomial is constant 1, thus a(2) = 0.

%e For n = 3 = prime(2), the corresponding polynomial is x, thus a(3) = 1.

%e 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 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 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 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 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 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 (End)

%p P:= n -> add(f[2]*x^(numtheory:-pi(f[1])-1), f =  ifactors(n)[2]):

%p seq(nops(factors(P(n))[2]),n=1..200); # _Robert Israel_, Oct 09 2016

%t b[n_] := Table[x^k, {k, 0, n}];

%t f[n_] := f[n] = FactorInteger[n]; z = 1000;

%t t[n_, m_, k_] := If[PrimeQ[f[n][[m, 1]]] && f[n][[m, 1]] == 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 TableForm[Table[{n, FactorInteger[n],

%t    p[n, x], -1 + Length[FactorList[p[n, x]]]},

%t {n, 1, z/4}]]

%t Table[-1 + Length[FactorList[p[n, x]]], {n, 1, z/4}]

%t (* A206442 *)

%o (PARI)

%o 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 pfps(n) = if(1==n, 0, if(!(n%2), 1 + pfps(n/2), 'x*pfps(A064989(n))));

%o A206442 = n -> if(!bitand(n,(n-1)), 0, #(factor(pfps(n))~));

%o \\ Alternatively, one may use the version of pfps given by _Charles R Greathouse IV_ in A277322:

%o pfps(n)=my(f=factor(n)); sum(i=1, #f~, f[i, 2] * 'x^(primepi(f[i, 1])-1));

%o \\ In which case this version of the "main function" should suffice:

%o A206442 = n -> if(1==n, 0, #(factor(pfps(n))~));

%o \\ _Antti Karttunen_, Oct 09 2016

%Y Cf. A061395, A064989, A206284, A206285.

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

%K nonn

%O 1,14

%A _Clark Kimberling_, Feb 07 2012

%E Example section rewritten by _Antti Karttunen_, Oct 09 2016