4 ms·
The ’standard’ proof of the infinitude of primes implies that: Given primes p1, p2, …, pn, multiply them, add 1, and factor the result. All its prime factors a
by Someone 3y ago
The ’standard’ proof of the infinitude of primes implies that:
Given primes p1, p2, …, pn, multiply them, add 1, and factor the result. All its prime factors are new primes.
For example, given {5,7,11}, the product is 385. Adding one yields 386.
Factoring that learns you that 386 = 2 × 193. Both are primes not in the original list.
If you start with {}, the series you get is
{} ⇒ 2 = 2
{2} ⇒ 3 = 3
{2,3} ⇒ 7 = 7
{2,3,7} ⇒ 43 = 43
{2,3,7,43} ⇒ 1807 = 13 × 139
{2,3,7,43,13,139} ⇒ 3263443 = 3263443
(https://oeis.org/A126263 https://oeis.org/A126263; i think it doesn’t generate all primes)
- eru 3y agoI would be interested in seeing the list of primes not generated by this process. (I wonder whether you need to be able to factor efficiently to get your hands on that list, or whether there's some way around that.)