A prime problem

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

Given primes p1, … pk, let N = p1pk+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 p1pk+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?


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in open problems and tagged , . Bookmark the permalink.

2 Responses to A prime problem

  1. Colin Reid says:

    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.

  2. 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 = 0.3273… . In fact, with enough primes, the eigenvalue tends to 0, by Dirichlet's Theorem.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s