# Is $n! + 1$ often a prime?

Related to another question (If $n = 51! +1$, then find number of primes among $n+1,n+2,\ldots, n+50$), I wonder: How often is $n!+1$ a prime?

There is a related OEIS sequence A002981, however, nothing is said if the sequence is finite or not. Does anybody know more about it?

• The $€100$ question - is it true that $n!+1$ is prime for infinitely many $n$'s. – Nicky Hekster Jul 1 '14 at 9:56
• You would expect there to be an infinite number of them, because if numbers of the form n!+1 were random w.r.t. primality, then the probability of sucha number being prime would be approximately 1/log(n! + 1) which is approximately 1/[n( log(n)-1)], the summation over n to infinity diverges. But these numbers are not exactly random and they are actually more likely to be prime. – Count Iblis Jul 1 '14 at 16:15
• – VividD Jul 2 '14 at 0:34
• Also related is the probability that the primorial plus one is a prime – Jorge Fernández Hidalgo Jan 13 '15 at 15:18

$n! + 1$ is prime for $n = 0, 1, 2, 3, 11, 27, 37, 41, 73, 77, 116, 154, 320, 340, 399, 427, 872, 1477, 6380, 26951, 110059, 150209, \dots$, no other factorial primes are known as of May 2014. See here for more info on factorial primes.

• I'm curious, how did they determine that 150209!+1 is prime? I'd be very interested to know how they determined the primality of 150,000 different million-digit numbers... – CaptainCodeman Jul 1 '14 at 13:21
• Proving that a number p is a prime is easier if you know the complete factorisation of p+1 or p-1. And of course the factorisation of p-1 is known when p = n! + 1. Proving that a general number of that size is prime would be an awful lot more difficult. – gnasher729 Jul 1 '14 at 13:36
• Looking at primes.utm.edu/primes/page.php?id=102627 it looks like that what's Rene Dohmen did, using OpenPFGW. – user153918 Jul 1 '14 at 14:17
• @CaptainCodeman In general (ie excluding cases where an easy option is available), proving a number isn't prime is mostly done using algorithms that have a certain probability of finding a factor if one exists. If those algorithms fail to find a factor after enough iterations that the odds of one existing are very low, a very computationally intensive (on the order of a day of computer time to complete, but better than the naive brute force approach) algorithm is used to do the final proof. primes.utm.edu/prove/prove4.html – Dan Neely Jul 1 '14 at 14:19
• I concur with all the remarks above - there is a slew of algorithms that could help here. See for example en.wikipedia.org/wiki/Category:Integer_factorization_algorithms. The challenge is to find algorithnms that are polynomial in run time. For general purpose factoring, the so-called Elliptic Curve Method (invented by my thesis advisor Hendrik Lenstra) is the third-fastest known factoring method. The second fastest is the multiple polynomial quadratic sieve and the fastest is the general number field sieve. – Nicky Hekster Jul 1 '14 at 14:27

Just looking at the heuristics of the problem:

If you pick a random integer $x$, it will be a prime number with a probability about $1 / \ln x$. Now the number $n! + 1$ is not a random integer. We know that $n! + 1$ is not divisible by any prime number $p ≤ n$. A random large integer is not divisible by any prime $p ≤ n$ with probability $(1-1/2)(1-1/3)(1-1/5)...$ which is about $1 / (2 \ln n)$. So the likelihood that $n! + 1$ is a prime is accordingly higher, about $2 \ln n / \ln (n!)$.

Using the Stirling formula, $\ln (n!)$ is about $n \ln n - n$ or $n(\ln n - 1)$. So $n!+1$ is prime with probability about $(2/n)/(1 - 1 / \ln n)$.

The factor $(1 - 1 / \ln n)$ is quite close to 1; the number of primes of the form $n! + 1$ with $n ≤ M$ is about $2 \ln M$. Very roughly agrees with the list of primes given earlier (I think it is a list of known primes, with many numbers in between not examined).

Such numbers are called factorial primes. There is only limited number of known such numbers.

The largest factorial primes are discovered only recently. From an announcement of an organization called PrimeGrid PRPNet:

On 30 August 2013, PrimeGrid’s PRPNet found the 2nd largest known Factorial prime: $$147855!-1$$ The prime is $700,177$ digits long. The discovery was made by Pietari Snow (Lumiukko) of Finland using an Intel(R) Core(TM) i7 CPU 940 @ 2.93GHz with 6 GB RAM running Linux. This computer took just a little over 69 hours and 37 minutes to complete the primality test.

PrimeGrid is a set of projects based on distributed computing, and devoted to finding primes satisfying various conditions.

Factorial primes-related recent events in PrimeGrid:

$147855!-1$ found: official announcement

$110059!+1$ found: official announcement

$103040!-1$ found: official announcement

$94550!-1$ found: official announcement

Other current PrimeGrid activities:

• 321 Prime Search: searching for mega primes of the form $3·2n±1$.
• Cullen-Woodall Search: searching for mega primes of forms $n·2n+1$ and $n·2n−1$.
• Extended Sierpinski Problem: helping solve the Extended Sierpinski Problem.
• Generalized Fermat Prime Search: searching for megaprimes of the form $b2n+1$.
• Prime Sierpinski Project: helping solve the Prime Sierpinski Problem.
• Proth Prime Search: searching for primes of the form $k·2n+1$.
• Seventeen or Bust: helping to solve the Sierpinski Problem.
• Sierpinski/Riesel Base 5: helping to solve the Sierpinski/Riesel Base 5 Problem.
• Sophie Germain Prime Search: searching for primes $p$ and $2p+1$.
• The Riesel problem: helping to solve the Riesel Problem.