Question 161
Given an integer $k \ge 3$ and a sequence $\{a_n\}$ that satisfies $a_k = 2k$ and for each $n \gt k$,
$$
a_n = \begin{cases} a_{n-1} + 1, & \text{if } a_{n-1} \text{ and } n \text{ are coprime,} \\ 2n, & \text{otherwise.} \end{cases}
$$
Prove that $a_n - a_{n-1}$ is a prime for infinitely many $n$. (Posed by Zhu Huawei)
$$
a_n = \begin{cases} a_{n-1} + 1, & \text{if } a_{n-1} \text{ and } n \text{ are coprime,} \\ 2n, & \text{otherwise.} \end{cases}
$$
Prove that $a_n - a_{n-1}$ is a prime for infinitely many $n$. (Posed by Zhu Huawei)