Hacker News Reader

Comment by _Microft | Hacker News Reader

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.

View on HN

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.

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/propI...

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.

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

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.

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.

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

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.

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

Reply on news.ycombinator.com