9
$\begingroup$

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?

$\endgroup$
4
  • 10
    $\begingroup$ 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/… $\endgroup$
    – user1073
    Jun 16, 2016 at 21:05
  • 5
    $\begingroup$ 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. $\endgroup$ Jun 16, 2016 at 21:47
  • 6
    $\begingroup$ 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. $\endgroup$ Jun 16, 2016 at 23:06
  • 1
    $\begingroup$ The article @GerryMyerson mentioned: Golomb - The evidence for Fortune's conjecture (MSN). $\endgroup$
    – LSpice
    Mar 25, 2019 at 18:12

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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