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
Keywords
Programs
-
Mathematica
a[n_] := DivisorSum[n, EulerPhi[n/#] * DivisorSigma[0, #]^(n/#) &]; Array[a, 50] (* Amiram Eldar, May 11 2021 *)
-
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));
Formula
a(n) = Sum_{d|n} phi(n/d) * tau(d)^(n/d).
If p is prime, a(p) = 1 + p.