47
$\begingroup$

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?

$\endgroup$
4
  • 18
    $\begingroup$ The $€100$ question - is it true that $n!+1$ is prime for infinitely many $n$'s. $\endgroup$
    – Nicky Hekster
    Commented Jul 1, 2014 at 9:56
  • 1
    $\begingroup$ 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. $\endgroup$
    – Count Iblis
    Commented Jul 1, 2014 at 16:15
  • $\begingroup$ Related: math.stackexchange.com/questions/20001/… $\endgroup$
    – VividD
    Commented Jul 2, 2014 at 0:34
  • $\begingroup$ Also related is the probability that the primorial plus one is a prime $\endgroup$
    – Asinomás
    Commented Jan 13, 2015 at 15:18

3 Answers 3

Reset to default
43
$\begingroup$

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

$\endgroup$
9
  • 7
    $\begingroup$ 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... $\endgroup$
    – CaptainCodeman
    Commented Jul 1, 2014 at 13:21
  • 15
    $\begingroup$ 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. $\endgroup$
    – gnasher729
    Commented Jul 1, 2014 at 13:36
  • $\begingroup$ Looking at primes.utm.edu/primes/page.php?id=102627 it looks like that what's Rene Dohmen did, using OpenPFGW. $\endgroup$
    – user153918
    Commented Jul 1, 2014 at 14:17
  • 2
    $\begingroup$ @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 $\endgroup$
    – Dan Is Fiddling By Firelight
    Commented Jul 1, 2014 at 14:19
  • 1
    $\begingroup$ 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. $\endgroup$
    – Nicky Hekster
    Commented Jul 1, 2014 at 14:27
20
$\begingroup$

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

$\endgroup$
11
$\begingroup$

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

You must log in to answer this question.

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