Note that the smallest quadratic nonresidue $a$ is always a prime, because if $a=b c$ with $b, c>1$ then one of $b$ and $c$ is also a quadratic nonresidue. We apply the following heuristic: if $p_{1}$, $p_{2}, \ldots$ are the primes in increasing order, then given a "uniform random prime" $q$, the values of $\left(\frac{p_{1}}{q}\right),\left(\frac{p_{2}}{q}\right), \ldots$ are independent and are 1 with probability $\frac{1}{2}$ and -1 with probability $\frac{1}{2}$. 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 sympyprint(sum([smallest_nqr(p)2 for p in sympy.ntheory.primerange(3,sympy.prime(105+2))])) Remark. In 1961, Erdős showed that as $N \rightarrow \infty$, the average value of $f(p)$ over odd primes $p<N$ will converge to $\sum_{n=1}^{\infty} \frac{p_{n}}{2^{n}} \approx 3.675$.