The sequence of positive integers $a_1, a_2, \ldots, a_{2025}$ is defined as follows: $a_1=2^{2024}+1$ and $a_{n+1}$ is the greatest prime factor of $a_n^2-1$ for $1 \leq n \leq 2024$. Find the value of $a_{2024}+a_{2025}$.
Problem
Source: Australia MO 2024 P5
Tags: number theory
vsamc
24.02.2024 19:57
The answer is $\boxed{5}$.
Claim: There exists some $k\leq 2024$ for which $a_k \leq 3$.
Proof: Assume the contrary. Suppose that $a_k = p$ for some $k\leq 2023$ and some prime $p > 3$. Then, note that $a_{k+1}$ is the greatest prime factor of $a_k^2 -1 = (p-1)(p+1).$ Since $p$ is odd, we have $a_k^2-1 = 4\left(\frac{p-1}{2}\right)\left(\frac{p+1}{2}\right)$, so $a_{k+1} \leq \frac{p+1}{2} = \frac{a_k+1}{2}.$ Now, note that $a_2$ is the greatest prime factor of $a_1^2 -1 = (a_1-1)(a_1+1) = 2^{2024}(2^{2024}+2) = 2^{2025}(2^{2023}+1),$ so $a_2 \leq 2^{2023}+1$. Applying the above logic to $a_2$, we get that $a_3 \leq \frac{a_2+1}{2} \leq \frac{2^{2023}+2}{2} = 2^{2022}+1$. Similarly, $a_4 \leq 2^{2021} + 1$, $\cdots$, until we get $a_{2024} \leq 2^1+1 = 3$, a contradiction. Thus, there must exist such a $k$. $\square$
Since there exists such a $k$, note that if $a_k = 2$, then $a_{k+1} = 3$, and then $a_{k+2} = 2$, etc., and if $a_k = 3$ instead, then $a_{k+1} = 2$, $a_{k+2} = 3$, etc. So, since $k\leq 2024$, it follows that $(a_{2024}, a_{2025}) = (2, 3)$ or $(a_{2024}, a_{2025}) = (3, 2)$, so either way $a_{2024} + a_{2025} = 5$, as claimed. $\blacksquare$
imagien_bad
24.02.2024 20:46
The answer is $\boxed{5}$. The first case is if all of $a_1, a_2, \ldots, a_{2024}$ are odd. If $a_i$ is odd, then $a_{i+1}$ is at most $\frac{a_i + 1}{2}$. Let $f(x) = \frac{x+1}{2}$. We see that $f(2^k + 1) = 2^{k-1} + 1$. Therefore, $a_{2024} \le f^{2023} (a_1) = 3$, so $a_{2024} = 3$. Thus, $a_{2025} = 2$, so $a_{2024} + a_{2025} = 5$. Now assume that there exists some $k\le 2024$ with $a_k = 2$ (this is the only other possibility as $2$ is the only possible even number in the sequence). Then the sequence after $a_k$ becomes $\{2,3,2,3,\cdots,\}$. Therefore $\{a_{2024}, a_{2025} \} = \{2,3 \}$, so the answer is $5$ in this case also.