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

%I #9 Mar 11 2021 17:32:21

%S 1,5,55,517,12501,93371,4941259,67109381,2324522989,40000012505,

%T 2853116706111,35664401886907,3634501279107037,66672040958289359,

%U 3503151123046887555,147573952589743522309,13235844190181388226833,236078448451781550068849,35611553801885644604231623

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

%F a(n) = Sum_{d|n} phi(d^(d+1)) = Sum_{d|n} phi(d) * d^d.

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

%t a[n_] := Sum[(n/GCD[k, n])^(n/GCD[k, n]), {k, 1, n}]; Array[a, 20] (* _Amiram Eldar_, Mar 11 2021 *)

%o (PARI) a(n) = sum(k=1, n, (n/gcd(k, n))^(n/gcd(k, n)));

%o (PARI) a(n) = sumdiv(n, d, eulerphi(d^(d+1)));

%o (PARI) a(n) = sumdiv(n, d, eulerphi(d)*d^d);

%o (PARI) my(N=20, x='x+O('x^N)); Vec(sum(k=1, N, eulerphi(k^(k+1))*x^k/(1-x^k)))

%Y Cf. A000010, A226459, A342411.

%K nonn

%O 1,2

%A _Seiichi Manyama_, Mar 11 2021