Problem

Source: Ukrainian Mathematical Olympiad 2021. Day 2, Problem 9.8

Tags: number theory



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