, 2020

Solution:

Of course, there is no such thing as a uniform random prime. More rigorously, for any $n$, the joint distributions of $\left(\frac{p_{1}}{q}\right), \ldots, \left(\frac{p_{n}}{q}\right)$ where $q$ is a uniform random prime less than $N$ converges in distribution to $n$ independent coin flips between 1 and -1 as $N \rightarrow \infty$. For ease of explanation, we won't adopt this more formal view, but it is possible to make the following argument rigorous by looking at primes $q<N$ and sending $N \rightarrow \infty$. Given any $n$, the residue of $q \bmod n$ is uniform over the $\varphi(n)$ residues $\bmod n$ that are relatively prime to $n$. By quadratic reciprocity, conditioned on either $q \equiv 1(\bmod 4)$ or $q \equiv 3(\bmod 4)$, exactly half of the nonzero residues $\bmod p_{n}$ satisfy $\left(\frac{p_{n}}{q}\right)=1$ and exactly half satisfy $\left(\frac{p_{n}}{q}\right)=-1$ for odd $p_{n}$ (the case of $p_{n}=2$ is slightly different and one must look mod 8, but the result is the same). The residue of $q \bmod 8, p_{2}, p_{3}, \ldots, p_{n}$ are independent as these are pairwise relatively prime, yielding our heuristic.

Thus, we may model our problem of finding the smallest quadratic nonresidue with the following process: independent fair coins are flipped for each prime, and we take the smallest prime that flipped heads. We can estimate the expected value of $f(p)^{2}$ as $\sum_{n=1}^{\infty} \frac{p_{n}^{2}}{2^{n}}$. Looking at the first few terms gives us
$$\frac{2^{2}}{2}+\frac{3^{2}}{4}+\frac{5^{2}}{8}+\frac{7^{2}}{16}+\frac{11^{2}}{32}+\frac{13^{2}}{64}+\frac{17^{2}}{128}+\frac{19^{2}}{256}+\frac{23^{2}}{512}+\frac{29^{2}}{1024} \approx 22$$
The terms after this decay rapidly, so a good approximation is $E=22 \cdot 10^{5}$, good enough for 20 points. The more inaccurate $E=20 \cdot 10^{5}$ earns 15 points.

This Python code computes the exact answer:

```
def smallest_nqr(p):
for a in range(1, p):
if pow(a, (p-1)//2, p) == p-1:
return a
import sympy
print(sum([smallest_nqr(p) 2 for p in sympy.ntheory.primerange(3, sympy.prime(105+2))]))
```