Euclid’s proof that the set of primes is infinite is well known.

Given primes *p*_{1}, … *p*_{k}, let *N* = *p*_{1}…*p*_{k}+1. Then no prime factor of *N* is in the list *p*_{1}, … *p*_{k}.

Some years ago, Steve Donkin set a challenge to the students which is based on turning this into an algorithm:

Start with any prime *p*_{1}. For *k* = 1,2,…, let *p*_{k+1} be the smallest prime factor of *p*_{1}…*p*_{k}+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 *n*^{th} stage (provided these numbers are not zero).

(Added later) For example, among the primes up to 2×10^{6}, 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?

### Like this:

Like Loading...

*Related*

##
About Peter Cameron

I count all the things that need to be counted.

If 3 is not contained in the sequence p_1,…,p_{k+1} and k is at least 2, then p_1…p_k + 1 is 2 mod 3, so has a prime divisor that is 2 mod 3. The question is whether at some point the least prime divisor is 2 mod 3, so that p_{k+2} = 3.

I think I can cast some light for John’s observation. I believe it’s essentially due to the occurrence of “small” primes. If enough small primes congruent to 1 mod 3 have appeared in the list, then the probability of the next term being 2 mod 3 becomes great.

We’ll suppose that 3 has not appeared yet in the process p_1,…,p_k, where k>2, and also that that p_k=1 mod 3. By Colin’s observation, this means that p_{k+1} will not be 3. Consider the process as lying in one of the following states:

State A: Neither 7 nor 13 has appeared.

State B: 7 has appeared but 13 has not.

State C: 13 has appeared but 7 has not.

State D: 7 and 13 have both appeared.

Now consider propagating the process to step k+1. Regard it as being “killed” if p_{k+1} = 2 mod 3; otherwise we estimate the transition probabilities between the various states according to a couple of simplifying assumptions:

1. If s has not appeared, then the probability that p_{k+1} = s is given by 1/s * \prod(1-1/q), where the product is over all q in the range 3<q<s which have not appeared.

2. If p_{k+1} is greater than 13 then the probability that it is congruent to 1 mod 3 is 1/2.

It is easy to calculate the transition probabilities for this process. They form a triangular matrix; the eigenvalues are the transition probabilities from each state to itself. The largest is the one for state D, which is 4/5 * 10/11 * 1/2 = 0.3636… .

Now I'm prepared to admit that 0.3636 is not less than 1/3. But we could have kept track of more primes. For instance, using the primes up to 23 would give a process whose largest eigenvalue is 4.10.16.22/2.5.11.17.23 = 0.3273… . In fact, with enough primes, the eigenvalue tends to 0, by Dirichlet's Theorem.