# How many primes does Euclid's proof account for?

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!

• As far as I know the last question you asked is open, noone knows if it is true... – N. S. Mar 24 '12 at 20:27
• @N.S.: I thought as much! I wonder if the same is true of my first question. – Clive Newstead Mar 24 '12 at 20:27
• 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.) – Michael Hardy Mar 24 '12 at 22:32
• @MichaelHardy: Indeed $-$ in fact I implicitly used this result when I said pick the smallest prime factor. – Clive Newstead Mar 24 '12 at 22:37
• For the record, $p_n$ is known as the Euclid–Mullin sequence (OEIS A000945). – jwodder Mar 25 '12 at 0:06

• 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. – Clive Newstead Mar 24 '12 at 21:50
• 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. – Michael Hardy Mar 24 '12 at 22:59