A144294 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

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

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;

PROG

(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

CROSSREFS

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