A063987 -id:A063987 - cp's OEIS frontend

A178151 The number of quadratic residues (mod p) less than p/2, where p=prime(n).

1, 1, 2, 4, 3, 4, 6, 7, 7, 9, 9, 10, 12, 14, 13, 19, 15, 18, 21, 18, 22, 25, 22, 24, 25, 28, 31, 27, 28, 34, 40, 34, 39, 37, 41, 39, 42, 47, 43, 52, 45, 54, 48, 49, 54, 57, 59, 64, 57, 58, 67, 60, 73, 64, 72, 67, 73, 69, 70, 75, 73, 81, 87, 78, 79, 87, 84, 94, 87, 88, 99, 96, 93

Offset: 2

T. D. Noe, May 21 2010

nonn

Sequence A063987 lists the quadratic residues (mod p) for each prime p. When p=1 (mod 4), there are an equal number of quadratic residues less than p/2 and greater than p/2. When p=3 (mod 4), there are always more quadratic residues less than p/2 than greater than p/2.

			The quadratic residues of 19, the 8th prime, are 1, 4, 5, 6, 7, 9, 11, 16, 17. Six of these are less than 19/2. Hence a(8)=6.

R. J. Mathar, Table of n, a(n) for n = 2..3132
MathOverflow, Most squares in the first half-interval

Cf. A178152, A178153, A178154

A178151 := proc(n)
    local r,a,p;
    p := ithprime(n) ;
    a := 0 ;
    for r from 1 to p/2 do
        if numtheory[legendre](r,p) =1 then
            a := a+1 ;
        end if;
    end do:
    a;
end proc: # R. J. Mathar, Feb 10 2017

