OFFSET
1,3
FORMULA
G.f.: Sum_{k>=1} Sum_{j>=1} phi(j) * x^(j*prime(k)) / (1 - x^j).
a(n) = Sum_{k=1..n} pi(gcd(n,k)).
MATHEMATICA
Table[Sum[EulerPhi[n/d] PrimePi[d], {d, Divisors[n]}], {n, 70}]
Table[Sum[PrimePi[GCD[n, k]], {k, n}], {n, 70}]
PROG
(PARI) a(n) = sumdiv(n, d, eulerphi(n/d)*primepi(d)); \\ Michel Marcus, Apr 03 2020
CROSSREFS
KEYWORD
nonn
AUTHOR
Ilya Gutkovskiy, Apr 02 2020
STATUS
approved