HMMT-Nov 2019 thm, Problem 5

Alison is eating 2401 grains of rice for lunch. She eats the rice in a very peculiar manner: every step, if she has only one grain of rice remaining, she eats it. Otherwise, she finds the smallest positive integer $d>1$ for which she can group the rice into equal groups of size $d$ with none left over. She then groups the rice into groups of size $d$, eats one grain from each group, and puts the rice back into a single pile. How many steps does it take her to finish all her rice?

Solution: Note that $2401=7^{4}$. Also, note that the operation is equivalent to replacing $n$ grains of rice with $n \cdot \frac{p-1}{p}$ grains of rice, where $p$ is the smallest prime factor of $n$. Now, suppose that at some moment Alison has $7^{k}$ grains of rice. After each of the next four steps, she will have $6 \cdot 7^{k-1}, 3 \cdot 7^{k-1}, 2 \cdot 7^{k-1}$, and $7^{k-1}$ grains of rice, respectively. Thus, it takes her 4 steps to decrease the number of grains of rice by a factor of 7 given that she starts at a power of 7 . Thus, it will take $4 \cdot 4=16$ steps to reduce everything to $7^{0}=1$ grain of rice, after which it will take one step to eat it. Thus, it takes a total of 17 steps for Alison to eat all of the rice. $\fbox{17}$.

Answer: 17