A339871 - OEIS

A339871

Number of primes p for which the p-adic valuation of phi(n) exceeds the p-adic valuation of n-1, with a(1) = 0 by convention.

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

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

OFFSET

1,14

LINKS

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

FORMULA

a(n) = A001221(A160595(n)).

a(n) <= A055734(n).

PROG

(PARI) A339871(n) = if(1==n, 0, my(s=0); for(k=1, n, my(p=prime(k)); if(valuation(eulerphi(n), p)>valuation(n-1, p), s++)); (s));

(PARI) A339871(n) = if(1==n, 0, my(f=factor(eulerphi(n))); sum(i=1, #f~, f[i, 2]>valuation(n-1, f[i, 1])));

(PARI) A339871(n) = omega(eulerphi(n)/gcd(n-1, eulerphi(n)));