HMMT-Feb 2023 guts, Problem 34

The number 2027 is prime. For $i=1,2, \ldots, 2026$, let $p_{i}$ be the smallest prime number such that $p_{i} \equiv i(\bmod 2027)$. Estimate $\max \left(p_{1}, \ldots, p_{2026}\right)$. Submit a positive integer $E$. If the correct answer is $A$, you will receive $\left\lfloor 25 \min \left((E / A)^{8},(A / E)^{8}\right)\right\rfloor$ points. (If you do not submit a positive integer, you will receive zero points for this question.)

Solution: Solution: In this solution, all logs are in base $e$. Let $p_{1}, p_{2}, \ldots$ be the primes in sorted order. Let $q_{i}=p_{i} \bmod 2027$. Since the residues of primes modulo 2027 should be uniformly distributed, we can make the probabilistic approximation that the $q_{i}$ are random variables uniformly distributed among $1, \ldots, 2026$. This becomes the famous "coupon collector" problem: the random variables $q_{i}$ are coupons with 2026 different types, and we keep collecting coupons until we have encountered one of each type. In other words, we seek to find the smallest $k$ such that $\left\{q_{1}, \ldots, q_{k}\right\}=\{1, \ldots, 2026\}$, and then the answer to the problem is $p_{k}$. It is known that the expected value of $k$ is $2026\left(\frac{1}{1}+\frac{1}{2}+\cdots+\frac{1}{2026}\right) \approx 2026 \log 2026$. This is because we must draw an expected $\frac{2026}{2026}$ coupons until we get our first distinct coupon type, then an expected $\frac{2026}{2025}$ coupons until we get our second new coupon type, and so on. The standard deviation of $k$ is a small fraction of its its expectation, so we can safely assume that $k$ is approximately $2026 \log 2026$. Since the $n$-th prime is approximately $n \log n$, our estimate is \[ \begin{aligned} E & \approx 2026 \log 2026 \log (2026 \log 2026) \\ & \approx 2026 \log ^{2} 2026 \\ & \approx 117448 \end{aligned} \] This achieves $A / E \approx 0.969$, which scores 19 out of 25 points. $\fbox{113779}$.

Answer: 113779