# 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. Commented Jul 1, 2014 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. Commented Jul 1, 2014 at 16:15
• Commented Jul 2, 2014 at 0:34
• Also related is the probability that the primorial plus one is a prime Commented Jan 13, 2015 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... Commented Jul 1, 2014 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. Commented Jul 1, 2014 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
Commented Jul 1, 2014 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 Commented Jul 1, 2014 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. Commented Jul 1, 2014 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 a limited number of known such numbers.

The largest factorial primes were 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·2^n±1$$.
• Cullen-Woodall Search: searching for mega primes of forms $$n·2^n+1$$ and $$n·2^n−1$$.
• Extended Sierpinski Problem: helping solve the Extended Sierpinski Problem.
• Generalized Fermat Prime Search: searching for megaprimes of the form $$b2^n+1$$.
• Prime Sierpinski Project: helping solve the Prime Sierpinski Problem.
• Proth Prime Search: searching for primes of the form $$k·2^n+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.
• "The largest (known) factorial primes were discovered only recently." This statement will be true for a very long time, as long as available and affordable computational power grows. Commented Jul 22 at 16:47