|
%I M5039 N2175 N2326 #67 Aug 23 2023 08:35:26
%S 17,73,241,1009,2641,8089,18001,53881,87481,117049,515761,1083289,
%T 3206641,3818929,9257329,22000801,48473881,48473881,175244281,
%U 427733329,427733329,898716289,2805544681,2805544681,2805544681
%N 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.
%D 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 D. H. Lehmer, A sieve problem on "pseudo-squares", Math. Tables Other Aids Comp., 8 (1954), 241-242.
%D D. H. Lehmer, E. Lehmer and D. Shanks, Integer sequences having prescribed quadratic character, Math. Comp., 24 (1970), 433-451.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence in two entries, N2175 and N2326.).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D 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.
%D 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).
%H Charles R Greathouse IV, <a href="/A002189/b002189.txt">Table of n, a(n) for n = 0..73</a> (from Bernstein link)
%H D. J. Bernstein, <a href="http://cr.yp.to/focus.html">Doubly focused enumeration of locally square polynomial values</a>
%H D. H. Lehmer, <a href="/A002189/a002189_1.pdf">A sieve problem on "pseudo-squares"</a>, Math. Tables Other Aids Comp., 8 (1954), 241-242. [Annotated scanned copy]
%H D. H. Lehmer, E. Lehmer and D. Shanks, <a href="/A002189/a002189.pdf">Integer sequences having prescribed quadratic character</a>, Math. Comp., 24 (1970), 433-451 [Annotated scanned copy]
%H R. F. Lukes, C. D. Patterson and H. C. Williams, <a href="https://doi.org/10.1090/S0025-5718-96-00678-3">Some results on pseudosquares</a>, Mathematics of Computation 65:213 (1996), pp. 361-372.
%H Jonathan P. Sorenson, <a href="http://arxiv.org/abs/1001.3316">Sieving for pseudosquares and pseudocubes in parallel using doubly-focused enumeration and wheel datastructures</a>, arXiv:1001.3316 [math.NT], 2010.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Pseudosquare.html">Pseudosquare</a>
%e 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
%t 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 *)
%t 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 *)
%o (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
%Y Cf. A018883, A045535, A090983.
%K nonn,nice
%O 0,1
%A _N. J. A. Sloane_
%E The PSAM reference gives a table through p = 223 (the b-file here has many more terms).
%E More terms from _Don Reble_, Nov 14 2006
%E Additional references from _Charles R Greathouse IV_, Oct 13 2008
|
