A Curious Sequence of Prime Numbers | Hacker News Reader

A Curious Sequence of Prime Numbers

blogs.scientificamerican.com

84 pointsheadalgorithm28 comments

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.

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.

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

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.

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.

At first I read

> The similar sequence that chooses the largest instead of smallest prime that divides 1 plus the product of the previous terms avoids an infinite number of primes.

as saying that it avoids having an infinite number of primes in the sequence (i.e. that the sequence itself contained a finite number of distinct primes), but it's actually that there's an infinite number of primes not present in the sequence.

Fascinating sequence, good article, thanks!

Oh thanks, I read it that way too.

A way less interesting comment on the Euclid–Mullin sequence, for anyone who's just learned about it in a math class: it is common to take away the wrong lesson "the product of all the primes so far, plus 1, is always prime." (Even if it's totally obvious to you that this is false, I assure you that it's not obvious to everyone. Sigh, I've also just noticed that, by skipping to the part of the article about interesting unsolved questions, I missed that the author says exactly this. Sorry! Hopefully the rest of the comment is worth something.)

This succeeds for a little while, since (the product of no primes) + 1 is 2, 2 + 1 is 3, 2·3 + 1 is 7, and 2·3·7 + 1 is 43, and most math geeks will recognise these as primes. However, it fails immediately after: 2·3·7·43 + 1 is 13·139. (If you take "all the primes so far" to mean not just "all the primes generated this way" but "all primes less than or equal to those generated this way", then we get a slightly different trajectory: after 7 comes 2·3·5·7 + 1 = 211, which is prime; and then the so-called primorial (https://en.wikipedia.org/wiki/Primorial) 211# has a successor that is huge, way bigger than 2297, but is divisible by 2297.)

It is possible to modify the sequence so that it proveably generates all primes; see, for example, Booker - A variant of the Euclid–Mullin sequence containing every prime (https://arxiv.org/abs/1605.08929). According to Wikipedia, the notion was introduced in Mullin - Recursive function theory (A modern look at a Euclidean idea) (https://doi.org/10.1090%2FS0002-9904-1963-11017-4).

EDIT: Replying to child (https://news.ycombinator.com/item?id=20017324 )—sorry for doing it here; I'm "posting too fast", but don't want to ignore it:

> I'm genuinely confused by this. I don't see how 2·3·7·43 is "the product of all the primes so far", since 11, 13, 17, 19, 23, 29, 31, 37, and 41 are missing.

> Does the author mean "all the primes generated by the sequence", or "all the primes up to a certain number"? I always thought the Euclid method involved the latter.

Just to be clear, I'm not the author of the linked post. I did write "all the primes so far" to mean "all the primes generated in this way", which is the sense in which Mullin used it in the article linked above. Both approaches work to generate 'new' primes, in the sense that they're not among the primes multiplied together; but you must use the primorial if you want to generate new, bigger primes. I edited to take into account the more natural interpretation (see the parenthetical above), but probably it was while you were posting.

I only just now understood that Euclid's method doesn't necessarily generate a prime number; it produces a number that you can't "get to" by multiplying the primes in your list of prime numbers; as such any list of primes is incomplete.

And since you can't "get to" it with your existing list, this means the prime factorization of this new number includes at least one prime not on your list, and therefore you can grow your list with every step (assuming you're capable of prime factorizing arbitrary numbers).

Further off-topic: 1 + 2^(2^n) is prime where n is an element of {0,1,2,3,4}, but not 5. This went unnoticed for a century - Fermat went his life suspecting that it held for all naturals. (Pre-computer days, of course.)

https://matheducators.stackexchange.com/a/16640/

This is a surprisingly small number for it to go unnoticed for a century. I'm pretty sure I wrote up a list of the first 50 or so powers of two to pass time in elementary school: if someone told me to, I could have checked the primality of numbers of the form 2^(2^n)+1 as well (though it'd be somewhat more tedious).

Of course you mean numbers of the form 2^(2^n) + 1; without the increment, primality is easy to check. :-) Anyway, are you sure that it would be so easy to check primality of 15-decimal-digit numbers without even a pocket calculator, especially with no guarantee that there was any reason to do so? (Notice, for example, that you needed to add "if someone told me to".)

For more on this, see KConrad's comment https://matheducators.stackexchange.com/questions/16636/is-t... and kcrisman's comment https://matheducators.stackexchange.com/questions/16636/is-t... on the post linked by your parent.

Yes, thanks for the correction :) I've fixed it above.

Wait, you expect to be able to easily check primality of 2^32 + 1 by hand? Like with a naive algorithm you’d need to use erastothenes sieve to find primes up to 2^16 to test against. Granted, 641 itself is rather small but if you didn’t expect to encounter a factor that early...

> Like with a naive algorithm you’d need to use erastothenes sieve to find primes up to 2^16 to test against.

π(2^16)=6542: if you told me in elementary school that I might disproving something famous I can see myself working on that for a couple of hours daily for a week or so.

What if I told you you'd very probably just show that the pattern continues to hold for the first 5 n?

You’d stifle mathematical innovation: after all, there are quite a few things that have been proved or discovered by people who were fortunate enough to not be told that they were solving a hard problem.

2^(2^5) + 1 is 4296967297 = 641 * 6700417. Not at all a huge number today, but in those days it'd probably be considered "astronomical".

Also, the series 2^(2^n)+1 grows extremely quickly; the next number is 18446744073709551617 = 274177 * 6728042131072, and after that 340282366920938463463374607431768211457 = 59649589127497217 * 5704689200685129054721.

2^32+1 is likely reaching the limits of what an elementary school child is able to do by hand. As for the larger numbers: they do get unwieldy quickly, but I think it might be possible to manually find the factors of them with probabilistic primality testing.

Well, the child will be bored much earlier :-)

For Fermat numbers 2^(2^n) + 1, it is well known that every prime factor should have the form k 2^(n+2) + 1. The sequence (A007117) thus goes like: k = 5 for n = 5 (Euler in 1732, very managable), k = 1071 for n = 6 (Thomas Clausen in 1854) and k = 116503103764643 for n = 7 (only known in 1970 after the modern computer).

Just a typo but 2^(2^5) + 1 is 42946967297, you skipped the fourth digit.

There were so many other more interesting mathematical results to work on back then, that were equally accessible to a bright and motivated schoolchild. Euler and Fermat had it easy!

Reply on news.ycombinator.com