login
a(n) = Sum_{k = 1..n} k^phi(n), where phi(n) = A000010(n).
14

%I #30 Jan 17 2022 09:17:14

%S 1,3,14,30,979,91,184820,8772,978405,25333,40851766526,60710,

%T 36720042483591,19092295,5666482312,9961449608,76762718946972480009,

%U 105409929,164309788542828686799730,70540730666,15909231318568907,67403375450475,1433191209985108404653810959324,351625763020,15975648280734359596251725645

%N a(n) = Sum_{k = 1..n} k^phi(n), where phi(n) = A000010(n).

%C a(n) == -1 (mod n) if and only if n is prime or is a Giuga number A007850.

%C a(n) == 1 (mod n) if (and probably only if) n is a primary pseudoperfect number A054377.

%H Seiichi Manyama, <a href="/A235137/b235137.txt">Table of n, a(n) for n = 1..388</a>

%H J. Sondow and K. MacMillan, <a href="http://www.emis.de/journals/INTEGERS/papers/l34/l34.Abstract.html">Reducing the Erdős-Moser equation 1^n + 2^n + ... + k^n = (k+1)^n modulo k and k^2</a>, Integers 11 (2011), #A34.

%H J. Sondow and E. Tsukerman, <a href="https://arxiv.org/abs/1401.0322">The p-adic order of power sums, the Erdos-Moser equation, and Bernoulli numbers</a>, arXiv:1401.0322 [math.NT], 2014; see section 4.

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Giuga_number">Giuga number</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Primary_pseudoperfect_number">Primary pseudoperfect number</a>

%F a(n) (mod n) = A235138(n).

%e a(4) = 30 since 1^(phi(4)) + 2^(phi(4)) + 3^(phi(4)) + 4^(phi(4))= 1^2 + 2^2 + 3^2 + 4^2 = 1 + 4 + 9 + 16 = 30.

%e a(5) = 979, since phi(5) = 4 and 1^4 + 2^4 + 3^4 + 4^4 + 5^4 = 1 + 16 + 81 + 256 + 625 = 979.

%e a(6) = 91, since phi(6) = 2 and 1^2 + 2^2 + 3^2 + 4^2 + 5^2 + 6^2 = 1 + 4 + 9 + 16 + 25 + 36 = 91.

%t a[n_] := Sum[PowerMod[i, EulerPhi@n, n], {i, n}]

%o (PARI) a(n) = sum(k=1, n , k^eulerphi(n)); \\ _Michel Marcus_, Oct 21 2015

%Y Cf. A000010, A007850, A054377, A235138.

%K nonn

%O 1,2

%A _Jonathan Sondow_ and Emmanuel Tsukerman, Jan 03 2014