Producing New Primes

The proof of Euclid's Theorem on the existence of infinitely many prime numbers can be presented as an algorithm to produce new primes given any finite list of known primes. In brief, it works as follows:

1. Initialize the list of known primes to P₁ = 2, and initialize M = 1.
2. Form the integer N = P₁P₂ ... P_M + 1.
3. Factor N, and add the smallest prime factor of N to the list of known primes.
4. Increase M, and go to (2).

Here are the first primes we get from this process. Starting with 2, we form N = 2 + 1 = 3.

Starting with the known primes 2 and 3, we form N = 2x3 + 1 = 7.

Starting with the known primes 2, 3, and 7, we form N = 2x3x7 + 1 = 43.

Starting with the known primes 2, 3, 7, and 43, we form N = 2x3x7x43 + 1 = 1807 = 13x139. Notice that at this step the number N itself is not prime; we really do need to factor N and take one of the factors. In this case, we get 13.

Starting with the known primes 2, 3, 7, 43, and 13, we form N = 2x3x7x43x13 + 1 = 23479 = 53x443. So, the next prime on the list is 53.

Problem: Does every prime number eventually appear on the list of primes produced by this algorithm? If the answer is "yes", then how would you prove it? If the answer is "no", then what is the smallest prime that does not appear on the list?

Problem: In particular, does the prime 5 ever appear? What about the prime 11?

Problem: How often does the construction produce a new prime directly? How often does it produce a composite number that you must factor in order to get a new prime?

[Home Page] [Bioinformatics] [Mathematics] [Creative Efforts]

[HOME] [PREVIOUS] [NEXT] [UP] [DOWN]