A165909 - OEIS

%I #54 Feb 28 2021 09:53:47

%S 0,1,1,1,5,8,7,5,12,25,22,14,39,42,30,14,68,60,76,35,70,110,92,42,125,

%T 169,126,84,203,150,186,72,165,289,175,96,333,342,208,135,410,308,430,

%U 198,225,460,423,124,490,525,408,299,689,549,385,252,532,841,767,270

%N a(n) is the sum of the quadratic residues of n.

%C The table below shows n, the number of nonzero quadratic residues (QRs) of n (A105612), the sum of the QRs of n and the nonzero QRs of n (A046071) for n = 1..10.

%C ..n..num QNRs..sum QNRs.........QNRs

%C ..1.........0.........0

%C ..2.........1.........1.........1

%C ..3.........1.........1.........1

%C ..4.........1.........1.........1

%C ..5.........2.........5.........1..4

%C ..6.........3.........8.........1..3..4

%C ..7.........3.........7.........1..2..4

%C ..8.........2.........5.........1..4

%C ..9.........3........12.........1..4..7

%C .10.........5........25.........1..4..5..6..9

%C When p is prime >= 5, a(p) is a multiple of p by a variant of Wolstenholme's theorem (see A076409 and A076410). _Robert Israel_ remarks that we don't need Wolstenholme, just the fact that Sum_{x=1..p-1} x^2 = p*(2*p-1)*(p-1)/6. - _Bernard Schott_, Mar 13 2019

%D G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 4th ed., Oxford Univ. Press, 1960, pp. 88-90.

%H Alois P. Heinz, <a href="/A165909/b165909.txt">Table of n, a(n) for n = 1..10000</a> (first 1000 terms from C. H. Gribble)

%t residueQ[n_, k_] := Length[Select[Range[Floor[k/2]], PowerMod[#, 2, k] == n&, 1]] == 1;

%t a[n_] := Select[Range[n-1], residueQ[#, n]&] // Total;

%t Array[a, 60] (* _Jean-François Alcover_, Mar 13 2019 *)

%o (Haskell)

%o import Data.List (nub)

%o a165909 n = sum $ nub $ map (`mod` n) $

%o                         take (fromInteger n) $ tail a000290_list

%o -- _Reinhard Zumkeller_, Aug 01 2012

%o (PARI) a(n) = sum(k=0, n-1, k*issquare(Mod(k,n))); \\ _Michel Marcus_, Mar 13 2019

%Y Row sums of A046071 and of A096008.

%Y Cf. A000290, A076409, A076410.

%K nonn

%O 1,5

%A _Christopher Hunt Gribble_, Sep 30 2009