A165909 a(n) is the sum of the quadratic residues of n.

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, 169, 126, 84, 203, 150, 186, 72, 165, 289, 175, 96, 333, 342, 208, 135, 410, 308, 430, 198, 225, 460, 423, 124, 490, 525, 408, 299, 689, 549, 385, 252, 532, 841, 767, 270

Offset: 1

Author

Christopher Hunt Gribble, Sep 30 2009

Keywords

• nonn

Comments

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.

..n..num QNRs..sum QNRs.........QNRs

..1.........0.........0

..2.........1.........1.........1

..3.........1.........1.........1

..4.........1.........1.........1

..5.........2.........5.........1..4

..6.........3.........8.........1..3..4

..7.........3.........7.........1..2..4

..8.........2.........5.........1..4

..9.........3........12.........1..4..7

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

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

References

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..10000 (first 1000 terms from C. H. Gribble)

Crossrefs

Row sums of A046071 and of A096008.

Cf. A000290, A076409, A076410.

Programs

Haskell

import Data.List (nub)
a165909 n = sum $ nub $ map (`mod` n) $
                        take (fromInteger n) $ tail a000290_list
-- Reinhard Zumkeller, Aug 01 2012

Mathematica

residueQ[n_, k_] := Length[Select[Range[Floor[k/2]], PowerMod[#, 2, k] == n&, 1]] == 1;
a[n_] := Select[Range[n-1], residueQ[#, n]&] // Total;
Array[a, 60] (* Jean-François Alcover, Mar 13 2019 *)

PARI

a(n) = sum(k=0, n-1, k*issquare(Mod(k,n))); \\ Michel Marcus, Mar 13 2019