A333699 a(n) = Sum_{d|n} phi(n/d) * pi(d).

0, 1, 2, 3, 3, 7, 4, 8, 8, 11, 5, 18, 6, 16, 20, 18, 7, 27, 8, 30, 28, 23, 9, 44, 21, 27, 29, 41, 10, 58, 11, 41, 41, 34, 45, 68, 12, 38, 48, 72, 13, 83, 14, 62, 76, 45, 15, 98, 39, 72, 61, 72, 16, 95, 66, 101, 68, 54, 17, 147, 18, 59, 106, 89, 78, 125, 19, 92, 81, 136

Offset

1,3

Comments

Möbius transform of A386596(n). Also, Dirichlet convolution of pi(n) and phi(n). - Wesley Ivan Hurt, Jul 26 2025

Links

Table of n, a(n) for n=1..70.

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

a(n) = Sum_{d|n} A386596(d) * mu(n/d). - Wesley Ivan Hurt, Jul 26 2025

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

Cf. A000010 (phi), A000720 (pi), A018804, A046992, A062774, A386596.

Sequence in context: A105437 A323952 A168140 * A088100 A384156 A097359

Adjacent sequences: A333696 A333697 A333698 * A333700 A333701 A333702

Keyword

nonn

Author

Ilya Gutkovskiy, Apr 02 2020

Status

approved