Let $k$ be an integer $\geq 3$. Sequence $\{a_n\}$ satisfies that $a_k = 2k$ and for all $n > k$, we have \[a_n = \begin{cases} a_{n-1}+1 & \text{if } (a_{n-1},n) = 1 \\ 2n & \text{if } (a_{n-1},n) > 1 \end{cases} \] Prove that there are infinitely many primes in the sequence $\{a_n - a_{n-1}\}$.
Problem
Source:
Tags: number theory unsolved, number theory
28.11.2010 10:04
Let $a_n=2n$ and $p$ is minimal prime divisor of $n-1=lp$, then $a_{n+i}=2n+i,i<p-1,a_{n+p-1}=2n+2p-2$, because $(a_{n+i-1},n+i)=(2n+i-1,n+i)=(n-1,n+i)=(n-1,i+1)=1$. Therefore $a_{n+p-1}-a_{n+p-2}=p$ is prime.
03.03.2015 12:41
Well I am not sure what the phrase "infinitely many primes" means here.If it means that there infinitely many $n$ such that $a_n-a_{n-1}$ is a prime,then the above proof is alright. But if it means that there are infinitely many "distinct" primes in the sequence,I think then we have to prove this: Define a sequence by $a_0=k$ and $a_{i+1}=a_i+p_i-1$ where $p_i$ is the minimal prime factor of $a_i-1$. Then the set $S=(p_i)$ is not bounded above.
10.05.2016 16:47
mathdebam wrote: Well I am not sure what the phrase "infinitely many primes" means here.If it means that there infinitely many $n$ such that $a_n-a_{n-1}$ is a prime,then the above proof is alright. Yes,his solution is right,we don't need to prove distinct primes according to official solution
15.06.2018 09:25
mathdebam wrote: Well I am not sure what the phrase "infinitely many primes" means here.If it means that there infinitely many $n$ such that $a_n-a_{n-1}$ is a prime,then the above proof is alright. But if it means that there are infinitely many "distinct" primes in the sequence,I think then we have to prove this: Define a sequence by $a_0=k$ and $a_{i+1}=a_i+p_i-1$ where $p_i$ is the minimal prime factor of $a_i-1$. Then the set $S=(p_i)$ is not bounded above. It isn't too hard to show that the set $S=(p_i)$ is not finite. Assume for contradiction it is. Then take $N>p_1$, where $p_1$ is the largest element of $S$. Then consider the set $T={N! - p_1, N! - (p_1-1),...,N!-1}$ Note $a_i$ is equal to one of these terms, since the largest prime in $S$ is $p_1$. So either the smallest prime divisor of such an $a_i$ is not in $S$, in which case we are done, and if it is, note that $a_{i+1}$ is also in the set $T$. But this cannot happen forever sense $a_i$ is strictly increasing, so we eventually get a contradiction.