HMMT February Guts Round, 2024

Solution:

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{2 N}{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{2 N}{x}\right) \cdot \frac{d x}{2 \log x}$$
We now approximately calculate this integral as follows:
$$\begin{aligned} \int_{1}^{N^{2}} \min \left(2, \frac{2 N}{x}\right) \cdot \frac{d x}{2 \log x} & =\int_{1}^{N} \frac{d x}{\log x}+\int_{N}^{N^{2}} \frac{N}{x \log x} d x \\ & \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.

Here is a code using sympy to calculate the final answer:
```
from sympy.ntheory import factorint
cnt = 0
for n in range(1, 106+1):
if max(factorint(n2+1, multiple=True)) > n:
cnt += 1
print(cnt)
```