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

Author

N. J. A. Sloane, Dec 03 2008

Keywords

• nonn

Comments

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.

Links

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

Crossrefs

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

Programs

Maple

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;

PARI

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

Python

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