Table[p=Prime[n]; Length[Select[Range[(p-1)/2], JacobiSymbol[ #,p]==1&]], {n,2,100}]

A278579 Quadratic non-residues of 23: numbers n such that Jacobi(n,23) = -1.

Original entry on oeis.org

5, 7, 10, 11, 14, 15, 17, 19, 20, 21, 22, 28, 30, 33, 34, 37, 38, 40, 42, 43, 44, 45, 51, 53, 56, 57, 60, 61, 63, 65, 66, 67, 68, 74, 76, 79, 80, 83, 84, 86, 88, 89, 90, 91, 97, 99, 102, 103, 106, 107, 109, 111, 112, 113, 114, 120, 122, 125, 126, 129, 130, 132, 134, 135, 136, 137, 143, 145, 148, 149

Offset: 1

N. J. A. Sloane, Nov 29 2016

nonn

Important for the study of Ramanujan numbers A000594.

Wilton, John Raymond. "Congruence properties of Ramanujan's function τ(n)." Proceedings of the London Mathematical Society 2.1 (1930): 1-10. See page 1.

Index entries for linear recurrences with constant coefficients, signature (1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1).

Cf. A028736, A000594, A063987, A278580, A028759 (=first 22 terms).

For the primes in this sequence see A191065.

LinearRecurrence[{1,0,0,0,0,0,0,0,0,0,1,-1},{5,7,10,11,14,15,17,19,20,21,22,28},80] (* Harvey P. Dale, Jan 12 2020 *)

From Robert Israel, Nov 30 2016: (Start)
a(n+11) = a(n)+23.
G.f.: (x^11+x^10+x^9+x^8+2*x^7+2*x^6+x^5+3*x^4+x^3+3*x^2+2*x+5)/(x^12-x^11-x+1). (End)

A063988 Triangle in which n-th row gives quadratic non-residues modulo the n-th prime.

Original entry on oeis.org

2, 2, 3, 3, 5, 6, 2, 6, 7, 8, 10, 2, 5, 6, 7, 8, 11, 3, 5, 6, 7, 10, 11, 12, 14, 2, 3, 8, 10, 12, 13, 14, 15, 18, 5, 7, 10, 11, 14, 15, 17, 19, 20, 21, 22, 2, 3, 8, 10, 11, 12, 14, 15, 17, 18, 19, 21, 26, 27, 3, 6, 11, 12, 13, 15, 17, 21, 22, 23, 24, 26, 27, 29, 30, 2, 5, 6, 8, 13, 14

Offset: 2

Suggested by Gary W. Adamson, Sep 18 2001

			Mod the 5th prime, 11, the quadratic residues are 1,3,4,5,9 and the non-residues are 2,6,7,8,10.
Triangle begins:
  2;
  2, 3;
  3, 5, 6;
  2, 6, 7, 8, 10;
  ...

Albert H. Beiler, Recreations in the theory of numbers, New York, Dover, (2nd ed.) 1966. See Table 82 at p. 202.

T. D. Noe, Rows n=2..100 of triangle, flattened

Cf. A063987.

with(numtheory): for n from 1 to 20 do for j from 1 to ithprime(n)-1 do if legendre(j, ithprime(n)) = -1 then printf(`%d,`,j) fi; od: od:

row[n_] := Select[p = Prime[n]; Range[p - 1], JacobiSymbol[#, p] == -1 &]; Table[row[n], {n, 2, 12}] // Flatten (* Jean-François Alcover, Oct 17 2012 *)

residue(n,m)={local(r);r=0;for(i=0,floor(m/2),if(i^2%m==n,r=1));r}
  isA063988(n,m)=!residue(n,prime(m)) \\ Michael B. Porter, May 07 2010

tabf(nn) = {for(n=1, prime(nn), p = prime(n); for (i=2, p-1, if (kronecker(i, p) == -1, print1(i, ", "));); print(););} \\ Michel Marcus, Jul 19 2013

from sympy import jacobi_symbol as J, prime
def a(n):
    p=prime(n)
    return [i for i in range(1, p) if J(i, p)==-1]
print([a(n) for n in range(2, 13)]) # Indranil Ghosh, May 27 2017

More terms from James Sellers, Sep 25 2001

A166715 Irregular triangle read by rows: row n lists nonzero quadratic residues modulo the n-th term of A123239.

Original entry on oeis.org

1, 1, 1, 3, 4, 5, 9, 1, 3, 4, 9, 10, 12, 1, 3, 4, 7, 9, 10, 11, 12, 16, 21, 25, 26, 27, 28, 30, 33, 34, 36, 1, 2, 4, 5, 8, 9, 10, 16, 18, 20, 21, 23, 25, 31, 32, 33, 36, 37, 39, 40, 1, 3, 4, 5, 7, 9, 12, 15, 16, 17, 19, 20, 21, 22, 25, 26, 27

Offset: 1

A.K. Devaraj, Oct 20 2009

			Triangle starts:
1;
1;
1,3,4,5,9;
1,3,4,9,10,12;
...
Modulo A123239(3)=11, the quadratic residues are 1,3,4,5,9.

G. C. Greubel, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Quadratic Residue.

Cf. A046071, A063987, A123239.

MangammalQ[p_]:=Block[{k=3},While[k>2,k=Mod[3k,p]];k!=2];
A123239=Select[Prime[Range[17]],MangammalQ];
A166715=Flatten[Union[Mod[Range[Floor[#/2]]^2,#]]&/@A123239] (* Ray Chandler, Jul 21 2011 *)

Edited by N. J. A. Sloane, Oct 22 2009
Edited by Charles R Greathouse IV, Oct 28 2009
Edited, corrected and extended by Ray Chandler, Jul 21 2011

A178152 The number of quadratic residues (mod p) greater than p/2, where p=prime(n).

Original entry on oeis.org

0, 1, 1, 1, 3, 4, 3, 4, 7, 6, 9, 10, 9, 9, 13, 10, 15, 15, 14, 18, 17, 16, 22, 24, 25, 23, 22, 27, 28, 29, 25, 34, 30, 37, 34, 39, 39, 36, 43, 37, 45, 41, 48, 49, 45, 48, 52, 49, 57, 58, 52, 60, 52, 64, 59, 67, 62, 69, 70, 66, 73, 72, 68, 78, 79, 78, 84, 79, 87, 88, 80, 87, 93, 90

Offset: 2

T. D. Noe, May 21 2010

nonn

Sequence A063987 lists the quadratic residues (mod p) for each prime p. When p=1 (mod 4), there are an equal number of quadratic residues less than p/2 and greater than p/2. When p=3 (mod 4), there are always more quadratic residues less than p/2 than greater than p/2.

			The quadratic residues of 19, the 8th prime, are 1, 4, 5, 6, 7, 9, 11, 16, 17. Three of these are greater than 19/2. Hence a(8)=3.

MathOverflow, Most squares in the first half-interval

Cf. A178151, A178153, A178154

Table[p=Prime[n]; Length[Select[Range[(p+1)/2,p-1], JacobiSymbol[ #,p]==1&]], {n,2,100}]

A248222 Maximal gap between quadratic residues mod n.

Original entry on oeis.org

1, 1, 2, 3, 3, 2, 3, 4, 3, 3, 4, 5, 5, 3, 5, 7, 4, 3, 5, 7, 6, 4, 5, 8, 3, 5, 3, 7, 4, 5, 5, 8, 6, 4, 5, 9, 5, 5, 6, 11, 6, 6, 6, 8, 6, 5, 5, 12, 4, 3, 6, 8, 7, 3, 8, 9, 7, 4, 6, 11, 7, 5, 9, 8, 9, 6, 7, 13, 7, 5, 7, 12, 5, 5, 7, 8, 11, 6, 7, 15, 3, 6, 8, 12, 13, 6, 11, 16, 7, 6

Offset: 1

David W. Wilson and M. F. Hasler, Oct 04 2014

nonn

"Maximal gap between squares mod n" would be a less ambiguous definition.
The definition of quadratic residue modulo a nonprime varies from author to author. Sometimes, even when n is a prime, 0 is not counted as a quadratic residue. In this entry, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n.
See A248376 for the variant with the additional restriction that the residue be coprime to the modulus. - M. F. Hasler, Oct 08 2014

			For n=7, the quadratic residues are all numbers congruent to 0, 1, 2, or 4 (mod 7), so the largest gap of 3 occurs for example between 4 = 2^2 (mod 7) and 7 = 0^2 (mod 7).
For n=16, the quadratic residues are the numbers congruent to 0, 1, 4 or 9 (mod 16), so the largest gap occurs between, e.g., 9 = 3^2 (mod 16) and 16 = 0^2 (mod 16).

K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, Springer, 1982, p. 194. [Requires gcd(q,n)=1 for q to be a quadratic residue mod n.]
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier-North Holland, 1978, p. 45.
G. B. Mathews, Theory of Numbers, 2nd edition. Chelsea, NY, p. 32. [Does not require gcd(q,n)=1.]
Ivan Niven and Herbert S. Zuckerman, An Introduction to the Theory of Numbers, New York: John Wiley, 2nd ed., 1966, p. 69. [Requires gcd(q,n)=1 for q to be a quadratic residue mod n.]
J. V. Uspensky and M. A. Heaslet, Elementary Number Theory, McGraw-Hill, NY, 1939, p. 270. [Does not require gcd(q,n)=1.]

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Quadratic Residue
Wikipedia, Quadratic residue

Cf. A063987, A130290, A088190, A088191, A088192.

(DD(v)=vecextract(v,"^1")-vecextract(v,"^-1")); a(n)=vecmax(DD(select(f->issquare(Mod(f,n)),vector(n*2,i,i))))

Comments and references added by N. J. A. Sloane, Oct 04 2014

A248376 Maximal gap between quadratic residues mod n; here quadratic residues must be coprime to n.

Original entry on oeis.org

1, 2, 3, 4, 3, 6, 4, 8, 3, 8, 4, 12, 5, 8, 12, 8, 4, 6, 5, 12, 12, 8, 6, 24, 3, 8, 3, 16, 4, 18, 5, 8, 12, 8, 13, 12, 5, 10, 15, 32, 6, 24, 6, 16, 12, 12, 6, 24, 4, 8, 18, 20, 7, 6, 13, 32, 15, 10, 6, 48, 7, 10, 12, 8, 13, 24, 7, 16, 18, 20, 8, 24, 5, 10

Offset: 1

David W. Wilson and M. F. Hasler, Oct 05 2014

nonn

The definition of quadratic residue modulo a nonprime varies from author to author. Sometimes, quadratic residues are not required to be coprime to n, cf. A248222 for the corresponding variant of this sequence.

K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, Springer, 1982, p. 194. [Requires gcd(q,n)=1 for q to be a quadratic residue mod n.]
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier-North Holland, 1978, p. 45.
G. B. Mathews, Theory of Numbers, 2nd edition. Chelsea, NY, p. 32. [Does not require gcd(q,n)=1.]
Ivan Niven and Herbert S. Zuckerman, An Introduction to the Theory of Numbers, New York: John Wiley, 2nd ed., 1966, p. 69. [Requires gcd(q,n)=1 for q to be a quadratic residue mod n.]
J. V. Uspensky and M. A. Heaslet, Elementary Number Theory, McGraw-Hill, NY, 1939, p. 270. [Does not require gcd(q,n)=1.]

David W. Wilson, Table of n, a(n) for n = 1..10000
Eric W. Weisstein, MathWorld: Quadratic Residue
Wikipedia, Quadratic residue

Cf. A063987, A130290, A088190, A088191, A088192, A248222.

a(n)={L=m=1;for(i=2,n+1,gcd(i,n)>1&&next;issquare(Mod(i,n))||next;i-L>m&&m=i-L;L=i);m}

A307550 Irregular array of distinct terms read by rows: for n > 0, row n = [r(1),...,r(k)] with r(1) = n^2 (mod prime(n)), r(2) = r(1)^2 (mod prime(n)), ..., r(k) = r(k-1)^2 (mod prime(n)), where r(k) is the last term of the cycle.

Original entry on oeis.org

1, 1, 4, 1, 2, 4, 3, 9, 4, 5, 10, 9, 3, 15, 4, 16, 1, 7, 11, 12, 6, 13, 8, 18, 2, 4, 16, 3, 9, 13, 24, 25, 16, 28, 9, 19, 20, 33, 16, 34, 9, 7, 12, 5, 25, 10, 18, 37, 16, 24, 17, 31, 15, 10, 14, 37, 6, 36, 27, 24, 12, 3, 9, 34, 28, 32, 44, 28, 42, 15, 13, 10

Offset: 1

Michel Lagneau, Apr 14 2019

Consider the map of quadratic residues x -> x^2 (mod prime(n)) with the initial term x = r(1) = n^2 (mod prime(n)) needed to reach the end of the cycle. Row n contains all distinct quadratic residues r(i) such that r(i) = r(j)^2 (mod prime(n)) for some i, j.

The corresponding row lengths are given by the sequence {b(n)} = {1, 1, 2, 2, 4, 3, 4, 2, 10, 4, 4, 6, 6, 6, 11, 12, 28, 5, 10, 3, 4, 12, 20, 12, 5, 21, ...} with b(n) = A307551(n) + 1. We observe the following property: if prime(n) = 2p + 1 with p prime, b(n) = p - 1 if 2 is a primitive root mod p; that is, p is in A001122 (see A141305). Example: b(17) = 28 because prime(17) = 59 = 2*29 + 1 with 28 = 29 - 1, and 2 is a primitive root mod 29.

			Row 5 = [3, 9, 4, 5] because prime(5) = 11, and 3 = 5^2 (mod 11), 9 = 3^2 (mod 11), 4 = 9^2 (mod 11) and 5 = 4^2 (mod 11).
Irregular array starts:
  [1];
  [1];
  [4, 1];
  [2, 4];
  [3, 9, 4, 5];
  [10, 9, 3];
  [15, 4, 16, 1];
   ...

Cf. A000040, A001122, A000224, A046071, A063987, A096008, A141305, A307551.

nn:=30:T:=array(1..280):j:=0 :
for n from 1 to nn do:
p:=ithprime(n):lst0:={}:lst1:={}:ii:=0:r:=n:
for k from 1 to 10^6 while(ii=0) do:
  r1:=irem(r^2,p):lst0:=lst0 union {r1}:j:=j+1:T[j]:=r1:
      if lst0=lst1
       then
        ii:=1:
        else
        r:=r1:lst1:=lst0:
      fi:
     od:
   if lst0 intersect {r1} = {r1}
    then
    j:=j-1:else fi:
od:
print(T):

s[n_] := Module[{p = Prime[n]}, f[x_] := Mod[x^2, p]; Most[NestWhileList[f, f[n], Unequal, All]]]; seq = {}; Do[AppendTo[seq, s[n]], {n, 20}]; seq // Flatten (* Amiram Eldar, Jul 05 2019 *)

A307551 Number of iterations of the map of quadratic residues x -> x^2 (mod prime(n)) with the initial term x = n^2 (mod prime(n)) needed to reach the end of the cycle.

Original entry on oeis.org

0, 0, 1, 1, 3, 2, 3, 1, 9, 3, 3, 5, 5, 5, 10, 11, 27, 4, 9, 2, 3, 11, 19, 11, 4, 20, 7, 51, 17, 2, 5, 11, 9, 10, 35, 19, 11, 5, 81, 13, 10, 3, 35, 6, 21, 29, 11, 35, 27, 18, 27, 7, 5, 99, 7, 129, 65, 35, 10, 2, 22, 9, 23, 19, 13, 38, 19, 8, 171, 27, 13, 177, 59

Offset: 1

Michel Lagneau, Apr 14 2019

nonn

Let L(n) be the number of elements in row n of A307550. Then a(n) = L(n) - 1.

			a(5) = 3 because prime(5) = 11, and 5^2 (mod 11) = 3 -> 3^2 (mod 11) = 9 ->  9^2 (mod 11) = 4 -> 4^2 (mod 11) = 5 with 3 iterations, where 5 is the last term of the cycle.

Cf. A000040, A000224, A046071, A063987, A096008, A307550.

nn:=100:T:=array(1..3000):j:=0 :
for n from 1 to nn do:
p:=ithprime(n):lst0:={}:lst1:={}:ii:=0:r:=n:
for k from 1 to 10^6 while(ii=0) do:
  r1:=irem(r^2,p):lst0:=lst0 union {r1}:j:=j+1:T[j]:=r1:
      if lst0=lst1
       then
        ii:=1: printf(`%d, `,nops(lst0)-1):
        else
        r:=r1:lst1:=lst0:
      fi:
     od:
   if lst0 intersect {r1} = {r1}
    then
    j:=j-1:else fi:
od:

a[n_] := Module[{p = Prime[n]}, f[x_] := Mod[x^2, p]; Length[NestWhileList[f, f[n], Unequal, All]] - 2]; Array[a, 100] (* Amiram Eldar, Jul 05 2019 *)

A373355 Triangle read by rows: T(n, k) = [n - k + 1 || k] where [n || k] is defined below. Ways in which two primes can relate to each other modulo quadratic residue.

Original entry on oeis.org

1, 2, 3, 2, 1, 3, 1, 0, 0, 1, 2, 2, 1, 3, 3, 2, 3, 0, 0, 2, 3, 1, 1, 1, 1, 1, 1, 1, 2, 0, 0, 2, 3, 0, 0, 3, 1, 2, 0, 0, 1, 0, 0, 3, 1, 2, 3, 1, 0, 0, 0, 0, 1, 2, 3, 1, 0, 0, 3, 0, 1, 0, 2, 0, 0, 1, 2, 2, 1, 2, 3, 1, 1, 2, 3, 1, 3, 3, 1, 1, 1, 1, 2, 0, 1, 0, 3, 1, 1, 1, 1

Offset: 1

Peter Luschny, Jun 02 2024

			Triangle starts:
  [ 1] 1;
  [ 2] 2, 3;
  [ 3] 2, 1, 3;
  [ 4] 1, 0, 0, 1;
  [ 5] 2, 2, 1, 3, 3;
  [ 6] 2, 3, 0, 0, 2, 3;
  [ 7] 1, 1, 1, 1, 1, 1, 1;
  [ 8] 2, 0, 0, 2, 3, 0, 0, 3;
  [ 9] 1, 2, 0, 0, 1, 0, 0, 3, 1;
  [10] 2, 3, 1, 0, 0, 0, 0, 1, 2, 3;
  [11] 1, 0, 0, 3, 0, 1, 0, 2, 0, 0, 1;
  [12] 2, 2, 1, 2, 3, 1, 1, 2, 3, 1, 3, 3;

Carl Friedrich Gauss, Vierter Abschnitt. Von den Congruenzen zweiten Grades. Quadratische Reste und Nichtreste. Art. 97, in "Untersuchungen über die höhere Arithmetik", Hrsg. H. Maser, Verlag von Julius Springer, Berlin, 1889.

Cf. A063987, A373223.

QRP := proc(n, k) local QR, p, q, a, b;
   QR := (a, n) -> NumberTheory:-QuadraticResidue(a, n);
   p := ithprime(n); q := ithprime(k);
   a := QR(p, q); b := QR(q, p);
   if a = -1 and b = -1 then return 0 fi;
   if a =  1 and b =  1 then return 1 fi;
   if a =  1 and b = -1 then return 2 fi;
   if a = -1 and b =  1 then return 3 fi;
end: for n from 1 to 12 do lprint([n], seq(QRP(n-k+1, k), k = 1..n)) od;

QR[n_, k_] := Module[{x, y}, If[Reduce[x^2 == n + k*y, {x, y}, Integers] =!= False, 1, -1]];
QRS[n_, k_] := Module[{p = Prime[n], q = Prime[k], a, b}, a = QR[p, q]; b = QR[q, p]; Which[
      a == -1 && b == -1, 0,
      a == 1 && b == 1, 1,
      a == 1 && b == -1, 2,
      a == -1 && b == 1, 3]];
Table[QRS[n - k + 1, k], {n, 1, 13}, {k, 1, n}] // Flatten (* Jean-François Alcover, Oct 08 2024, after Maple program *)

from sympy.ntheory import is_quad_residue, prime
def QR(n, k): return is_quad_residue(n, k)
def QRS(n, k):
    p = prime(n); q = prime(k)
    a = QR(p, q); b = QR(q, p)
    if not a and not b: return 0
    if a and b: return 1
    if a and not b: return 2
    if not a and b: return 3
def T(n, k): return QRS(n - k + 1, k)
for n in range(1, 13): print([n], [T(n, k) for k in range(1, n + 1)])

Let two positive numbers n, k be given. We write (n R k) if two integers x and y exist, such that x^2 = n + k*y, and (n N k) otherwise. If the condition is satisfied n is called a quadratic residue modulo k. We distinguish four cases:
  [n | k] := 0 if (n N k) and (k N n);
  [n | k] := 1 if (n R k) and (k R n);
  [n | k] := 2 if (n R k) and (k N n);
  [n | k] := 3 if (n N k) and (k R n).
We write [n || k] for [prime(n) | prime(k)] and set T(n, k) = [n - k + 1 || k].
Exchanging 2 <-> 3 reverses the rows.

cp's OEIS Frontend

A178151 The number of quadratic residues (mod p) less than p/2, where p=prime(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A278579 Quadratic non-residues of 23: numbers n such that Jacobi(n,23) = -1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

A063988 Triangle in which n-th row gives quadratic non-residues modulo the n-th prime.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Extensions

A166715 Irregular triangle read by rows: row n lists nonzero quadratic residues modulo the n-th term of A123239.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A178152 The number of quadratic residues (mod p) greater than p/2, where p=prime(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A248222 Maximal gap between quadratic residues mod n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Extensions

A248376 Maximal gap between quadratic residues mod n; here quadratic residues must be coprime to n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI