A277322 - OEIS

A277322

a(n) = number of irreducible polynomial factors (counted with multiplicity) in the polynomial (with nonnegative integral coefficients) constructed from the prime factorization of n.

0, 0, 1, 0, 2, 1, 3, 0, 1, 1, 4, 1, 5, 2, 2, 0, 6, 1, 7, 1, 2, 1, 8, 1, 2, 2, 1, 1, 9, 1, 10, 0, 3, 2, 3, 1, 11, 2, 2, 1, 12, 1, 13, 1, 2, 1, 14, 1, 3, 1, 3, 1, 15, 1, 3, 1, 3, 3, 16, 1, 17, 2, 2, 0, 4, 1, 18, 1, 3, 1, 19, 1, 20, 2, 2, 1, 4, 2, 21, 1, 1, 2, 22, 2, 3, 2, 2, 1, 23, 2, 4, 1, 4, 2, 4, 1, 24, 1, 2, 1, 25, 1, 26, 1, 2

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,5

COMMENTS

Let p(n,x) be the completely additive polynomial-valued function such that p(prime(n),x) = x^(n-1) as defined by Clark Kimberling in A206284. Then this sequence is the number of irreducible factors in p(n,x), counted with multiplicity.

LINKS

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

FORMULA

a(2^n) = 0. [By an explicit convention.]

a(A000040(n)) = n-1.

a(A007188(n)) = n.

a(A260443(n)) = A277013(n).

EXAMPLE

For n = 7 = prime(4), the corresponding polynomial is x^3, which factorizes as (x)(x)(x), thus a(7) = 3.

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 = 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) = 2.

pfps(660) = pfps(2^2*3*5*11) = pfps(2^2) + pfps(3) + pfps(5) + pfps(11) = 2 + x + x^2 + x^4 which is irreducible, so a(660) = 1.

For n = 30030 = Product_{i=1..6} prime(i), the corresponding polynomial is x^5 + x^4 + x^3 + x^2 + x + 1, which factorizes as (x+1)(x^2 - x + 1)(x^2 + x + 1), thus a(30030) = 3.

PROG

(PARI)

allocatemem(2^29);

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

A277322 = n -> if(!bitand(n, (n-1)), 0, vecsum(factor(pfps(n))[, 2]));

for(n=1, 121121, write("b277322.txt", n, " ", A277322(n)));

(PARI)

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

A277322(n) = if(1==n, 0, vecsum(factor(pfps(n))[, 2])); \\ Charles R Greathouse IV, test for one added by Antti Karttunen, Oct 09 2016

CROSSREFS

Cf. A206442 (gives the number of irreducible polynomial factors without multiplicity), A206284 (positions of 1's, i.e., irreducible polynomials).