A sequence of integers is defined by

- a
_{0}= p, where p > 0 is a prime number, - a
_{n+1}= 2a_{n}+ 1, for n = 0, 1, 2, ... .

Is there a value of p such that the sequence consists entirely of prime numbers?

Firstly, we find a closed form solution for a_{n}.

Adding 1 to the recurrence relation, we get a_{n+1} + 1 = 2(a_{n} + 1).

Hence a_{n} + 1 = 2^{n}(a_{0} + 1).

Substituting a_{0} = p, we obtain a_{n} = 2^{n}p + (2^{n} − 1).

If p = 2, then a_{1} = 5 is prime, and so, without loss of generality, we may assume that p is odd.

Consider a_{n} 2^{n} − 1 (modulo p).

Then, since 2 and p are relatively prime, by Fermat's Little Theorem, 2^{p−1} 1 (mod p)._{ }

Hence a_{p−1} 0 (mod p).^{ }

Since a_{p−1} > p, it follows that a_{p−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