

A002189


Pseudosquares: a(n) = the least nonsquare positive integer which is 1 mod 8 and is a (nonzero) quadratic residue modulo the first n odd primes.
(Formerly M5039 N2175 N2326)


15



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,1


REFERENCES

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 "pseudosquares", Math. Tables Other Aids Comp., 8 (1954), 241242.
D. H. Lehmer, E. Lehmer and D. Shanks, Integer sequences having prescribed quadratic character, Math. Comp., 24 (1970), 433451.
R. F. Lukes, C. D. Patterson and H. C. Williams, "Some results on pseudosquares", Mathematics of Computation 65:213 (1996), pp. 361372.
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. 481531 of Mathematics of Computation 19431993 (Vancouver, 1993), Proc. Symp. Appl. Math., Vol. 48, Amer. Math. Soc. 1994.
Kjell Wooding and H. C. Williams, "Doublyfocused 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 "pseudosquares", Math. Tables Other Aids Comp., 8 (1954), 241242. [Annotated scanned copy]
D. H. Lehmer, E. Lehmer and D. Shanks, Integer sequences having prescribed quadratic character, Math. Comp., 24 (1970), 433451 [Annotated scanned copy]
Jonathan P. Sorenson, Sieving for pseudosquares and pseudocubes in parallel using doublyfocused enumeration and wheel datastructures
Eric Weisstein's World of Mathematics, Pseudosquare


EXAMPLE

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


MATHEMATICA

a[n_] := a[n] = (pp = Prime[ Range[2, n+1]]; k = If[ n == 0, 9, a[n1]  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}] (* JeanFranç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 *)


PROG

(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


CROSSREFS

Cf. A018883, A045535, A090983.
Sequence in context: A141972 A161735 A142648 * A002224 A096637 A201610
Adjacent sequences: A002186 A002187 A002188 * A002190 A002191 A002192


KEYWORD

nonn,nice


AUTHOR

N. J. A. Sloane.


EXTENSIONS

The PSAM reference gives a table through p = 223 (the bfile here has many more terms).
More terms from Don Reble, Nov 14 2006
Additional references from Charles R Greathouse IV, Oct 13 2008


STATUS

approved



