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,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.

Sequence in context: A075572 A089992 A074593 * A255313 A305883 A154800

Adjacent sequences: A144291 A144292 A144293 * A144295 A144296 A144297

Keyword

nonn

Author

N. J. A. Sloane, Dec 03 2008

Status

approved