For any positive integer $a > 1$, we define the sequence $(a_n)$ as follows: $a_{n+1} = a_n + d(a_n) - 1$, $n \in \mathbb{N}$, $a_1 = a$, where $d(b)$ denotes the smallest prime divisor of $b$. Prove that for any positive integer $k$, the sequence $d(a_n)$ for $n \geq k$ is not increasing, i.e. the condition $d(a_{n+1}) > d(a_n)$ is not true for at least one $n \geq k$. Proposed by Vadym Koval
Problem
Source: Ukrainian Mathematical Olympiad 2021. Day 2, Problem 9.8
Tags: number theory
21.12.2023 19:48
Since $a_{n+1}$ is uniquely determined by $a_n$, it suffices to show for every $a$ that $(a_n)$ is not strictly increasing. Suppose the contrary. So, there is some $a=a_1$ such that $d(a_{n+1})>d(a_n)$ for all $n$. Consider this sequence. Note that $d(m)\le\sqrt m$ iff $m$ is not prime. If there is $n$ such that $a_n=p$ is prime, then $a_{n+1}=2p-1$ is prime as well (suppose not, then $d(a_{n+1})\le\sqrt{2p-1}<p=d(a_n)$, a contradiction). Therefore, by induction, $a_{n+k}=2^k(p-1)+1$ is a prime number for all $k\ge0$. But $p\mid 2^{p-1}(p-1)+1=a_{n+p-1}>a_n=p$, so $a_{n+p-1}$ is not prime. Contradiction. Thus, $a_n$ is never a prime and so $d(a_n)\le\sqrt{a_n}$ for all $n\ge1$. Therefore, $\sqrt{a_{n+1}}\le\sqrt{a_n+\sqrt{a_n}-1}<\sqrt{a_n}+0.5$, so $\sqrt{a_n}<\sqrt{a_1}+0.5(n-1)<0.6n$ for all large enough $n$ and $a_{n+1}-a_n=(\sqrt{a_{n+1}}-\sqrt{a_n})(\sqrt{a_{n+1}}+\sqrt{a_n})<0.5\cdot(0.6(n+1)+0.6n)<0.7n$. Since $(d(a_n))$ is a strictly increasing sequence of integers, $d(a_n)-1>0.9n$ for all large enough $n$. But then $0.9n<d(a_n)-1=a_{n+1}-a_n<0.7n$ for all large enough $n$, so contradiction.
21.12.2023 20:20
very nice problem and solution