8 ms·

A Curious Sequence of Prime Numbers

84 points by headalgorithm 7y ago

JadeNB 7y ago
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 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 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 https://doi.org/10.1090%2FS0002-9904-1963-11017-4). EDIT: Replying to child (https://news.ycombinator.com/item?id=20017324 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.
- deleted 7y ago
  [deleted]
- human20190310 7y ago
  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.
  - eridius 7y ago
    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).
- MaxBarraclough 7y ago
  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/ https://matheducators.stackexchange.com/a/16640/
  - saagarjha 7y ago
    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).
    - JadeNB 7y ago
      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-there-a-simple-example-that-empirical-evidence-is-misleading/16640#comment41945_16640 https://matheducators.stackexchange.com/questions/16636/is-t... and kcrisman's comment https://matheducators.stackexchange.com/questions/16636/is-there-a-simple-example-that-empirical-evidence-is-misleading/16640#comment41973_16640 https://matheducators.stackexchange.com/questions/16636/is-t... on the post linked by your parent.
_Microft 7y ago
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.
pahkah 7y ago
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!
- sp332 7y ago
  Oh thanks, I read it that way too.

84 points by headalgorithm 7y ago

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 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 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 https://doi.org/10.1090%2FS0002-9904-1963-11017-4). EDIT: Replying to child (https://news.ycombinator.com/item?id=20017324 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.

deleted 7y ago
[deleted]
human20190310 7y ago
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.
- eridius 7y ago
  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).
MaxBarraclough 7y ago
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/ https://matheducators.stackexchange.com/a/16640/
- saagarjha 7y ago
  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).
  - JadeNB 7y ago
    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-there-a-simple-example-that-empirical-evidence-is-misleading/16640#comment41945_16640 https://matheducators.stackexchange.com/questions/16636/is-t... and kcrisman's comment https://matheducators.stackexchange.com/questions/16636/is-there-a-simple-example-that-empirical-evidence-is-misleading/16640#comment41973_16640 https://matheducators.stackexchange.com/questions/16636/is-t... on the post linked by your parent.

_Microft 7y ago

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.

pahkah 7y ago

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!

sp332 7y ago
Oh thanks, I read it that way too.