A144295 -id:A144295 - cp's OEIS frontend

A144294 Let k = n-th nonsquare = A000037(n); then a(n) = smallest prime p such that k is not a square mod p.

3, 5, 3, 7, 5, 3, 7, 3, 5, 5, 3, 13, 3, 5, 7, 3, 11, 5, 3, 7, 3, 5, 5, 3, 11, 7, 3, 5, 7, 3, 5, 3, 11, 7, 3, 5, 5, 3, 7, 11, 3, 5, 3, 11, 5, 3, 7, 7, 3, 5, 5, 3, 13, 7, 3, 5, 3, 7, 5, 3, 7, 13, 3, 5, 5, 3, 7, 7, 3, 5, 11, 3, 5, 3, 11, 11, 3, 5, 5, 3, 7, 17, 3, 5, 7, 3, 7, 5, 3, 13

Offset: 1

N. J. A. Sloane, Dec 03 2008

nonn

In a posting to the Number Theory List, Oct 15 2008, Kurt Foster remarks that a positive integer M is a square iff M is a quadratic residue mod p for every prime p which does not divide M. He then asks how fast the present sequence grows.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

For records see A144295, A144296. See A092419 for another version.

with(numtheory); f:=proc(n) local M,i,j,k; M:=100000; for i from 2 to M do if legendre(n,ithprime(i)) = -1 then RETURN(ithprime(i)); fi; od; -1; end;

a(n)=my(k=n+(sqrtint(4*n)+1)\2); forprime(p=2,, if(!issquare(Mod(k,p)), return(p))) \\ Charles R Greathouse IV, Aug 28 2016

from math import isqrt
from sympy.ntheory import nextprime, legendre_symbol
def A144294(n):
    k, p = n+(m:=isqrt(n))+(n>=m*(m+1)+1), 2
    while (p:=nextprime(p)):
        if legendre_symbol(k,p)==-1:
            return p # Chai Wah Wu, Oct 20 2024

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.

Original entry on oeis.org

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

A144296 Records in A144294.

Original entry on oeis.org

3, 5, 7, 13, 17, 19, 31, 41, 43, 47, 53, 71, 79, 89, 103, 127, 131, 137

Offset: 1

N. J. A. Sloane, Dec 03 2008

Cf. A144294, A144295.

f(n)=my(k=n+(sqrtint(4*n)+1)\2); forprime(p=2, , if(!issquare(Mod(k, p)), return(p))); \\ A144294
lista(nn) = {my(v=vector(nn, n, f(n))); my(m=0, nm=0); for (n=1, nn, nm = v[n]; if (nm > m, print1(nm, ", "); m = nm;););} \\ Michel Marcus, Jun 25 2021

a(9)-a(12) from R. J. Mathar, Dec 04 2008
a(13)-a(15) from Michel Marcus, Jun 25 2021
a(16)-a(18) from Michael S. Branicky, Sep 30 2024

cp's OEIS Frontend

A144294 Let k = n-th nonsquare = A000037(n); then a(n) = smallest prime p such that k is not a square mod p.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI

Python

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

A144296 Records in A144294.

Views

Author

Keywords

Crossrefs

Programs

PARI

Extensions