# 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!

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.

• what is mean that "recursion is reversible"? And if we fix the sequence ${x_i} (mod p)$ there will be finitely many entries which are divisible by p. So, there initially can't be infinitely many entries which are divisible by p. – alexhak May 13 '18 at 12:28
• Saying a recursion is reversible means that given enough of the succeeding terms we can compute the term which preceded them (this is where we use the fact that $p$ doesn't divide the coefficients). I don't understand your second concern...say the period is $\psi$ and that $x_i\equiv 0 \pmod p$ then $x_{i+n\psi}\equiv 0 \pmod p$ for all $n$. – lulu May 13 '18 at 12:31
• My second concern is about "there must be infinitely many entries in the sequence which are divisible by p". Why is it so? – alexhak May 13 '18 at 12:44
• For the reason I said. Read over my last comment carefully. – lulu May 13 '18 at 12:44
• Do you know how to solve this problem click here? – alexhak May 13 '18 at 17:58

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.