login
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

%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