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,5

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)

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 *)

Prog

(Haskell)
import Data.List (nub)
a165909 n = sum $ nub $ map (`mod` n) $
                        take (fromInteger n) $ tail a000290_list
-- Reinhard Zumkeller, Aug 01 2012
(PARI) a(n) = sum(k=0, n-1, k*issquare(Mod(k, n))); \\ Michel Marcus, Mar 13 2019

Crossrefs

Row sums of A046071 and of A096008.

Cf. A000290, A076409, A076410.

Sequence in context: A204921 A021867 A346192 * A334482 A243598 A230366

Adjacent sequences: A165906 A165907 A165908 * A165910 A165911 A165912

Keyword

nonn

Author

Christopher Hunt Gribble, Sep 30 2009

Status

approved