A384422 The number of prime powers (not including 1) p^e that divide n such that e is coprime to the p-adic valuation of n.

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

Offset: 1

Author

Amiram Eldar, May 28 2025

Keywords

• nonn
• easy

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000010, A072911, A077761, A085548.

Programs

Mathematica

f[p_, e_] := EulerPhi[e]; a[1] = 0; a[n_] := Plus @@ f @@@ FactorInteger[n]; Array[a, 100]

PARI

a(n) = vecsum(apply(eulerphi, factor(n)[, 2]));

Formula

Additive with a(p^e) = phi(e), where phi is the Euler totient function (A000010).

Sum_{k=1..n} a(k) ~ n*(log(log(n)) + B + C), where B is Mertens's constant (A077761), C = Sum_{p prime} f(1/p) = 0.24136815875213146317..., and f(x) = -x + (1-x)*x*Sum_{k>=1} mu(k)*x^(k-1)/(1-x^k)^2.