Euclid’s proof that the set of primes is infinite is well known.
Given primes p1, … pk, let N = p1…pk+1. Then no prime factor of N is in the list p1, … pk.
Some years ago, Steve Donkin set a challenge to the students which is based on turning this into an algorithm:
Start with any prime p1. For k = 1,2,…, let pk+1 be the smallest prime factor of p1…pk+1. This generates an infinite sequence of primes.
Problem: Does the prime 3 always occur in the sequence?
One might ask more generally whether every prime occurs in the sequence. The answer for 2 is straightforward, but I do not know about any other prime.
John Bray has done some computations on this. He observed the following on the primes he examined:
It appears that, for n ≥ 4, the number of primes (up to a given bound) for which 3 has not occurred by the (n+1)st stage is smaller than 1/3 of the number for which 3 has not occurred by the nth stage (provided these numbers are not zero).
(Added later) For example, among the primes up to 2×106, the numbers for which 3 occurs at step 3, 4, 5, … 12 are 74412, 50600, 17070, 4859, 1402, 443, 107, 31, 6, 1 respectively. The prime requiring 12 steps is 1572149.
Does anyone have any thoughts about either of these questions?