This is a passing curiosity, and I haven't found any duplicates, so I thought I'd share my thoughts.

In the most basic (or at least the most famous) proof of the infinitude of prime numbers, due to Euclid, we have a finite set $\mathcal{P}_n = \{ p_1, \dots, p_n \}$ of primes and note that $p_1 \cdots p_n + 1$ must have a prime factor not in $\mathcal{P}_n$. (In fact, no prime factors of $p_1 \cdots p_n + 1$ lie in $\mathcal{P}_n$.)

Suppose we set $p_1=2$ and, given $\mathcal{P}_n$, we choose $p_{n+1}$ to be the smallest prime dividing $p_1 \cdots p_n + 1$. I'm interested in finding out how many primes are picked up by this algorithm.

Specifically, for each $n$ let $m_n$ be the largest prime in $\mathcal{P}_n$, and suppose $m_n$ is the $k_n^{\text{th}}$ smallest prime. I'm interested in finding the asymptotic behaviour of $k_n$ as $n \to \infty$. For instance, $\dfrac{n}{k_n}$ is the proportion of primes less than the largest prime picked so far which are accounted for after $n$ primes have been picked.

Here are a few values:

$$\begin{array}{c|c|c|c} n & p_n & m_n & k_n \\ \hline 1 & 2 & 2 & 1 \\ 2 & 3 & 3 & 2 \\ 3 & 7 & 7 & 4 \\ 4 & 43 & 43 & 14 \\ 5 & 13 & 43 & 14 \\ 6 & 53 & 53 & 16 \\ 7 & 5 & 53 & 16 \\ 8 & 6221671 & 6221671 & \approx 397715 \end{array}$$

I'm aware that $k_n \sim \dfrac{m_n}{\log m_n}$ as $n \to \infty$, so knowing how $m_n$ grows with $n$ might also do the trick. I suspect it grows quite fast.

Another thing I'm curious about is whether every prime appears as $p_n$ for some $n$.

Edit: I now know that it's an open problem to find out whether every prime appears as some $p_n$ (I've accepted Pantelis's answer pro tem), and that we barely know any terms in the sequence $(p_n)$, but I'm still interested to find out if any progress has been made in understanding the asymptotic behaviour of these sequences. After all, we understand the asymptotic behaviour of the sequence of primes!

  • 2
    $\begingroup$ As far as I know the last question you asked is open, noone knows if it is true... $\endgroup$ – N. S. Mar 24 '12 at 20:27
  • $\begingroup$ @N.S.: I thought as much! I wonder if the same is true of my first question. $\endgroup$ – Clive Newstead Mar 24 '12 at 20:27
  • $\begingroup$ QUOTE $\mathcal{P}_n = \{ p_1, \dots, p_n \}$ of primes and note that $p_1 \cdots p_n + 1$ must have a prime factor not in $\mathcal{P}_n$ END OF QUOTE. You can say something stronger: $p_1\cdots p_n+1$ must have ALL of its prime factors not in $\mathcal{P}_n$. (Of course, in some cases that means just one.) $\endgroup$ – Michael Hardy Mar 24 '12 at 22:32
  • $\begingroup$ @MichaelHardy: Indeed $-$ in fact I implicitly used this result when I said pick the smallest prime factor. $\endgroup$ – Clive Newstead Mar 24 '12 at 22:37
  • 7
    $\begingroup$ For the record, $p_n$ is known as the Euclid–Mullin sequence (OEIS A000945). $\endgroup$ – jwodder Mar 25 '12 at 0:06

This is a conjecture due to Dan Shanks or maybe Mullin. See the book of Paulo Ribenboim The new Book of Prime number records page 11.

Mullin, A. A., Bull. Amer. Math. Soc., 69, 737 (1963).

Shanks, D. Euclid's primes, Bull. Inst. Combin. Appl., 1, 33-36 (1991).

Look at page 5 of this link to Paulo Ribenboim's The Little Book of Bigger Primes.

  • 2
    $\begingroup$ What was the conjecture? All I can find is a conjecture which is about gaps between primes rather than what I'm asking, where $p_n$ refers not to the $n$th prime ordered by size, but to the $n$th prime obtained using the algorithm in the Euclid's proof of the infinitude of primes. $\endgroup$ – Clive Newstead Mar 24 '12 at 21:50
  • 8
    $\begingroup$ Ribenboim, like many respectable authors, misrepresents Euclid's proof. Euclid's proof was not by contradiction. He said if $P$ is any finite set of primes, the $1+\prod P$ has at least one prime factor not in $P$. The assumption, for the sake of contradiction, that $P$ actually contains all primes, was added by some later authors. $\endgroup$ – Michael Hardy Mar 24 '12 at 22:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.