A076410 -id:A076410 - 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

A088144 Sum of primitive roots of n-th prime.

Original entry on oeis.org

1, 2, 5, 8, 23, 26, 68, 57, 139, 174, 123, 222, 328, 257, 612, 636, 886, 488, 669, 1064, 876, 1105, 1744, 1780, 1552, 2020, 1853, 2890, 1962, 2712, 2413, 3536, 4384, 3335, 5364, 3322, 3768, 4564, 7683, 7266, 8235, 4344, 8021, 6176, 8274

Offset: 1

Ed Pegg Jr, Nov 03 2003

nonn

It is a result that goes back to Mirsky that the set of primes p for which p-1 is squarefree has density A, where A denotes the Artin constant (A = Product_{q prime} (1-1/(q*(q-1)))). Numerically A = 0.3739558136.. = A005596. More precisely, Sum_{p <= x} mu(p-1)^2 = Ax/log x + o(x/log x) as x tends to infinity. Conjecture: sum_{p <= x, mu(p-1)=1} 1 = (A/2)x/log x + o(x/log x) and sum_{p <= x, mu(p-1)=-1} 1 = (A/2)x/log x + o(x/log x). - Pieter Moree (moree(AT)mpim-bonn.mpg.de), Nov 03 2003
The number of the primitive roots is A008330(n). - R. K. Guy, Feb 25 2011
If prime(n)  == 1 (mod 4), then a(n) = prime(n)*A008330(n)/2. There are also primes of the form prime(n) == 3 (mod 4) where prime(n) | a(n), namely prime(n) = 19, 127, 151, 163, 199, 251,... The list of primes in both modulo-4 classes where prime(n)|a(n) is 5, 13, 17, 19, 29, 37, 41, 53, 61,... - R. K. Guy, Feb 25 2011
a(n) = A076410(n) at n = 1, 3, 7, 55,... (for p = 2, 5, 17, 257... and perhaps only for the Fermat primes). - R. K. Guy, Feb 25 2011

			For 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, the primitive roots are as follows: {{1}, {2}, {2, 3}, {3, 5}, {2, 6, 7, 8}, {2, 6, 7, 11}, {3, 5, 6, 7, 10, 11, 12, 14}, {2, 3, 10, 13, 14, 15}, {5, 7, 10, 11, 14, 15, 17, 19, 20, 21}, {2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27}}

C. F. Gauss, Disquisitiones Arithmeticae, Yale, 1965; see p. 52.

T. D. Noe, Table of n, a(n) for n=1..1000
Leon Mirsky, The Number of Representations of an Integer as the Sum of a Prime and a k-Free Integer, Amer. Math. Monthly 56 (1949), 17-19.

Row sums of A060749, A254309.

Cf. A088145, A121380, A123475, A222009.

