Skip to main content.

Solution to puzzle 133: Prime sequence?

Skip restatement of puzzle.A sequence of integers is defined by

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 congruent to 2n − 1 (modulo p).
Then, since 2 and p are relatively prime, by Fermat's Little Theorem, 2p−1 congruent to 1 (mod p). 
Hence ap−1 congruent to 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

Back to top