A125615 -id:A125615 - cp's OEIS frontend

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

R. K. Guy, Oct 08 2002

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

			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

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.

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

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.

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

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

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

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

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

A282035 Sum of quadratic residues of (n-th prime == 3 mod 4).

Original entry on oeis.org

1, 7, 22, 76, 92, 186, 430, 423, 767, 1072, 994, 1343, 1577, 2369, 2675, 3683, 3930, 4587, 5134, 6520, 6012, 7518, 7831, 8955, 10761, 11596, 12258, 12428, 14809, 15517, 16802, 19527, 23025, 21148, 26811, 29148, 28720, 31929, 35247, 33321, 41900, 41807, 44778, 47844, 51856, 52771, 51253, 57466

Offset: 1

N. J. A. Sloane, Feb 20 2017

nonn

Vincenzo Librandi, Table of n, a(n) for n = 1..5000
Aebi, Christian, and Grant Cairns. Sums of Quadratic residues and nonresidues, arXiv preprint arXiv:1512.00896 (2015).

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.

with(numtheory):
a:=[]; m:=[]; d:=[];
for i1 from 1 to 200 do
p:=ithprime(i1);
if (p mod 4) = 3 then
sp:=0; sm:=0;
for j from 1 to p-1 do
if legendre(j,p)=1 then sp:=sp+j; else sm:=sm+j; fi; od;
a:=[op(a),sp]; m:=[op(m),sm]; d:=[op(d),sm-sp];
fi;
od:
a; m; d; # A282035, A282036, A282037

