News for hackers. Stuff that matters.
Re:A Curious Sequence of Prime Numbers by JadeNB on Sunday May 26, 2019 @04:27PM (#20017285)
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.

Re:A Curious Sequence of Prime Numbers by human20190310 on Sunday May 26, 2019 @04:41PM (#20017371)
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.
Re:A Curious Sequence of Prime Numbers by eridius on Monday May 27, 2019 @12:33AM (#20019468)
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).
Re:A Curious Sequence of Prime Numbers by MaxBarraclough on Sunday May 26, 2019 @06:31PM (#20017991)
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/

Re:A Curious Sequence of Prime Numbers by saagarjha on Sunday May 26, 2019 @06:43PM (#20018047)
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).
Re:A Curious Sequence of Prime Numbers by JadeNB on Sunday May 26, 2019 @07:10PM (#20018155)
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.

Re:A Curious Sequence of Prime Numbers by saagarjha on Sunday May 26, 2019 @07:16PM (#20018196)
Yes, thanks for the correction :) I've fixed it above.
Re:A Curious Sequence of Prime Numbers by userbinator on Sunday May 26, 2019 @07:17PM (#20018202)
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.

Re:A Curious Sequence of Prime Numbers by saagarjha on Sunday May 26, 2019 @07:24PM (#20018246)
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.
Re:A Curious Sequence of Prime Numbers by lifthrasiir on Sunday May 26, 2019 @10:46PM (#20019059)
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).

Re:A Curious Sequence of Prime Numbers by hoseja on Monday May 27, 2019 @04:51AM (#20020500)
Just a typo but 2^(2^5) + 1 is 42946967297, you skipped the fourth digit.
Re:A Curious Sequence of Prime Numbers by ummonk on Sunday May 26, 2019 @07:11PM (#20018162)
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...
Re:A Curious Sequence of Prime Numbers by saagarjha on Sunday May 26, 2019 @07:20PM (#20018225)
> 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.

Re:A Curious Sequence of Prime Numbers by ummonk on Sunday May 26, 2019 @07:51PM (#20018395)
What if I told you you'd very probably just show that the pattern continues to hold for the first 5 n?
Re:A Curious Sequence of Prime Numbers by saagarjha on Sunday May 26, 2019 @09:16PM (#20018737)
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.
Re:A Curious Sequence of Prime Numbers by dmurray on Sunday May 26, 2019 @08:17PM (#20018520)
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!