HMMT February

Let $N$ denote $10^{6}$. We count by summing over potential prime factors $p$. For any prime $p>2$, we have that $p \mid n^{2}+1$ for two values of $n$ if $p \equiv 1(\bmod 4)$, and zero values otherwise. Pretending these values are equally likely to be any of $1, \ldots, p$, we expect the number of $n$ corresponding to a $1(\bmod 4)$ prime to be $\min \left(2, \frac{2N}{p}\right)$. The number of primes up to $x$ is, by the Prime Number Theorem $\frac{x}{\log x}$. Assuming around half of the prime numbers are $1(\bmod 4)$, we on average expect some $x$ to be a $1(\bmod 4)$ prime $\frac{1}{2\log x}$ of the time. Approximating by an integral over potential primes $x$ from 1 to $N^{2}$, using our approximations, gives $$\int_{1}^{N^{2}} \min \left(2, \frac{2N}{x}\right) \cdot \frac{dx}{2\log x}$$ We now approximately calculate this integral as follows: $$\begin{aligned} \int_{1}^{N^{2}} \min \left(2, \frac{2N}{x}\right) \cdot \frac{dx}{2\log x} & =\int_{1}^{N} \frac{dx}{\log x}+\int_{N}^{N^{2}} \frac{N}{x\log x} dx \\ & \approx \frac{N}{\log N}+N\left(\log \log \left(N^{2}\right)-\log \log N\right) \\ & =\frac{N}{\log N}+N \log 2 \end{aligned}$$ Here, for the first integral, we estimate $\log x$ on $[1, N]$ by $\log N$, and for the second integral, we use that the antiderivative of $\frac{1}{x\log x}$ is $\log \log x$. Using $\log 2 \approx 0.7$, one can estimate $$\log N=2 \log 1000 \approx 20 \log 2 \approx 14$$ giving a final estimate of $$10^{6}/14+10^{6} \cdot 0.7=771428$$ This estimate yields a score of 15. If one uses the closer estimate $\log 2 \approx 0.69$, one gets the final estimate of 761428, yielding a score of 18.