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

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, 29, 30, 16, 19, 15, 23, 6, 36, 17, 23, 12, 40, 1, 42, 18, 21, 21, 46, 8, 42, 15, 31, 22, 52, 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

Offset: 1

Author

Jonathan Sondow and Emmanuel Tsukerman, Jan 03 2014

Keywords

• nonn
• look

Comments

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

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

a(2^k*p) = 2^(k-1)*p-2^k if p is an odd prime. - Robert Israel, Apr 25 2017

Examples

			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.
		

Links

• Robert Israel, Table of n, a(n) for n = 1..10000
• Jonathan Sondow and K. MacMillan, Reducing the Erdos-Moser equation 1^n + 2^n + . . . + k^n = (k+1)^n modulo k and k^2, Integers 11 (2011), #A34.
• Jonathan Sondow and E. Tsukerman, The p-adic order of power sums, the Erdos-Moser equation, and Bernoulli numbers, arXiv:1401.0322 [math.NT], 2014; see section 4.
• Wikipedia, Giuga number
• Wikipedia, Primary pseudoperfect number

Crossrefs

Cf. A007850, A054377, A235137.

Programs

Maple

f:= proc(n) local q; q:= numtheory:-phi(n);
   add(k&^q, k=1..n) mod n
end proc:
map(f, [$1..100]); # Robert Israel, Apr 25 2017

Mathematica

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

PARI

a(n)=my(p=eulerphi(n));sum(k=1,n,k^p) \\ Charles R Greathouse IV, Jan 04 2014

Formula

a(n) = A235137(n) (mod n).

Conjecture : a(n) = Sum_{d|n} phi(n/d)*d^phi(n) (mod n). - Ridouane Oudra, Feb 17 2024