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?

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

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .