A096636 -id:A096636 - cp's OEIS frontend

A377212 a(n) is the least number k that is not a quadratic residue modulo prime(n) but is a quadratic residue modulo all previous primes.

2, 3, 6, 21, 15, 91, 246, 429, 1005, 399, 3094, 3045, 21099, 41155, 43059, 404754, 214230, 569130, 182919, 2190279, 860574, 9361374, 8042479, 33440551, 36915670, 11993466, 287638530, 182528031, 697126530, 78278655, 3263415285, 6941299170, 25856763139, 32968406926, 13803374706

Offset: 2

Robert Israel, Oct 19 2024

nonn

a(n) = A000037(j) for the least j such that A144294(j) = prime(n).

Such numbers k exist for all n >= 2: for example, if x is a quadratic nonresidue modulo prime(n), by the Chinese Remainder Theorem there exists k such that k == x (mod prime(n)) and k == 1 (mod prime(j)) for 1 <= j < n.

			a(4) = 6 because 6 is not a quadratic residue modulo 7, but is a quadratic residue modulo 2, 3, and 5, and no smaller number works.

Cf. A000037, A096636, A144294, A144295.

f:= proc(n) local k,p;
  if issqr(n) then return -1 fi;
  p:= 1;
  for k from 1 do
      p:= nextprime(p);
      if numtheory:-quadres(n,p) = -1 then return k fi
  od
end proc:
V:= Array(2..32): count:= 0:
for k from 2 while count < 31 do
  v:= f(k);
if v > 0 and v <= 32 and V[v] = 0 then
  V[v]:= k; count:= count+1
fi
od:
convert(V,list);

from itertools import count
from math import isqrt
from sympy.ntheory import prime, nextprime, legendre_symbol
def A377212(n):
    p = prime(n)
    for r in count(1):
        k, q = r+(m:=isqrt(r))+(r>=m*(m+1)+1), 2
        while (q:=nextprime(q)):
            if q>p or legendre_symbol(k,q)==-1:
                break
        if p==q:
            return k # Chai Wah Wu, Oct 20 2024

a(33)-a(36) from Chai Wah Wu, Oct 21 2024

A096637 Smallest prime p == 1 mod 8 (A007519) and p > prime(n+2) such that p is a quadratic residue mod the first n odd primes 3, 5, 7, 11, ..., prime(n+1), and p is a quadratic non-residue mod prime(n+2).

Original entry on oeis.org

17, 73, 241, 1009, 2689, 8089, 33049, 53881, 87481, 483289, 515761, 1083289, 7921489, 3818929, 9257329, 22000801, 68204761, 48473881, 175244281, 1149374521, 427733329, 898716289

Offset: 0

Robert G. Wilson v, Jun 24 2004

nonn

Same as smallest prime p == 1 mod 8 with the property that the Legendre symbol (p|q) = 1 for the first n odd primes q = prime(k+1), k = 1, 2, ..., n, and (p|q) = -1 for q = prime(n+2).

Cf. A094928, A002224, A096636.

f[n_] := Block[{k = 2}, While[ JacobiSymbol[n, Prime[k]] == 1, k++ ]; Prime[k]]; t = Table[0, {50}]; Do[p = Prime[n]; If[Mod[p, 8] == 1, a = f[p]; If[ t[[ PrimePi[a]]] == 0, t[[ PrimePi[a]]] = p; Print[ PrimePi[a], " = ", p]]], {n, 10^9}]; t

Better name from Jonathan Sondow, Mar 07 2013

A096638 Smallest prime p == 3 mod 8 (A007520) and p > prime(n+2) such that p is a quadratic residue mod the first n odd primes 3, 5, 7, 11, ..., prime(n+1), and p is a quadratic non-residue mod prime(n+2).

Original entry on oeis.org

11, 43, 19, 211, 331, 2011, 1171, 7459, 10651, 18379, 90931, 257371, 399499, 1234531, 6938779, 3574411, 14669251, 39803611, 102808099, 288710899, 322503091, 465390979, 1582819291, 2410622971, 505313251

Offset: 0

Robert G. Wilson v, Jun 24 2004

nonn

Same as smallest prime p == 3 mod 8 with the property that the Legendre symbol (p|q) = 1 for the first n odd primes q = prime(k+1), k = 1, 2, ..., n, and (p|q) = -1 for q = prime(n+2).

Cf. A096633, A096636.

f[n_] := Block[{k = 2}, While[ JacobiSymbol[n, Prime[k]] == 1, k++ ]; Prime[k]]; t = Table[0, {50}]; Do[p = Prime[n]; If[Mod[p, 8] == 3, a = f[p]; If[ t[[ PrimePi[a]]] == 0, t[[ PrimePi[a]]] = p; Print[ PrimePi[a], " = ", p]]], {n, 10^9}]; t

Better name from Jonathan Sondow, Mar 07 2013

A222756 Smallest prime p > prime(n+2) such that the first n odd primes 3, 5, 7, 11, ..., prime(n+1) are quadratic residues mod p, and prime(n+2) is a quadratic non-residue mod p.

Original entry on oeis.org

5, 13, 11, 59, 421, 131, 1811, 2939, 13381, 12011, 66491, 148139, 275651, 644869, 2269739, 3462229, 6810301, 16145221, 120078131

Offset: 0

T. D. Noe, Mar 06 2013

nonn

Same as smallest prime p such that the Legendre symbol (q|p) = 1 for the first n odd primes q = prime(k+1), k = 1, 2, ..., n, and (q|p) = -1 for q = prime(n+2).

Cf. A096636 (p and q switched).

f[n_] := Block[{k = 2}, While[JacobiSymbol[Prime[k], n] == 1, k++]; Prime[k]]; nn = 15; t = Table[0, {nn}]; t[[1]] = 1; n = 2; While[Min[t] == 0, n++; p = Prime[n]; a = f[p]; ppa = PrimePi[a]; If[ppa <= nn && t[[ppa]] == 0, t[[ppa]] = p]]; Rest[t]

Simpler definition from Jonathan Sondow, Mar 06 2013

A096639 Smallest prime p == 5 mod 8 (A007521) and p > prime(n+2) such that p is a quadratic residue mod the first n odd primes 3, 5, 7, 11, ..., prime(n+1), and p is a quadratic non-residue mod prime(n+2).

Original entry on oeis.org

5, 13, 61, 109, 421, 1621, 7309, 8941, 13381, 82021, 365509, 300301, 1336141, 644869, 8658589, 3462229, 6810301, 16145221, 165163909, 43030381, 163384621, 249623581, 2283397141, 1272463669, 2055693949

Offset: 0

Robert G. Wilson v, Jun 24 2004

nonn

Same as smallest prime p == 5 mod 8 with the property that the Legendre symbol (p|q) = 1 for the first n odd primes q = prime(k+1), k = 1, 2, ..., n, and (p|q) = -1 for q = prime(n+2).

Cf. A096634, A096636.

f[n_] := Block[{k = 2}, While[ JacobiSymbol[n, Prime[k]] == 1, k++ ]; Prime[k]]; t = Table[0, {50}]; Do[p = Prime[n]; If[Mod[p, 8] == 5, a = f[p]; If[ t[[ PrimePi[a]]] == 0, t[[ PrimePi[a]]] = p; Print[ PrimePi[a], " = ", p]]], {n, 10^9}]; t

Better name from Jonathan Sondow, Mar 07 2013

A096640 Smallest prime p == 7 mod 8 (A007521) and p > prime(n+2) such that p is a quadratic residue mod the first n odd primes 3, 5, 7, 11, ..., prime(n+1), and p is a quadratic non-residue mod prime(n+2).

Original entry on oeis.org

23, 7, 31, 79, 631, 751, 2311, 21319, 48799, 82471, 256279, 78439, 1768831, 1365079, 2631511, 1427911, 4355311, 5715319, 49196359, 117678031, 180628639, 475477759, 452980999

Offset: 0

Robert G. Wilson v, Jun 24 2004

nonn

Same as smallest prime p == 7 mod 8 with the property that the Legendre symbol (p|q) = 1 for the first n odd primes q = prime(k+1), k = 1, 2, ..., n, and (p|q) = -1 for q = prime(n+2).

Cf. A096635, A096636.

f[n_] := Block[{k = 2}, While[ JacobiSymbol[n, Prime[k]] == 1, k++ ]; Prime[k]]; t = Table[0, {50}]; Do[p = Prime[n]; If[Mod[p, 8] == 7, a = f[p]; If[ t[[ PrimePi[a]]] == 0, t[[ PrimePi[a]]] = p; Print[ PrimePi[a], " = ", p]]], {n, 10^9}]; t

Better name from Jonathan Sondow, Mar 07 2013

A237436 Least prime p > prime(n+1) such that p is a square mod the first n odd primes 3, 5, 7, 11, ..., prime(n+1).

Original entry on oeis.org

7, 19, 79, 331, 751, 1171, 7459, 10651, 18379, 78439, 78439, 399499, 644869, 1427911, 1427911, 4355311, 5715319, 43030381, 43030381, 163384621

Offset: 1

Jonathan Sondow, Feb 15 2014

nonn

Least prime p > prime(n+1) such that p is a quadratic residue mod the first n odd primes 3, 5, 7, 11, ..., prime(n+1).

Least odd prime p such that the Legendre symbol (p|q) = 1 for q = 3, 5, 7, 11, ..., prime(n+1).

			Let f(p) = list of Legendre (p|q) for q = 3, 5, 7, 11, 13, 17, 19, 23, ...
Then f(p) is
p=3: 0, -1, -1, 1, 1, -1, -1, 1, ...
p=5: -1, 0, -1, 1, -1, -1, 1, -1, ...
p=7: 1, -1, 0, -1, -1, -1, 1, -1, ...
p=11: -1, 1, 1, 0, -1, -1, 1, -1, ...
p=13: 1, -1, -1, -1, 0, 1, -1, 1, ...
p=17: -1, -1, -1, -1, 1, 0, 1, -1, ...
p=19: 1, 1, -1, -1, -1, 1, 0, -1, ...
f(7) is the first list that begins with 1, so a(1) = 7.
f(19) is the first list that begins with 1, 1, so a(2) = 19.

Wikipedia, Legendre symbol
Wikipedia, Quadratic residue

Cf. A222756 (p and q switched), A237437.

Table[p = Prime[n+2]; While[Length[Select[Prime[Range[2, n + 1]], JacobiSymbol[p, #] == 1 &]] < n, p = NextPrime[p]]; p, {n, 1, 18}]

a(n) = a(n+1) if and only if Legendre (a(n)|prime(n+2)) = 1.
a(n) <= A096636(n).
a(n) < A096636(n) if and only if a(n) = a(n+1).
a(n) = A096636(n) if and only if Legendre (a(n)|prime(n+2)) = -1.

A112304 Least number whose least prime quadratic nonresidue is prime(n).

Original entry on oeis.org

2, 7, 19, 46, 214, 394, 1114, 3994, 3826, 13666, 83554, 22234, 189814, 644869, 1387786, 1427911, 4355311, 5715319, 12807391, 43030381, 64320754, 133826599, 452980999

Offset: 2

T. D. Noe, Sep 02 2005

nonn

In terms of the Legendre symbol (a|p), this sequence can be described as the least number k such that (k|prime(n))=-1 and (k|prime(i))=1 for i=2,..,n-1. Note that a(n) <= A096636(n).

Cf. A096636 (Smallest prime whose least prime quadratic non-residue is prime(n).).

nn=23; a=Table[0, {nn}]; n=0; done=False; While[ !done, n++; i=2; While[i=2 && i<=nn+2 && JacobiSymbol[n, Prime[i]]==-1 && a[[i-1]]==0, a[[i-1]]=n; done=(Times@@a>0)]]; a

A377380 a(n) is the first positive number k such that k is alternately a quadratic residue and nonresidue modulo the first n primes, but not the n+1'th.

Original entry on oeis.org

1, 2, 11, 41, 26, 5, 671, 89, 59, 1181, 1991, 3755, 21521, 34145, 25994, 137885, 61106, 1503029, 2617439, 1008551, 2897081, 22363295, 33603926, 36518450, 79865294, 185914490, 593068985, 2211452939, 2120224529, 1673286179, 2644173521, 1976870465

Offset: 1

Robert Israel, Oct 27 2024

nonn

a(n) == 2 (mod 3) for n >= 2.

			a(3) = 11 because 11 is a quadratic residue mod 2, a nonresidue mod 3, a residue mod 5, but a residue mod 7, and no smaller number works.

Cf. A096636, A377212.

with(numtheory):
N:= 20:
V:= Vector(N): V[1]:= 1: count:= 1:
for x from 2 by 3 while count < N do
  p:= 1:
  for m from 0 do
    p:= nextprime(p);
    if numtheory:-quadres(x,p) <> (-1)^m then break fi;
  od;
  if V[m] = 0 then
    V[m]:= x; count:= count+1;
  fi
od:
convert(V,list);

cp's OEIS Frontend

A377212 a(n) is the least number k that is not a quadratic residue modulo prime(n) but is a quadratic residue modulo all previous primes.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Python

Extensions

A096637 Smallest prime p == 1 mod 8 (A007519) and p > prime(n+2) such that p is a quadratic residue mod the first n odd primes 3, 5, 7, 11, ..., prime(n+1), and p is a quadratic non-residue mod prime(n+2).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Extensions

A096638 Smallest prime p == 3 mod 8 (A007520) and p > prime(n+2) such that p is a quadratic residue mod the first n odd primes 3, 5, 7, 11, ..., prime(n+1), and p is a quadratic non-residue mod prime(n+2).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Extensions

A222756 Smallest prime p > prime(n+2) such that the first n odd primes 3, 5, 7, 11, ..., prime(n+1) are quadratic residues mod p, and prime(n+2) is a quadratic non-residue mod p.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Extensions

A096639 Smallest prime p == 5 mod 8 (A007521) and p > prime(n+2) such that p is a quadratic residue mod the first n odd primes 3, 5, 7, 11, ..., prime(n+1), and p is a quadratic non-residue mod prime(n+2).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Extensions

A096640 Smallest prime p == 7 mod 8 (A007521) and p > prime(n+2) such that p is a quadratic residue mod the first n odd primes 3, 5, 7, 11, ..., prime(n+1), and p is a quadratic non-residue mod prime(n+2).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Extensions

A237436 Least prime p > prime(n+1) such that p is a square mod the first n odd primes 3, 5, 7, 11, ..., prime(n+1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A112304 Least number whose least prime quadratic nonresidue is prime(n).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

A377380 a(n) is the first positive number k such that k is alternately a quadratic residue and nonresidue modulo the first n primes, but not the n+1'th.

Views

Author

Keywords