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?

  • 8
    $\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 '16 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$ – Steven Stadnicki Jun 16 '16 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$ – Gerry Myerson Jun 16 '16 at 23:06
  • 1
    $\begingroup$ The article @GerryMyerson mentioned: Golomb - The evidence for Fortune's conjecture (MSN). $\endgroup$ – LSpice Mar 25 '19 at 18:12

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.


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.