HMMT-Nov 2022 thm, Problem 3

Alice is bored in class, so she thinks of a positive integer. Every second after that, she subtracts from her current number its smallest prime divisor, possibly itself. After 2022 seconds, she realizes that her number is prime. Find the sum of all possible values of her initial number.

Solution: Solution: Let $a_{k}$ denote Alice's number after $k$ seconds, and let $p_{k}$ be the smallest prime divisor of $a_{k}$. We are given that $a_{2022}$ is prime, and want to find $a_{0}$. If $a_{0}$ is even, then $a_{n+1}=a_{n}-2$, since every $a_{n}$ is even. Then we need $a_{2022}=2$, so $a_{0}=4046$. If $a_{0}$ is odd, then $a_{1}=a_{0}-p_{0}$ is even, so by similar logic to the even case, $a_{1}=4044$. Then since $p_{0} \mid a_{0}-p_{0}$ and $4044=4 \cdot 3 \cdot 337$, we must have $p_{0}=3$ or 337 . But if $p_{0}=337, a_{0}=12 \cdot 337+337=13 \cdot 337$, so 337 is not the smallest prime divisor of $a_{0}$. Thus, we need $p_{0}=3$, so $a_{0}=4047$, which works. Thus, the final answer is $4046+4047=8093$. $\fbox{8093}$.

Answer: 8093