Is there a value of p such that the sequence consists entirely of prime numbers?
Firstly, we find a closed form solution for an.
Adding 1 to the recurrence relation, we get an+1 + 1 = 2(an + 1).
Hence an + 1 = 2n(a0 + 1).
Substituting a0 = p, we obtain an = 2np + (2n − 1).
If p = 2, then a1 = 5 is prime, and so, without loss of generality, we may assume that p is odd.
Consider an 2n − 1 (modulo p).
Then, since 2 and p are relatively prime, by Fermat's Little Theorem, 2p−1 1 (mod p).
Hence ap−1 0 (mod p).
Since ap−1 > p, it follows that ap−1 is composite.
Therefore, there is no value of p such that the above sequence consists entirely of prime numbers.
Source: The Art and Craft of Problem Solving (Problem 7.2.13), by Paul Zeitz