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

%I #42 Mar 12 2024 15:40:31

%S 0,1,2,2,4,1,6,4,6,3,10,2,12,5,7,8,16,3,18,6,11,9,22,4,20,11,18,10,28,

%T 29,30,16,19,15,23,6,36,17,23,12,40,1,42,18,21,21,46,8,42,15,31,22,52,

%U 9,39,20,35,27,58,58,60,29,33,32,47,5,66,30,43,11,70,12,72,35,35,34,59,7,78,24,54,39,82,2,63,41,55,36,88,87,71,42,59,45,71,16,96,35,57,30

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

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

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

%C a(2^k*p) = 2^(k-1)*p-2^k if p is an odd prime. - _Robert Israel_, Apr 25 2017

%H Robert Israel, <a href="/A235138/b235138.txt">Table of n, a(n) for n = 1..10000</a>

%H Jonathan Sondow and K. MacMillan, <a href="http://math.colgate.edu/~integers/l34/l34.Abstract.html">Reducing the Erdos-Moser equation 1^n + 2^n + . . . + k^n = (k+1)^n modulo k and k^2</a>, Integers 11 (2011), #A34.

%H Jonathan 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) = A235137(n) (mod n).

%F Conjecture : a(n) = Sum_{d|n} phi(n/d)*d^phi(n) (mod n). - _Ridouane Oudra_, Feb 17 2024

%e a(4) = 30 (mod 4) = 2 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.

%p f:= proc(n) local q; q:= numtheory:-phi(n);

%p add(k&^q, k=1..n) mod n

%p end proc:

%p map(f, [$1..100]); # _Robert Israel_, Apr 25 2017

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

%o (PARI) a(n)=my(p=eulerphi(n));sum(k=1,n,k^p) \\ _Charles R Greathouse IV_, Jan 04 2014

%Y Cf. A007850, A054377, A235137.

%K nonn,look

%O 1,3

%A _Jonathan Sondow_ and Emmanuel Tsukerman, Jan 03 2014