login
Sum (mod n) of the distinct residues of x^n (mod n), x=0..n-1.
1

%I #12 May 20 2021 08:25:18

%S 0,1,0,1,0,2,0,1,0,5,0,2,0,0,0,1,0,2,0,2,0,0,0,2,0,13,0,0,0,0,0,1,0,

%T 17,0,2,0,0,0,2,0,4,0,22,0,0,0,2,0,25,0,0,0,2,0,28,0,29,0,4,0,0,0,1,0,

%U 0,0,17,0,0,0,2,0,37,0,38,0,0,0,2,0,41,0,4

%N Sum (mod n) of the distinct residues of x^n (mod n), x=0..n-1.

%C if n = 2^m, a(n) = 1 ;

%C if n is odd, a(n) = 0 ;

%C if a(n) is prime > 2, then a(n) = n/2, for example a(10) = a(2*5) = 5 ;

%C There exists composite numbers k such that a(k)=k/2, for example a(44)= a(2*22)=22.

%H Antti Karttunen, <a href="/A196777/b196777.txt">Table of n, a(n) for n = 1..16384</a>

%H Antti Karttunen, <a href="/A196777/a196777.txt">Data supplement: n, a(n) computed for n = 1..65537</a>

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

%e a(10) = 5 because the residues (mod 10) of x^10 are 0, 1, 4, 5, 6, 9 and the sum 25 ==5 (mod 10).

%p with(numtheory):sumDistRes := proc(n) local re, x, r ; re := {} ; for x from 0 to n-1 do re := re union { modp(x^n, n) } ; end do: add(r, r=re) ; end : for n from 1 to 150 do ; z:=irem(sumDistRes(n),n) ;printf("%d, ", z);end do: #

%o (PARI) A196777(n) = (vecsum(Set(vector(n, k, lift(Mod(k-1, n)^n))))%n); \\ (After code in A195812) - _Antti Karttunen_, May 19 2021

%Y Cf. A195812, A196546.

%K nonn

%O 1,6

%A _Michel Lagneau_, Oct 06 2011