Solution to puzzle 133: Prime sequence?

A sequence of integers is defined by

• a₀ = 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ⁿ(a₀ + 1).
Substituting a₀ = p, we obtain a_n = 2ⁿp + (2ⁿ − 1).

If p = 2, then a₁ = 5 is prime, and so, without loss of generality, we may assume that p is odd.
Consider a_n 2ⁿ − 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

Back to top