A321349 a(n) = Sum_{d|n} phi(d^n), where phi() is the Euler totient function (A000010).

1, 3, 19, 137, 2501, 16071, 705895, 8421505, 258293449, 4007813013, 259374246011, 2972767821815, 279577021469773, 4762869973595499, 233543432626753439, 9223512776490647553, 778579070010669895697, 13115569455375954492093, 1874292305362402347591139

Offset

1,2

Links

Seiichi Manyama, Table of n, a(n) for n = 1..386

Formula

G.f.: Sum_{k>=1} k^(k-1)*phi(k)*x^k/(1 - (k*x)^k).

a(n) = Sum_{d|n} d^(n-1)*phi(d).

a(n) = Sum_{k=1..n} (n/gcd(n,k))^(n-1).

From Richard L. Ollerton, May 08 2021: (Start)

a(n) = Sum_{k=1..n} phi(gcd(n,k)^n)/phi(n/gcd(n,k)).

a(n) = Sum_{k=1..n} gcd(n,k)^(n-1)*phi(gcd(n,k))/phi(n/gcd(n,k)). (End)

Mathematica

Table[Sum[EulerPhi[d^n], {d, Divisors[n]}], {n, 19}]
nmax = 19; Rest[CoefficientList[Series[Sum[k^(k - 1) EulerPhi[k] x^k/(1 - (k x)^k), {k, 1, nmax}], {x, 0, nmax}], x]]
Table[Sum[(n/GCD[n, k])^(n - 1), {k, n}], {n, 19}]

Prog

(PARI) a(n) = sumdiv(n, d, eulerphi(d^n)); \\ Michel Marcus, Nov 06 2018

Crossrefs

Cf. A000010, A057660, A068963, A068970, A226459, A226561.

Sequence in context: A321515 A094661 A094662 * A115750 A156894 A221374

Adjacent sequences: A321346 A321347 A321348 * A321350 A321351 A321352

Keyword

nonn

Author

Ilya Gutkovskiy, Nov 06 2018

Status

approved