3 ms·

Isn't "A common misconception about this proof is that the number p_1×p_2×p_3×…×p_n +1 itself has to be prime." plain wrong? They seem to assume that this produ

Isn't "A common misconception about this proof is that the number p_1×p_2×p_3×…×p_n +1 itself has to be prime." plain wrong? They seem to assume that this product generates p_n+1 while it would generate p_m with m >= n + 1 instead, thereby maybe leaving gaps in the sequence (making attempts to use the method again and again to generate all primes unsuccessful). Edit: the counter-example of 2 x 3 x 5 x 7 x 11 x 13 + 1 = 59 * 509 proves this wrong. My mistake.

glial 7y ago
I thought it was wrong -- but looking back at Euclid's proof, Euclid doesn't specify that p_1...p_n be all the primes -- just all the known primes, so there could be gaps. He says that either (1) -- p_1×p_2×p_3×…×p_n +1 is prime, or (2) -- p_1×p_2×p_3×…×p_n +1 is not prime, but it's also not divisible by any of the pre-specified primes, so there must be another prime that divides into it aside from p_1...p_n. See here: https://mathcs.clarku.edu/~djoyce/java/elements/bookIX/propIX20.html https://mathcs.clarku.edu/~djoyce/java/elements/bookIX/propI...
- _Microft 7y ago
  OK, I understand. Strange that the non-successive primes are numbered with successive indices though. PS: Well, actually not because they are not numbering all primes but numbering primes they know.
  - kosievdmerwe 7y ago
    Even if they are successive then the product plus one might not be prime, since the product plus one is so much larger than p_n, there might be a prime that divides it (and likely at least 2). The first non-prime example is 2x3x5x7x11x13 + 1 which equals 59 x 509
    - _Microft 7y ago
      Sure, see my first post about that. I amended it shortly after I posted but it felt wrong to remove the part that people responded too already.
obastani 7y ago
The misconception is that p_1 × p_2 × ... × p_n + 1 has to be prime at all. It can very well be the case that p_1 × p_2 × ... × p_n + 1 is composite.
deleted 7y ago
[deleted]
ummonk 7y ago
Correct statement would be that it generates a product of one or more new primes.
fwip 7y ago
Thanks for the counter example, I had the same concern.
phkahler 7y ago
An interesting variation: if you have the first n primes, partition them in two groups and take the product of all primes in each group. Then take the difference of the two products. This number will not be divisible by any of the primes, and if it is less than the square of the nth prime (and greater than 1) it will be prime. Searching for the partition that produces the lowest difference of products produces the next prime for a short while: 2x5 - 3 = 7 3x7 - 2x5 = 11 11x5 - 2x3x7 = 13 This fails to produce the next prime very soon, but it's slightly interesting.
thechao 7y ago
Here’s a question: if we take the product of the first P prime numbers (we call the product Q), then consider any interval of natural numbers that contain Q, and construct the ratio of non-primes over he size of that interval. We know that the interval (Q-P, P+Q) has a lower bound of nearly 1/2 non-primes, and possibly larger: can we construct a non-Q-like interval with probably larger ratio of non-primes to interval size? The question is about the ratio.

glial 7y ago

I thought it was wrong -- but looking back at Euclid's proof, Euclid doesn't specify that p_1...p_n be all the primes -- just all the known primes, so there could be gaps. He says that either (1) -- p_1×p_2×p_3×…×p_n +1 is prime, or (2) -- p_1×p_2×p_3×…×p_n +1 is not prime, but it's also not divisible by any of the pre-specified primes, so there must be another prime that divides into it aside from p_1...p_n. See here: https://mathcs.clarku.edu/~djoyce/java/elements/bookIX/propIX20.html https://mathcs.clarku.edu/~djoyce/java/elements/bookIX/propI...

_Microft 7y ago
OK, I understand. Strange that the non-successive primes are numbered with successive indices though. PS: Well, actually not because they are not numbering all primes but numbering primes they know.
- kosievdmerwe 7y ago
  Even if they are successive then the product plus one might not be prime, since the product plus one is so much larger than p_n, there might be a prime that divides it (and likely at least 2). The first non-prime example is 2x3x5x7x11x13 + 1 which equals 59 x 509
  - _Microft 7y ago
    Sure, see my first post about that. I amended it shortly after I posted but it felt wrong to remove the part that people responded too already.

obastani 7y ago

The misconception is that p_1 × p_2 × ... × p_n + 1 has to be prime at all. It can very well be the case that p_1 × p_2 × ... × p_n + 1 is composite.

deleted 7y ago

[deleted]

ummonk 7y ago

Correct statement would be that it generates a product of one or more new primes.

fwip 7y ago

Thanks for the counter example, I had the same concern.

phkahler 7y ago

An interesting variation: if you have the first n primes, partition them in two groups and take the product of all primes in each group. Then take the difference of the two products. This number will not be divisible by any of the primes, and if it is less than the square of the nth prime (and greater than 1) it will be prime. Searching for the partition that produces the lowest difference of products produces the next prime for a short while: 2x5 - 3 = 7 3x7 - 2x5 = 11 11x5 - 2x3x7 = 13 This fails to produce the next prime very soon, but it's slightly interesting.

thechao 7y ago

Here’s a question: if we take the product of the first P prime numbers (we call the product Q), then consider any interval of natural numbers that contain Q, and construct the ratio of non-primes over he size of that interval. We know that the interval (Q-P, P+Q) has a lower bound of nearly 1/2 non-primes, and possibly larger: can we construct a non-Q-like interval with probably larger ratio of non-primes to interval size? The question is about the ratio.