A333697 a(n) = Sum_{d|n} (-1)^omega(n/d) * phi(rad(n/d)) * p(d), where p = A000041 (partition numbers).

1, 1, 1, 2, 3, 6, 9, 14, 22, 31, 46, 59, 89, 114, 158, 201, 281, 337, 472, 570, 756, 936, 1233, 1456, 1926, 2323, 2942, 3556, 4537, 5334, 6812, 8088, 10021, 11997, 14805, 17432, 21601, 25507, 30971, 36606, 44543, 52106, 63219, 74097, 88680, 104281, 124708, 145205, 173429, 202124

Offset: 1

Author

Ilya Gutkovskiy, Apr 02 2020

Keywords

• nonn

Crossrefs

Cf. A000010, A000041, A001221, A007947, A008683, A023900, A047968, A078392.

Programs

Mathematica

Table[Sum[(-1)^PrimeNu[n/d] EulerPhi[Last[Select[Divisors[n/d], SquareFreeQ]]] PartitionsP[d], {d, Divisors[n]}], {n, 50}]

PARI

rad(n) = factorback(factorint(n)[, 1]); \\ A007947
a(n) = sumdiv(n, d, (-1)^omega(n/d) * eulerphi(rad(n/d)) * numbpart(d)); \\ Michel Marcus, Apr 03 2020

Formula

a(n) = Sum_{d|n} A023900(n/d) * A000041(d).

a(n) = Sum_{d|n} A047968(n/d) * mu(d) * d.

Sum_{k=1..n} a(gcd(n,k)) = A000041(n).