1000th smallest prime

The number of consecutive positive quadratic residues mod $p$ that are less than $p$ is $\frac{p-5}4$ if $p \equiv 1 \pmod 4$ and $\frac{p-3}4$ if $p \equiv 3 \pmod 4.$ So the answer is $\frac{7919-3}4 = \fbox{1979}.$

To prove the general statement about quadratic residues, let $C$ be the number of consecutive quadratic residues. Then consider $\sum_{x=1}^{p-1} \left( \left( \frac{x}{p} \right) + 1 \right) \left( \left( \frac{x+1}{p} \right) + 1 \right).$ Here $\left( \frac{\cdot}{\cdot} \right)$ is the Legendre symbol .

When $x$ and $x+1$ are both quadratic residues, we get $4.$ When one of them is a nonresidue, we get $0.$ There is one more case: when $x=p-1,$ we get $\left( \frac{-1}{p} \right) + 1.$ So the conclusion is that $4C + 1 + \left( \frac{-1}{p} \right) = \sum_{x=1}^{p-1} \left( \left( \frac{x}{p} \right) + 1 \right) \left( \left( \frac{x+1}{p} \right) + 1 \right).$

Expanding the sum on the right gives $4C + 1 + \left( \frac{-1}{p} \right) = \sum_{x=1}^{p-1} \left( \frac{x}{p} \right) \left( \frac{x+1}{p} \right) + \sum_{x=1}^{p-1} \left( \frac{x}{p} \right) + \sum_{x=1}^{p-1} \left( \frac{x+1}{p} \right) + (p-1).$ The second term is $0,$ because there are $\frac{p-1}2$ residues and $\frac{p-1}2$ nonresidues. The third term is $-1,$ because it is the same as the second term, except that it replaces $\left(\frac1{p} \right) = 1$ with $\left(\frac{p}{p} \right) = 0.$ Bringing everything to the left side gives $4C + 3 - p + \left( \frac{-1}{p} \right) = \sum_{x=1}^{p-1} \left( \frac{x}{p} \right) \left( \frac{x+1}{p} \right) = \sum_{x=1}^{p-1} \left( \frac{x^2+x}{p} \right).$ But $\left(\frac{x^2+x}{p}\right) = \left(\frac{x^2}{p}\right)\left(\frac{1+x^{-1}}{p}\right) = \left(\frac{1+x^{-1}}{p}\right).$ As $x$ ranges from $1$ to $p-1,$ so does $x^{-1},$ so $y=1+x^{-1}$ ranges from $2$ to $p.$ We get $4C + 3 - p + \left( \frac{-1}{p} \right) = \sum_{x=1}^{p-1} \left( \frac{1+x^{-1}}{p} \right) = \sum_{y=2}^p \left( \frac{y}{p} \right) = -1.$ So $4C = p-4-\left( \frac{-1}{p} \right),$ which gives the result we had claimed.

This code uses a boolean array, in which it sets the quadratic residue entries to True. It then counts the number of consecutive pairs of positive quadratic residues. It outputs 1979.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

import numpy

p=7919;
bools = numpy.zeros(p);
for x in range(0, p):
    bools[(x**2)%p]=True; 
count=0;
for x in range(1, p-1):
    if bools[x] and bools[x+1]:
        count+=1;
print(count);