Table[Table[Mod[a^2, p], {a, 1, (p-1)/2}]//Total, {p, Select[Prime[Range[100]], Mod[#, 4]==3 &]}] (* Vincenzo Librandi, Feb 21 2017 *)
Table[Total[PowerMod[#,2,n]&/@Range[n/2]],{n,Select[Prime[Range[100]],Mod[#,4]==3&]}] (* Harvey P. Dale, Dec 11 2024 *)

do(p)=sum(k=1,p-1,k^2%p)/2
apply(do, select(p->p%4==3, primes(100))) \\ Charles R Greathouse IV, Feb 21 2017

A171555 Numbers of the form prime(n)*(prime(n)-1)/4.

Original entry on oeis.org

5, 39, 68, 203, 333, 410, 689, 915, 1314, 1958, 2328, 2525, 2943, 3164, 4658, 5513, 6123, 7439, 8145, 9264, 9653, 13053, 13514, 14460, 16448, 18023, 19113, 19670, 21389, 24414, 25043, 28308, 30363, 31064, 34689, 37733, 39303, 40100, 41718, 44205, 46764, 50288

Offset: 1

Juri-Stepan Gerasimov, Dec 11 2009

nonn

The halves of even numbers of the form p(p-1)/2 for p prime.

Sum of the quadratic residues of primes of the form 4k + 1. For example, a(3)=68 because 17 is the 3rd prime of the form 4k + 1 and the quadratic residues of 17 are 1, 4, 9, 16, 8, 2, 15, 13 which sum to 68. This sum is also the sum of the quadratic nonresidues. Cf. A230077. - Geoffrey Critzer, May 07 2015

R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; see Exercise 2.21 p. 110.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Aebi, Christian, and Grant Cairns. Sums of Quadratic residues and nonresidues, arXiv preprint arXiv:1512.00896 (2015).

Cf. A005098, A007742, A008837.

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.

Table[Table[Mod[a^2, p], {a, 1, (p - 1)/2}] // Total, {p,
Select[Prime[Range[100]], Mod[#, 4] == 1 &]}] (* Geoffrey Critzer, May 07 2015 *)
Select[(# (#-1))/4&/@Prime[Range[100]],IntegerQ] (* Harvey P. Dale, Dec 24 2022 *)

lista(nn) = forprime(p=2, nn, if ((p % 4)==1, print1(p*(p-1)/4, ", "))); \\ Michel Marcus, Mar 23 2016

Corrected (16448 inserted, 25043 inserted) by R. J. Mathar, May 22 2010

A282036 a(n) is the sum of quadratic nonresidues of A002145(n) (the n-th prime == 3 mod 4).

Original entry on oeis.org

2, 14, 33, 95, 161, 279, 473, 658, 944, 1139, 1491, 1738, 1826, 2884, 2996, 4318, 4585, 5004, 6191, 6683, 7849, 8413, 10314, 10746, 11394, 13157, 13393, 16013, 16566, 18936, 19783, 20376, 23946, 27057, 27804, 30883, 35541, 35232, 36384, 39832, 45671, 50858, 51363, 50059, 55097, 56040

Offset: 1

N. J. A. Sloane, Feb 20 2017

nonn

Robert Israel, Table of n, a(n) for n = 1..10000
Christian Aebi, Grant Cairns, Sums of Quadratic residues and nonresidues, arXiv:1512.00896 [math.NT], 2015.

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.

Cf. A002145.

with(numtheory):
a:=[]; m:=[]; d:=[];
for i1 from 1 to 200 do
p:=ithprime(i1);
if (p mod 4) = 3 then
sp:=0; sm:=0;
for j from 1 to p-1 do
if legendre(j,p)=1 then sp:=sp+j; else sm:=sm+j; fi; od;
a:=[op(a),sp]; m:=[op(m),sm]; d:=[op(d),sm-sp];
fi;
od:
a; m; d; # A282035, A282036, A282037
# Alternative:
f:= p -> add(-k^2 mod p, k=1..(p-1)/2)::
map(f, select(isprime, [seq(p,p=3..1000,4)])); # Robert Israel, Nov 09 2020

f[p_] := Total[Range[p-1] ~Complement~ Table[Mod[k^2, p], {k, (p-1)/2}] ]; f /@ Select[Range[3, 1000, 4], PrimeQ] (* Jean-François Alcover, Feb 16 2018, after Robert Israel *)

lista(nn) = forprime(p=2, nn, if(p%4==3, print1(sum(k=1, p-1, if (!issquare(Mod(k, p)), k)), ", "))); \\ Michel Marcus, Nov 09 2020

a(n) = Sum_{k=1..(A002145(n)-1)/2} (-k^2) mod A002145(n). - J. M. Bergot and Robert Israel, Nov 09 2020

A282037 Let p = n-th prime == 3 mod 4; a(n) = (sum of quadratic nonresidues mod p) - (sum of quadratic residues mod p).

Original entry on oeis.org

1, 7, 11, 19, 69, 93, 43, 235, 177, 67, 497, 395, 249, 515, 321, 635, 655, 417, 1057, 163, 1837, 895, 2483, 1791, 633, 1561, 1135, 3585, 1757, 3419, 2981, 849, 921, 5909, 993, 1735, 6821, 3303, 1137, 6511, 3771, 9051, 6585, 2215, 3241, 3269, 11975, 3409, 4419, 1497, 10563, 2615, 1641, 5067, 2855

Offset: 1

N. J. A. Sloane, Feb 20 2017

nonn

Equals A282036 - A282035.

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Christian Aebi and Grant Cairns. Sums of Quadratic residues and nonresidues, arXiv preprint arXiv:1512.00896 [math.NT] (2015).

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.

with(numtheory):
a:=[]; m:=[]; d:=[];
for i1 from 1 to 200 do
p:=ithprime(i1);
if (p mod 4) = 3 then
sp:=0; sm:=0;
for j from 1 to p-1 do
if legendre(j,p)=1 then sp:=sp+j; else sm:=sm+j; fi; od;
a:=[op(a),sp]; m:=[op(m),sm]; d:=[op(d),sm-sp];
fi;
od:
a; m; d; # A282035, A282036, A282037

sum[p_] := Total[If[JacobiSymbol[#, p] == 1, -#, #]& /@ Range[p-1]];
sum /@ Select[Prime[Range[200]], Mod[#, 4] == 3&] (* Jean-François Alcover, Aug 31 2018 *)

A282038 (Sum of the quadratic nonresidues of prime(n)) - (sum of the quadratic residues of prime(n)).

Original entry on oeis.org

-1, 1, 0, 7, 11, 0, 0, 19, 69, 0, 93, 0, 0, 43, 235, 0, 177, 0, 67, 497, 0, 395, 249, 0, 0, 0, 515, 321, 0, 0, 635, 655, 0, 417, 0, 1057, 0, 163, 1837, 0, 895, 0, 2483, 0, 0, 1791, 633, 1561, 1135, 0, 0, 3585, 0, 1757, 0, 3419, 0, 2981, 0, 0, 849, 0, 921, 5909, 0, 0, 993, 0, 1735, 0, 0, 6821, 3303, 0

Offset: 1

N. J. A. Sloane, Feb 20 2017

sign

Equals 0 if p == 1 (mod 4).

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Christian Aebi and Grant Cairns, Sums of Quadratic residues and nonresidues, arXiv preprint arXiv:1512.00896 [math.NT] (2015).

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.

with(numtheory):
a:=[]; m:=[]; d:=[];
for i1 from 1 to 100 do
p:=ithprime(i1);
sp:=0; sm:=0;
for j from 1 to p-1 do
if legendre(j,p)=1 then sp:=sp+j; else sm:=sm+j; fi; od;
a:=[op(a),sp]; m:=[op(m),sm]; d:=[op(d),sm-sp];
od:
a; m; d; # A076409, A125615, A282038

sum[p_] := Total[If[JacobiSymbol[#, p] == 1, -#, #]& /@ Range[p-1]];
a[n_] := sum[Prime[n]];
Array[a, 100] (* Jean-François Alcover, Aug 31 2018 *)

a(n) = my (p=prime(n)); return (sum(i=1, p-1, if (kronecker(i,p)==1, -i, +i))) \\ Rémy Sigrist, Apr 28 2017

A166406 a(n) = A166405(n)-A166100(n).

Original entry on oeis.org

-1, 1, 0, 7, -27, 11, 0, 30, 0, 19, 0, 69, -250, 9, 0, 93, 0, 70, 0, 156, 0, 43, 0, 235, -1029, 102, 0, 220, 0, 177, 0, 126, 0, 67, 0, 497, 0, 50, 0, 395, -2187, 249, 0, 522, 0, 182, 0, 760, 0, 0, 0, 515, 0, 321, 0, 888, 0, 230, 0, 1190, -6655, 246, 0, 635, 0, 655, 0

Offset: 0

Antti Karttunen, Oct 21 2009, Oct 22 2009

sign

Zeros occur at (A166409(k)-1)/2. The negative terms occur at positions given by A046092 (see the comment at A166040).

Sum of those positive i <= 2n+1, for which J(i,2n+1)=-1 minus sum of those positive i <= 2n+1, for which J(i,2n+1)=+1. Here J(i,k) is the Jacobi symbol.

Antti Karttunen, Table of n, a(n) for n = 0..65535

A125615(n)=a(A102781(n)). Cf. A166100, A166407-A166409. The cases where a(i)/A005408(i) is not integer seem also to be given by A166101.

from sympy import jacobi_symbol as J
def a(n):
    l=0
    m=0
    for i in range(1, 2*n + 2):
        if J(i, 2*n + 1)==-1: l+=i
        elif J(i, 2*n + 1)==1: m+=i
    return l - m
print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 12 2017

A166405 Sum of those positive i <= 2n+1, for which J(i,2n+1)=-1. Here J(i,k) is the Jacobi symbol.

Original entry on oeis.org

0, 2, 5, 14, 0, 33, 39, 45, 68, 95, 63, 161, 0, 126, 203, 279, 165, 245, 333, 312, 410, 473, 270, 658, 0, 459, 689, 660, 513, 944, 915, 630, 780, 1139, 759, 1491, 1314, 775, 1155, 1738, 0, 1826, 1360, 1479, 1958, 1729, 1395, 2090, 2328, 1485, 2525, 2884

Offset: 0

Antti Karttunen, Oct 21 2009

nonn

			For n=5, we get odd number 11 (2*5+1), and J(i,11) = 1,-1,1,1,1,-1,-1,-1,1,-1,0 when i ranges from 1 to 11, J(i,11) obtaining value -1 when i=2, 6, 7, 8 and 10, thus a(5)=33.

A. Karttunen, Table of n, a(n) for n = 0..131071

A125615(n)=a(A102781(n)). Cf. A166100, A166406-A166408. The cases where a(i)/A005408(i) is not integer seem also to be given by A166101. This is NOT a bisection of A165898. Scheme-code for jacobi-symbol is given at A165601.

Table[Total@ Select[Range[2n + 1], JacobiSymbol[#, 2n + 1]==-1 &], {n, 0, 100}] (* Indranil Ghosh, Jun 12 2017 *)

from sympy import jacobi_symbol as J
def a(n): return sum(i for i in range(1, 2*n + 2) if J(i, 2*n + 1)==-1)
# Indranil Ghosh, Jun 12 2017

A125616 (Sum of the quadratic nonresidues of prime(n)) / prime(n).

Original entry on oeis.org

1, 2, 3, 3, 4, 5, 7, 7, 9, 9, 10, 11, 14, 13, 16, 15, 17, 21, 18, 22, 22, 22, 24, 25, 28, 28, 27, 28, 34, 35, 34, 36, 37, 41, 39, 41, 47, 43, 47, 45, 54, 48, 49, 54, 54, 59, 59, 57, 58, 67, 60, 66, 64, 72, 67, 73, 69, 70, 72, 73, 78, 87, 78, 79, 84, 84, 89, 87, 88, 99, 96, 93, 96

Offset: 3

Nick Hobson, Nov 30 2006

Always an integer for primes >= 5.

			The quadratic nonresidues of 7=prime(4) are 3, 5 and 6. Hence a(4) = (3+5+6)/7 = 2.

D. M. Burton, Elementary Number Theory, McGraw-Hill, Sixth Edition (2007), p. 185.

Nick Hobson, Table of n, a(n) for n = 3..1000

Cf. A002143, A076409, A076410, A125613-A125618.

a:= proc(n) local p;
   p:= ithprime(n);
   convert(select(t->numtheory:-legendre(t,p)=-1, [$1..p-1]),`+`)/p;
end proc:
seq(a(n),n=3..100); # Robert Israel, May 10 2015

Table[Total[Flatten[Position[Table[JacobiSymbol[a, p], {a, p - 1}], -1]]]/ p, {p, Prime[Range[3, 100]]}] (* Geoffrey Critzer, May 10 2015 *)

vector(73, m, p=prime(m+2); t=1; for(i=2, (p-1)/2, t+=((i^2)%p)); (p-1)/2-t/p)

a(n) = A125615(n)/prime(n).

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

A177861 Product of the quadratic nonresidues of prime(n).

Original entry on oeis.org

1, 2, 6, 90, 6720, 36960, 11642400, 283046400, 2412984420000, 1140422816332800, 1226781977195174400, 1863152400854384640000, 5988092802221559085056000, 112886540292742916603904000, 158983195607776600998537600000000

Offset: 1

Jonathan Sondow, May 14 2010

a(n) == (-1)^((p-1)/2) (mod p), if p = prime(n) is odd.

			The quadratic nonresidues of prime(4) = 7 are 3, 5, and 6, so a(4) = 3*5*6 = 90.

Carl-Erik Froeberg, On sums and products of quadratic residues, BIT, Nord. Tidskr. Inf.-behandl. 11 (1971) 389-398.

Rahul Gupta, Algorithmic Number Theory, Section 24.5

A125615 Sum of the quadratic nonresidues of prime(n), A177860 Product of the quadratic residues of prime(n), A177863 Product of the quadratic nonresidues of prime(n) modulo prime(n).

Table[ Apply[Times, Flatten[Position[ Table[JacobiSymbol[i, Prime[n]], {i, 1, Prime[n] - 1}], -1]]], {n, 1, 16}]

a(n) = (p-1)!/A177860(n), where p = prime(n).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A282035 Sum of quadratic residues of (n-th prime == 3 mod 4).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A171555 Numbers of the form prime(n)*(prime(n)-1)/4.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A282036 a(n) is the sum of quadratic nonresidues of A002145(n) (the n-th prime == 3 mod 4).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A282037 Let p = n-th prime == 3 mod 4; a(n) = (sum of quadratic nonresidues mod p) - (sum of quadratic residues mod p).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

A282038 (Sum of the quadratic nonresidues of prime(n)) - (sum of the quadratic residues of prime(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A166406 a(n) = A166405(n)-A166100(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

A166405 Sum of those positive i <= 2n+1, for which J(i,2n+1)=-1. Here J(i,k) is the Jacobi symbol.