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

Related to this question, I wonder how often $n!+1$ is a prime?

There is a related OEIS sequence A002981, however, nothing is said if the sequence is finite or not... or anything in that sense...

-
The $€100$ question - is it true that $n!+1$ is prime for infinitely many $n$'s. –  Nicky Hekster Jul 1 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 at 16:15
–  VividD Jul 2 at 0:34

$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 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 at 13:36
Looking at primes.utm.edu/primes/page.php?id=102627 it looks like that what's Rene Dohmen did, using OpenPFGW. –  Alonso del Arte Jul 1 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 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 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).

-

The largest factorial primes are discovered only recently. From an announcement:

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.
-