Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
14  
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
    
Related: math.stackexchange.com/questions/20001/… –  VividD Jul 2 at 0:34

3 Answers 3

up vote 35 down vote accepted

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

share|improve this answer
3  
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
7  
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
1  
@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).

share|improve this answer

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.
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.