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,6

Links

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

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.

Mathematica

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

Prog

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

Crossrefs

Cf. A000010, A072911, A077761, A085548.

Sequence in context: A086435 A266226 A376885 * A385416 A099305 A334461

Adjacent sequences: A384419 A384420 A384421 * A384423 A384424 A384425

Keyword

nonn,easy

Author

Amiram Eldar, May 28 2025

Status

approved