A002189 Pseudo-squares: a(n) = the least nonsquare positive integer which is 1 mod 8 and is a (nonzero) quadratic residue modulo the first n odd primes.

17, 73, 241, 1009, 2641, 8089, 18001, 53881, 87481, 117049, 515761, 1083289, 3206641, 3818929, 9257329, 22000801, 48473881, 48473881, 175244281, 427733329, 427733329, 898716289, 2805544681, 2805544681, 2805544681

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• nice

Comments

To save the reader's time, note that the 1965 article by Atkin does not appear to be related to this sequence. - N. J. A. Sloane, May 10 2025

Examples

			a(0) = 17 since 1 + 8*0 and 1 + 8*1 are squares, 17 = 1 + 8*2 is not and the quadratic residue condition is satisfied vacuosly. - _Michael Somos_, Nov 24 2018
		

References

• A. O. L. Atkin, On pseudo-squares, Proc. London Math. Soc., 14A (1965), 22-27.(See comment above)
• Michael A. Bender, R Chowdhury, A Conway, The I/O Complexity of Computing Prime Tables, In: Kranakis E., Navarro G., Chávez E. (eds) LATIN 2016: Theoretical Informatics. LATIN 2016. Lecture Notes in Computer Science, vol 9644. Springer, Berlin, Heidelberg. See Footnote 9.
• D. H. Lehmer, A sieve problem on "pseudo-squares", Math. Tables Other Aids Comp., 8 (1954), 241-242.
• D. H. Lehmer, E. Lehmer and D. Shanks, Integer sequences having prescribed quadratic character, Math. Comp., 24 (1970), 433-451.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence in two entries, N2175 and N2326.).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• H. C. Williams and Jeffrey Shallit, Factoring integers before computers, pp. 481-531 of Mathematics of Computation 1943-1993 (Vancouver, 1993), Proc. Symp. Appl. Math., Vol. 48, Amer. Math. Soc. 1994.
• Kjell Wooding and H. C. Williams, "Doubly-focused enumeration of pseudosquares and pseudocubes". Proceedings of the 7th International Algorithmic Number Theory Symposium (ANTS VII, 2006).

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 0..73 (from Bernstein link)
• D. J. Bernstein, Doubly focused enumeration of locally square polynomial values
• D. H. Lehmer, A sieve problem on "pseudo-squares", Math. Tables Other Aids Comp., 8 (1954), 241-242. [Annotated scanned copy]
• D. H. Lehmer, E. Lehmer and D. Shanks, Integer sequences having prescribed quadratic character, Math. Comp., 24 (1970), 433-451 [Annotated scanned copy]
• R. F. Lukes, C. D. Patterson and H. C. Williams, Some results on pseudosquares, Mathematics of Computation 65:213 (1996), pp. 361-372.
• Jonathan P. Sorenson, Sieving for pseudosquares and pseudocubes in parallel using doubly-focused enumeration and wheel datastructures, arXiv:1001.3316 [math.NT], 2010.
• Eric Weisstein's World of Mathematics, Pseudosquare

Crossrefs

Cf. A018883, A045535, A090983.

Programs

Mathematica

a[n_] := a[n] = (pp = Prime[ Range[2, n+1]]; k = If[ n == 0, 9, a[n-1] - 8]; While[ True, k += 8; If[ ! IntegerQ[ Sqrt[k]] && If[ Scan[ If[ ! (JacobiSymbol[k, #] == 1 ), Return[ False]] & , pp], , False, True], Break[]]]; k); Table[ Print[ an = a[n]]; an, {n, 0, 24}] (* Jean-François Alcover, Sep 30 2011 *)
a[ n_] := If[ n < 0, 0, Module[{k = If[ n == 0, 9, a[n - 1] - 8]}, While[ True, If[! IntegerQ[Sqrt[k += 8]] && Do[ If[ JacobiSymbol[k, Prime[i]] != 1, Return @ 0], {i, 2, n + 1}] =!= 0, Return @ k]]]]; (* Michael Somos, Nov 24 2018 *)

PARI

a(n)=n=prime(n+1);for(s=4,1e9,forstep(k=(s^2+7)>>3<<3+1, s^2+2*s, 8, forprime(p=3, n, if(kronecker(k,p)<1,next(2)));return(k))) \\ Charles R Greathouse IV, Mar 29 2012

Extensions

The PSAM reference gives a table through p = 223 (the b-file here has many more terms).

More terms from Don Reble, Nov 14 2006

Additional references from Charles R Greathouse IV, Oct 13 2008