Pick a positive integer to start a sequence. Now double it, and add one to the result: this is the second number of your sequence. Double that number, and add one, and that will be your third number; repeat the doubling and adding, and you will have a fourth number, and so on.
If you start with a prime number, and you keep doubling and adding one, is it possible to produce a sequence with only prime numbers?
|
|
Submitted by Old Original Oskar!
|
|
Rating: 4.0000 (2 votes)
|
|
|
Solution:
|
(Hide)
|
|
First, let's try p=2; we produce 5, 11, 23, 47, but 95 isn't a prime, so from now on, we can assume p is odd.
If the first number is a(0)=p, we have a(n+1)=2a(n)+1, and it's easy to show that a(n)=p.2^n+(2^n-1).
Consider a(n) modulus p; a(n) is congruent to 2^n-1, so a(p-1) is congruent to 2^(p-1)-1, but applying Fermat's little theorem, 2^(p-1) is congruent to 1 modulus p, so a(p-1) is a multiple of p, so it's not a prime. |
