# Infinitely many primes coming from Euclid's proof

When teaching Euclid's classic proof of the infinitude of primes today, the following question appeared to me. Let $p_1,p_2,p_3,\ldots$ be the prime numbers, listed in increasing order. Set

$$k_n = p_1 p_2 \cdots p_n + 1.$$

The numbers $k_n$ do not need to be prime, but they seem to be remarkably often. In particular, the first non-prime is

$$k_6 = (2)(3)(5)(7)(11)(13)+1 = 30031 = (59)(509).$$

Question: are infinitely many of the $k_n$ prime? My guess is that this is wide open; if it is, what do the usual heuristics for primes tell us we should expect?

• As you surmised, this problem is wide open. The following paper (Section 2.1) provides a heuristic for why the number of primes of the form $p_1\cdots p_n+1$ with $p_n\leq N$ should be approximately $e^\gamma \log(N)$: ams.org/journals/mcom/2002-71-237/S0025-5718-01-01315-1/… – user1073 Jun 16 '16 at 21:05
• I wouldn't call that 'remarkably often' - e.g., $k_5$ is of size approximately $2300$ and not divisible by any factors $\lt 13$; we'd 'expect' a number that big with no small factors to be prime more than 60% of the time. – Steven Stadnicki Jun 16 '16 at 21:47
• Solomon Golomb, The evidence for Fortune's conjecture, Math Mag 54 (1981) 209-210, wrote that the only known prime values occur for $1\le n\le5$ and $n=11$. He also wrote, "When asked by a student whether $k_n$ is prime for infinitely many values of $n$, George Polya is reported to have replied, 'There are many questions which fools can ask that wise men cannot answer.'" A bit harsh, perhaps. oeis.org/A014545 goes beyond $n=11$ and says it's prime for these $n$: 0, 1, 2, 3, 4, 5, 11, 75, 171, 172, 384, 457, 616, 643, 1391, 1613, 2122, 2647, 2673, 4413, 13494, 31260, 33237. – Gerry Myerson Jun 16 '16 at 23:06
• The article @GerryMyerson mentioned: Golomb - The evidence for Fortune's conjecture (MSN). – LSpice Mar 25 '19 at 18:12

## 1 Answer

The following pages provides some basics about this topic, as well as some references that might be helpful: http://mathworld.wolfram.com/EuclidNumber.html and https://en.wikipedia.org/wiki/Euclid_number.