A344195 a(n) = Sum_{k=1..n} tau(gcd(k,n))^(n/gcd(k,n)), where tau(n) is the number of divisors of n.

1, 3, 4, 9, 6, 26, 8, 49, 25, 140, 12, 240, 14, 782, 156, 1215, 18, 3349, 20, 5130, 800, 20498, 24, 19558, 151, 98324, 3148, 111492, 30, 270624, 32, 551091, 20520, 2097176, 924, 1716189, 38, 9437210, 98348, 8630496, 42, 25362724, 44, 43714584, 266346, 184549406, 48, 137141048, 813, 671096867

Offset

1,2

Links

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

Formula

a(n) = Sum_{d|n} phi(n/d) * tau(d)^(n/d).

If p is prime, a(p) = 1 + p.

Mathematica

a[n_] := DivisorSum[n, EulerPhi[n/#] * DivisorSigma[0, #]^(n/#) &]; Array[a, 50] (* Amiram Eldar, May 11 2021 *)

Prog

(PARI) a(n) = sum(k=1, n, numdiv(gcd(k, n))^(n/gcd(k, n)));
(PARI) a(n) = sumdiv(n, d, eulerphi(n/d)*numdiv(d)^(n/d));

Crossrefs

Cf. A000005, A279789, A342424, A344140, A344194.

Sequence in context: A055225 A054791 A167531 * A376683 A356541 A062319

Adjacent sequences: A344192 A344193 A344194 * A344196 A344197 A344198

Keyword

nonn

Author

Seiichi Manyama, May 11 2021

Status

approved