All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Does it continue? 4: Euclid's next prime (Posted on 2017-09-21) Difficulty: 3 of 5
Before trying the problem "note your opinion as to whether the observed pattern is known to continue, known not to continue, or not known at all."

Let P(n)= The product of the first n primes.

P(n)+1 is like Euclid's method to show there are infinitely many primes, and may or not be prime itself. Now look at the difference between P(n) and the next prime after P(n)+1.

n=1, 5-(2)=3
n=2, 11-(2x3)=5
n=3, 37-(2x3x5)=7
n=4, 223-(2x3x5x7)=13
n=5, 2333-(2x3x5x7x11)=23
n=6, 30047-(2x3x5x7x11x13)=17
n=7, 510529-(2x3x5x7x11x13x17)=19
n=8, 9699713-(2x3x5x7x11x13x17x19)=23

Are these differences always prime?

No Solution Yet Submitted by Jer    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Some Thoughts Prediction and result Comment 3 of 3 |

Prediction: Yes, almost certainly.

Result: Well, Charlie didn't find a counter-example.

Why it might be true: Consider how the sequence is constructed, for some small P(n) = p1*p2*p3*...p(n). By construction, P(n) is divisible by every prime used to generate the sequence, so with the exception of P(n)+1 none of the next n numbers can be prime; nor can P(n)+2k, P(n)+3k, P(n)+5k... etc.

In fact, by construction, we know that the very next prime is, say, Q. Plainly Q is not divisible by 2,3,5,...p(n) or it wouldn't be prime. Equally, neither is Q-P(n), since P(n) is divisible by all those small primes. So either Q-P(n) is prime, or it is the product of factors either of which is larger than n.

We call the gap between p(n)+1 and Q, G. We identify the position of p(n)+1 as 1, then p(n)+2 = 2, p(n)+3 = 3, etc. As in the game Mastermind, if each prime up to n divides the position 1,2,3..., then it is a factor of the corresponding entry, warranted not only to divide the entry but to do so in the correct position:

210 2*3*5*7             Position
211 P                             1
212 2*2*53                    2
213 3*71                       3
214 2*107                     4
215 5*43                       5
216 2^3*3^3                6
217 7*31                       7

But for 210, G=13. Since G is greater than 11, 11 must appear as a factor of at least one entry (in fact 220= 2^2*5*11). We can be sure 11 will appear as a factor of at least one entry, but we don't know which; correct, but not necessarily in the correct place. What number appears in its stead? In position 11 is 221 = 13*17, and 13 is the largest least factor in the gap, and also 13 = G.

So in addition to the warranted positions that are already accounted for, the next few primes between n and G must also be accommodated either as a co-factor in a warranted position, or in one of the open prime positions. E.g for 2310:

2310 2*3*5*7*11  
2311 P                   1
2312 2*2*17*17    2
2313 3^2*257       3
2314 2*13*89        4
2315 5*463           5
2316 2^2*3*193    6
2317 7*331            7
2318 2*19*61        8
2319 3*773            9
2320 2^4*5*29     10
2321 11*221         11
2322 2*3^3*43     12
2323 23*101         13
2324 2^2*7*83    14
2325 3*5^2*31     15
2326 2*1163         16
2327 13*179         17
2328 2^3*3*97     18
2329 17*137         19
2330 2*5*233       20
2331 3^2*7*37     21
2332 2^2*11*53   22
2332 P                  23

The positions up to 12 and the compound ones thereafter are all warranted. Position 13 = 2323 23*101,  17 = 13*179, 19 = 17*137, and position 23 is prime. 23 is the largest least factor in the gap, and also 23 = G.

30030 is a little different because 30031 is not prime. In a way, this is simpler, as every position up to G is warranted:

30030 2*3*5*7*11*13  
30031 59*509          1
30032 2^4*1877      2
30033 3^2*47*71    3
30034 2*15017        4
30035 5*6007          5
30036 2^2*3*2503  6
30037 7^2*613        7
30038 2*23*653       8
30039 3*17*19*31   9
30040 2^3*5*751    10
30041 11*2731         11
30042 2*3^2*1669   12
30043 13*2311          13
30044 2^2*7*29*37  14
30045 3*5*2003        15
30046 2*83*181        16
30047 P                    17

So yes, it looks like a good bet that such differences are always prime.

   

 

Edited on September 22, 2017, 1:58 am
  Posted by broll on 2017-09-21 22:47:03

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information