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!

Solution 1:

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.