The sequence p 1 , p 2 ... is defined as follows:
p 1 = 2 and for n ≥ 2 , p n is the largest prime divisor of p 1 p 2 . . . . p n − 1 + 1 . Find the first prime number which is not a member of the sequence.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Before someone corrects me, I didn't mean to write that p n = p 1 p 2 … p n − 1 + 1 . It should actually be that p n = the largest prime divisor of that number..
There is a minor mistake which I had found. Note that the factorization of 5 k − 1 should be ( 4 ) ( 5 k − 1 + 5 k − 2 + . . . 5 + 1 ) . Other than that, nice and concise solution!
Log in to reply
Yes, too bad I can't fix it. At least the proof is still valid.
Problem Loading...
Note Loading...
Set Loading...
Let us compute the first few terms of this sequence:
[ 2 , 3 , 7 , 4 3 , 1 3 9 , 5 0 2 0 7 , … ]
I claim that 5 is the smallest prime that will never be a member of this sequence. What does a 5 in this sequence imply?
p n = p 1 p 2 … p n − 1 + 1 ≡ 0 ( m o d 5 )
And not only this, but 5 would be the largest prime divisor of p n , because of how the sequence is defined. The only other possible prime divisors are 2 and 3, but because p 1 = 2 and p 2 = 3 , we must have that p n ≡ 0 ( m o d 2 , 3 ) . Our number must be a power of 5. Now we will substitute our new information. For some k ∈ N ,
p 1 p 2 … p n − 1 + 1 = 5 k ⇒
p 1 p 2 … p n − 1 = 5 k − 1 = 4 ( 5 k − 1 − 5 k − 2 + 5 k − 3 − ⋯ − 5 + 1 )
We can see that the RHS is divisible by p 1 = 2 , but twice. From this it follows that if we can prove that 2 will not appear again in the sequence, then we will have a contradiction and prove our claim. By similar reasoning, we can do the same thing as before. For some k ∈ N ,
p 1 p 2 … p n − 1 = 2 k − 1
The LHS is divisible by p 1 = 2 , yet the RHS is odd. This is a contradiction, and thus 2 will not appear twice, and then it directly follows that 5 is the smallest prime that will never appear in the defined sequence.