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

%I #12 Oct 21 2024 03:03:44

%S 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,

%T 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,

%U 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

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

%C 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.

%H Charles R Greathouse IV, <a href="/A144294/b144294.txt">Table of n, a(n) for n = 1..10000</a>

%p 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;

%o (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

%o (Python)

%o from math import isqrt

%o from sympy.ntheory import nextprime, legendre_symbol

%o def A144294(n):

%o k, p = n+(m:=isqrt(n))+(n>=m*(m+1)+1), 2

%o while (p:=nextprime(p)):

%o if legendre_symbol(k,p)==-1:

%o return p # _Chai Wah Wu_, Oct 20 2024

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

%K nonn

%O 1,1

%A _N. J. A. Sloane_, Dec 03 2008