A076409 Sum of the quadratic residues of prime(n).

1, 1, 5, 7, 22, 39, 68, 76, 92, 203, 186, 333, 410, 430, 423, 689, 767, 915, 1072, 994, 1314, 1343, 1577, 1958, 2328, 2525, 2369, 2675, 2943, 3164, 3683, 3930, 4658, 4587, 5513, 5134, 6123, 6520, 6012, 7439, 7518, 8145, 7831, 9264, 9653, 8955, 10761, 11596

Offset

1,3

Comments

Row sums of A063987. - R. J. Mathar, Jan 08 2015

prime(n) divides a(n) for n > 2. This is implied by a variant of Wolstenholme's theorem (see Hardy & Wright reference). - Isaac Saffold, Jun 21 2018

References

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

Kenneth A. Ribet, Modular forms and Diophantine questions, Challenges for the 21st century (Singapore 2000), 162-182; World Sci. Publishing, River Edge NJ 2001; Math. Rev. 2002i:11030.

Links

Zak Seidov, Table of n, a(n) for n = 1..1000

Christian Aebi and Grant Cairns, Sums of Quadratic residues and nonresidues, arXiv preprint arXiv:1512.00896 [math.NT] (2015).

Formula

If prime(n) = 4k+1 then a(n) = k*(4k+1).

For n>2 if prime(n) = 4k+3 then a(n) = (k - b)*(4k+3) where b = (h(-p) - 1) / 2; h(-p) = A002143. For instance. If n=5, p=11, k=2, b=(1-1)/2=0 and a(5) = 2*11 = 22. If n=20, p=71, k=17, b=(7-1)/2=3 and a(20) = 14*71 = 994. - Andrés Ventas, Mar 01 2021

Example

If n = 3, then p = 5 and a(3) = 1 + 4 = 5. If n = 4, then p = 7 and a(4) = 1 + 4 + 2 = 7. If n = 5, then p = 11 and a(5) = 1 + 4 + 9 + 5 + 3 = 22. - Michael Somos, Jul 01 2018

Maple

A076409 := proc(n)
  local a, p, i ;
  p := ithprime(n) ;
  a := 0 ;
  for i from 1 to p-1 do
    if numtheory[legendre](i, p) = 1 then
       a := a+i ;
    end if;
  end do;
  a ;
end proc: # R. J. Mathar, Feb 26 2011

Mathematica

Join[{1, 1}, Table[ Apply[ Plus, Flatten[ Position[ Table[ JacobiSymbol[i, Prime[n]], {i, 1, Prime[n] - 1}], 1]]], {n, 3, 48}]]
Join[{1}, Table[p=Prime[n]; If[Mod[p, 4]==1, p(p-1)/4, Sum[PowerMod[k, 2, p], {k, p/2}]], {n, 2, 1000}]] (* Zak Seidov, Nov 02 2011 *)
a[ n_] := If[ n < 3, Boole[n > 0], With[{p = Prime[n]}, Sum[ Mod[k^2, p], {k, (p - 1)/2}]]]; (* Michael Somos, Jul 01 2018 *)

Prog

(PARI) a(n, p=prime(n))=if(p<5, return(1)); if(k%4==1, return(p\4*p)); sum(k=1, p-1, k^2%p) \\ Charles R Greathouse IV, Feb 21 2017

Crossrefs

Cf. A076410.

Sums of residues, nonresidues, and their differences, for p == 1 mod 4, p == 3 mod 4, and all p: A171555; A282035, A282036, A282037; A076409, A125615, A282038.

Sequence in context: A036498 A350193 A248086 * A294154 A260658 A028281

Adjacent sequences: A076406 A076407 A076408 * A076410 A076411 A076412

Keyword

nonn,easy

Author

R. K. Guy, Oct 08 2002

Extensions

Edited and extended by Robert G. Wilson v, Oct 09 2002

Status

approved