|
|
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.
(Formerly M5039 N2175 N2326)
|
|
17
|
|
|
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 "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
|
|
|
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[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 *)
|
|
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
|
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
The PSAM reference gives a table through p = 223 (the b-file here has many more terms).
|
|
STATUS
|
approved
|
|
|
|