HMMT 十一月 2022 · THM 赛 · 第 3 题

HMMT November 2022 — THM Round — 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.

解析

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. Proposed by: Maxim Li Answer: 8093 Solution: Let a denote Alice’s number after k seconds, and let p be the smallest prime divisor of k k a . We are given that a is prime, and want to find a . k 2022 0 If a is even, then a = a − 2, since every a is even. Then we need a = 2, so a = 4046. 0 n +1 n n 2022 0 If a is odd, then a = a − p is even, so by similar logic to the even case, a = 4044. Then since 0 1 0 0 1 p | a − p and 4044 = 4 · 3 · 337, we must have p = 3 or 337. But if p = 337, a = 12 · 337+337 = 13 · 337, 0 0 0 0 0 0 so 337 is not the smallest prime divisor of a . Thus, we need p = 3, so a = 4047, which works. 0 0 0 Thus, the final answer is 4046 + 4047 = 8093.