PrimitiveRootQ[ a_Integer, p_Integer ] := Block[ {fac, res}, fac = FactorInteger[ p - 1 ]; res = Table[ PowerMod[ a, (p - 1)/fac[ [ i, 1 ] ], p ], {i, Length[ fac ]} ]; ! MemberQ[ res, 1 ] ] PrimitiveRoots[ p_Integer ] := Select[ Range[ p - 1 ], PrimitiveRootQ[ #, p ] & ]
Total /@ Table[PrimitiveRootList[Prime[k]], {k, 1, 45}] (* Updated for Mathematica 13 by Harlan J. Brothers, Feb 27 2023 *)

a(n)=local(r, p, pr, j); p=prime(n); r=vector(eulerphi(p-1)); pr=znprimroot(p); for(i=1, p-1, if(gcd(i, p-1)==1, r[j++]=lift(pr^i))); vecsum(r) \\ after Franklin T. Adams-Watters's code in A060749, Michel Marcus, Mar 16 2015

A125615 Sum of the quadratic nonresidues of prime(n).

Original entry on oeis.org

0, 2, 5, 14, 33, 39, 68, 95, 161, 203, 279, 333, 410, 473, 658, 689, 944, 915, 1139, 1491, 1314, 1738, 1826, 1958, 2328, 2525, 2884, 2996, 2943, 3164, 4318, 4585, 4658, 5004, 5513, 6191, 6123, 6683, 7849, 7439, 8413, 8145, 10314, 9264, 9653, 10746, 11394

Offset: 1

Nick Hobson, Nov 30 2006

For all n > 2, prime(n) divides a(n).

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

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

Nick Hobson, 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. A076409, A076410, A125613-A125618.

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[p=Prime[n];Total[Complement[Range[p-1],Union[Table[PowerMod[k, 2, p], {k, p}]]]],{n,47}] (* James C. McMahon, Dec 19 2024 *)

vector(47, n, p=prime(n); t=1; for(i=2, (p-1)/2, t+=((i^2)%p)); p*(p-1)/2-t)

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

A125613 Sum of the squares of the quadratic residues of prime(n).

Original entry on oeis.org

1, 1, 17, 21, 132, 351, 816, 874, 1104, 4031, 3286, 8473, 11726, 11868, 11233, 24857, 28143, 38247, 46766, 40754, 66722, 65017, 83249, 120150, 156364, 173013, 152955, 184147, 218763, 245436, 297053, 327500, 437030, 413803, 556217, 488334, 652335

Offset: 1

Nick Hobson, Nov 30 2006

For all n > 3, prime(n) divides a(n).

			The quadratic residues of 7=prime(4) are 1, 2 and 4. Hence a(4)=1^2 + 2^2 + 4^2=21.

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

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

Cf. A076409, A076410, A125613-A125618.

Table[Total[ResourceFunction["QuadraticResidues"][Prime[n]]^2],{n,37}] (* James C. McMahon, Dec 19 2024 *)

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

A125618 (Sum of the squares of the quadratic nonresidues of prime(n)) / prime(n).

Original entry on oeis.org

10, 23, 23, 40, 65, 117, 127, 199, 209, 254, 319, 474, 441, 654, 583, 765, 1071, 826, 1218, 1252, 1246, 1476, 1637, 2000, 2042, 1899, 2028, 2974, 3155, 2998, 3394, 3593, 4291, 3983, 4469, 5525, 4867, 5743, 5301, 7274, 5964, 6321, 7446, 7684, 9013, 9099

Offset: 4

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^2 + 5^2 + 6^2)/7 = 10.

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

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

Cf. A076409, A076410, A125613-A125618.

Table[Total[Complement[Range[p-1], Union[Table[PowerMod[k, 2, p], {k, p}]]]^2]/p, {p, Prime@Range[4,49]}] (* James C. McMahon, Dec 20 2024 *)

vector(46, m, p=prime(m+3); t=1; for(i=2, (p-1)/2, t+=((i^2)%p)^2); (p-1)*(2*p-1)/6-t/p)

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

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

Original entry on oeis.org

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

Christopher Hunt Gribble, Sep 30 2009

nonn

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

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

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

Row sums of A046071 and of A096008.

Cf. A000290, A076409, A076410.

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

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

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

A165951 a(n) = (Sum of the quadratic non-residues of prime(n) - Sum of the quadratic residues of prime(n)) / prime(n).

Original entry on oeis.org

0, 0, 0, 1, 1, 0, 0, 1, 3, 0, 3, 0, 0, 1, 5, 0, 3, 0, 1, 7, 0, 5, 3, 0, 0, 0, 5, 3, 0, 0, 5, 5, 0, 3, 0, 7, 0, 1, 11, 0, 5, 0, 13, 0, 0, 9, 3, 7, 5, 0, 0, 15, 0, 7, 0, 13, 0, 11, 0, 0, 3, 0, 3, 19, 0, 0, 3, 0, 5, 0, 0, 19, 9, 0, 3, 17, 0, 0, 0, 0, 9, 0, 21, 0, 15, 5, 0, 0, 0, 7, 7, 25, 7, 9, 3, 21, 0, 0

Offset: 1

Christopher Hunt Gribble, Oct 01 2009

nonn

The positive terms are A002143 minus its first term (for p=3, A002143(1)=1 corresponds to 0 here). - Javier Múgica, Nov 23 2024

C. H. Gribble, Table of n, a(n) for n=1,..., 348513 (i.e. for primes < 5x10^6).

Cf. A076410, A125616.

Cf. allso A002143 (positive terms).

a(n) = Sum_{j=1..prime(n)-1} floor(j^2/prime(n)) - floor((prime(n)-2)*(prime(n)-1)/3) for n >= 3.

a(n) = A125616(n) - A076410(n) for n>=3.

a(1)-a(2) added by Christopher Hunt Gribble, Oct 07 2009

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

A125617 Sum of the squares of the quadratic nonresidues of prime(n).

Original entry on oeis.org

0, 4, 13, 70, 253, 299, 680, 1235, 2691, 3683, 6169, 7733, 10414, 13717, 22278, 23373, 38586, 35563, 51255, 76041, 60298, 96222, 103916, 110894, 143172, 165337, 206000, 218494, 206991, 229164, 377698, 413305, 410726, 471766, 535357, 647941, 625331

Offset: 1

Nick Hobson, Nov 30 2006

For all n > 3, prime(n) divides a(n).

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

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

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

Cf. A076409, A076410, A125613-A125618.

Table[Total[Complement[Range[p-1],Union[Table[PowerMod[k, 2, p], {k, p}]]]^2],{p,Prime@Range[37]}] (* James C. McMahon, Dec 19 2024 *)

vector(37, n, p=prime(n); t=1; for(i=2, (p-1)/2, t+=((i^2)%p)^2); p*(p-1)*(2*p-1)/6-t)

A125614 (Sum of the squares of the quadratic residues of prime(n)) / prime(n).

Original entry on oeis.org

3, 12, 27, 48, 46, 48, 139, 106, 229, 286, 276, 239, 469, 477, 627, 698, 574, 914, 823, 1003, 1350, 1612, 1713, 1485, 1721, 2007, 2172, 2339, 2500, 3190, 2977, 3733, 3234, 4155, 4306, 3688, 5023, 4848, 5529, 4791, 6356, 6517, 5655, 7051, 7452, 7964, 8845

Offset: 4

Nick Hobson, Nov 30 2006

Always an integer for primes > 5.

			The quadratic residues of 7=prime(4) are 1, 2 and 4. Hence a(4) = (1^2 + 2^2 + 4^2)/7 = 3.

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

Nick Hobson, Table of n, a(n) for n = 4..1003

Cf. A076409, A076410, A125613-A125618.

Table[Total[ResourceFunction["QuadraticResidues"][Prime[n]]^2/Prime[n]], {n,4, 50}] (* James C. McMahon, Dec 19 2024 *)

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

a(n) = A125613(n)/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

A088144 Sum of primitive roots of n-th prime.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

A125615 Sum of the quadratic nonresidues of prime(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A125613 Sum of the squares of the quadratic residues of prime(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

A125618 (Sum of the squares of the quadratic nonresidues of prime(n)) / prime(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

A165951 a(n) = (Sum of the quadratic non-residues of prime(n) - Sum of the quadratic residues of prime(n)) / prime(n).

Views