Is the sequence of prime numbers a linear recurrent sequence? A Linear recurrent sequence is $x_{i+m} = a_{m-1}x_{i+m-1} + a_{m-2}x_{i+m-2} + ... + a_1x_{i+1} + a_0x_i$, where m is the order of sequence and $a_i$ is integer.
Is the sequence of prime numbers ${2, 3, 5, 7, 11, 13, 17, 19, 23, ...}$ a linear recurrent sequence? And how can we validate our answer?
Please write the answer in detail!
 A: Suppose otherwise and fix the sequence $\{x_i\}$.
Pick a prime $p$ which doesn't divide any of the $a_i$. Clearly the sequence $\{x_i\}$ is eventually periodic $\pmod p$, as there are only finitely many $m-$tuples of residues $\pmod p$.  since the recursion is reversible it must be periodic from the start.
Since the prime $p$ is included in the sequence, by definition, there must be infinitely many entries in the sequence which are divisible by $p$.  A contradiction.
A: If it were, if all $a_i\geq0$ and $m>0$, then for any $k\in\mathbb N$ there would be an $N\in\mathbb N$ such that for all $n\geq N$ the difference between two primes $p_{n+1}-p_n$ would be greater than $k$.[1] Zhang proved that this is not true, see here. $m=0$ wouldn't work either obviously (As then $x_2=a_0 x_1$ would either be $x_1$ or not prime.)
I do not know how it would be with some $a_i <0$, but my guess is that here is a similar counter argument.
[1] This would also proof the twin prime conjecture false, but there is strong evidence it's true.
