A076409 -id:A076409 - cp's OEIS frontend

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

1, 1, 5, 7, 27, 22, 39, 15, 68, 76, 63, 92, 250, 117, 203, 186, 165, 175, 333, 156, 410, 430, 270, 423, 1029, 357, 689, 440, 513, 767, 915, 504, 780, 1072, 759, 994, 1314, 725, 1155, 1343, 2187, 1577, 1360, 957, 1958, 1547, 1395, 1330, 2328, 1485, 2525

Offset: 0

Antti Karttunen, Oct 13 2009. Erroneous name corrected Oct 20 2009

nonn

Note that this sequence is not equal to the sum of the quadratic residues of 2n+1 in range [1,2n+1], and thus NOT a bisection of A165898.

			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) getting value 1 when i=1, 3, 4, 5 and 9, thus a(5)=22.

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

A076409(n)=a(A102781(n)). Cf. A166101-A166104, A166405, A166406.

Scheme-code for jacobi-symbol is given at A165601.

Table[Total[Flatten[Position[JacobiSymbol[Range[2n+1],2n+1],1]]],{n,0,50}] (* Harvey P. Dale, Jun 19 2013 *)

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

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

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)

A177860 Product of the quadratic residues of prime(n).

Original entry on oeis.org

1, 1, 4, 8, 540, 12960, 1797120, 22619520, 465813504, 267346759680000, 216218419200000, 199658024013127680000, 136256285631578112000000, 12446179270879850496000000, 34611344543529418987929600

Offset: 1

Jonathan Sondow, May 14 2010

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

			The quadratic residues of prime(4) = 7 are 1, 2, and 4, so a(4) = 1*2*4 = 8.

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

Cf. A076409 Sum of the quadratic residues of prime(n), A177861 Product of the quadratic nonresidues of prime(n), A163366 Product of the quadratic residues 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)!/A177861(n), where p = prime(n).

A232505 Sum of odd quadratic residues of prime(n).

Original entry on oeis.org

1, 1, 1, 1, 18, 13, 38, 50, 26, 83, 66, 137, 224, 242, 147, 303, 509, 395, 578, 364, 714, 563, 965, 1046, 1254, 1155, 1043, 1565, 1323, 1676, 1667, 2440, 2456, 2589, 2563, 2284, 2827, 3362, 2526, 3503, 4408, 3765, 3271, 4902, 4557, 4005, 5829, 5380, 6952, 6093, 7046, 5288, 7626, 8691, 8552, 6871, 8563, 7622, 9007, 10250, 10365, 10233

Offset: 1

Jon Perry, Nov 25 2013

nonn

Seems to have no modular form.

			a(1), a(2), a(3) and a(4) are all 1, as for the corresponding primes 2, 3, 5 and 7 the quadratic residue sets are {1}, {1}, {1,4} and {1,2,4}, in which all cases, only 1 is an odd residue.
For a(5), which is computed for the 5th prime, 11, we have a set of its quadratic residues (those less than 11) as {1,3,4,5,9}, of which when we sum only the odd residues, 1+3+5+9, we get a(5) = 18.

Indranil Ghosh, Table of n, a(n) for n = 1..1000
Wikipedia, Quadratic residue

Cf. A076409, A232597.

Table[Function[p, Total@ Select[Range[1, p, 2], JacobiSymbol[#, p] == 1 &]]@ Prime@ n, {n, 62}] (* Michael De Vlieger, May 14 2017 *)

A232597(n) = {s=0; for(k=1, n, s=s+((k%2)*((1+kronecker(k, n))\2)*k)); return(s); }
forprime (i=1, 300, print1(A232597(i), ", ")) \\ Antti Karttunen, Nov 26 2013

from sympy.ntheory.residue_ntheory import quadratic_residues as q
from sympy import prime
def a(n): return sum(i for i in q(prime(n)) if i%2)
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, May 14 2017

a(n) = A232597(A000040(n)). - Antti Karttunen, Nov 26 2013

Missing 1 (as a(1) is value for the first prime, 2) inserted into beginning by Antti Karttunen, Nov 26 2013

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

A380790 Length of the n-th Golomb ruler constructed by the Paul Erdős and Pál Turán formula.

Original entry on oeis.org

20, 110, 308, 1254, 2106, 4760, 6650, 11822, 23954, 29202, 49950, 68060, 78518, 102460, 147446, 203432, 225090, 298418, 354858, 386316, 489484, 568052, 700964, 907920, 1025150, 1086856, 1218944, 1289034, 1436456, 2039620, 2238790, 2561900, 2675472, 3296774, 3430418

Offset: 2

Darío Clavijo, Feb 03 2025

nonn

In October of 1941 Paul Erdős and Pál Turán found that a Golomb ruler could be constructed for every odd prime p.
Such a ruler has the property that the mark or notches are defined by: notch(k) = 2pk + (k^2 mod p) for k in {0..p-1}, with p=A000040(n).
Empirical observation: a(n) satisfies p^3-p^2 <= a(n)/p^3 <= 0.9999.
Except for n=2, a(n) is divisible by p.
Also partial sums of A217793.

			 n | p  | Golomb ruler notches                             | a(n)
---+----+--------------------------------------------------+-------
 2 | 3  | 0, 7,  13                                        | 20
 3 | 5  | 0, 11, 24, 34, 41                                | 110
 4 | 7  | 0, 15, 32, 44, 58, 74,  85                       | 308
 5 | 11 | 0, 23, 48, 75, 93, 113, 135, 159, 185, 202, 221  | 1254

P. Erdös and P. Turán, On a Problem of Sidon in Additive Number Theory, and on some Related Problems, Journal of the London Mathematical Society, Volume s1-16, Issue 4, October 1941, Pages 212-215.
Wikipedia, Golomb ruler
Index entries for sequences related to Golomb rulers

Cf. A000010, A000040, A000330, A048153, A076409, A100104, A127921, A135177, A160378, A217793.

a(n)= if(n==2, return(20));  my(p=prime(n)); if(bitand(p, 3)==1, return((p*(p-1)*(2*p+1))/2)); if(bitand(p, 3)==3, return((p*(p-1)*(2*p+1))/2 - p * qfbclassno(-p)));

from sympy import prime
from math import isqrt
def a(n):
  p = prime(n)
  if p & 3 == 1: return (p*(p-1)*(2*p+1))//2
  m = isqrt(p-1)
  return (p-1) * p**2 + (m*(m+1)*(2*m+1))//6 + sum(pow(k,2,p) for k in range(m+1,p))
print([a(n) for n in range(2, 37) ])

a(n) = Sum_{k=0..p-1} (2*k*p + k^2 mod p), where p is the n-th prime.
a(n) = (p-1)*p^2 + 1 + Sum_{k=2..p-1} (k^2 mod p), where p is the n-th prime.
a(n) = (p-1)*p^2 + A000330(m) + Sum_{k=m+1..p-1} (k^2 mod p), where m = floor(sqrt(p-1)) and p is the n-th prime.
a(n) = (p-1)*p^2 + p*(p-1)*(p+1)/12 - 2*p*(Sum_{k=1..(p-1)/2} floor(k^2/p)), where p is the n-th prime.
a(n) = A100104(A000040(n)) + A048153(A000040(n)) - 1.
a(n) = A100104(A000040(n)) + A076409(n).
a(n) = A160378(A000040(n)), iif A000040(n) = 1 (mod 4).
a(n) = A160378(A000040(n)) - A000040(n)*A355879(n), iif A000040(n) = 3 (mod 4).
a(n) < A000040(n)^3.
a(n) > A000040(n)^3 - A000040(n)^2.
a(n) = 0 mod A000040(n) for n >= 3.
a(n) = Sum_{k=0..A000040(n)-1} A217793(n - 1, k).
a(n) = A135177(n) + A127921(n) - 2*p*(Sum_{k=1..(p-1)/2} floor(k^2/p)), where p = A000040(n).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

A177860 Product of the quadratic residues of prime(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A232505 Sum of odd quadratic residues of prime(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

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

Views

Author

Keywords