How many consecutive composite integers follow k!+1?

2011-02-02T08:17:47Z

I originally thought this question was too basic for MathOverflow, so I tried Math.StackExchange, but no one there seemed to have a solution. Here goes.

How many consecutive composite integers follow k!+1? I wrote a program in Mathematica to compute explicit answers for the first 300, but there doesn't seem to be much of a pattern. The results of that are here. This is a problem in Underwood Dudley's Elementary Number Theory (section 23.2 part (b)), but for the LIFE of me, I can't figure it out! My initial thought was this: Let m be the smallest prime such that k<m. Then any number of the form k!+i, where 1<i<m will clearly be composite. Hence, there are at least m-2 composite numbers which follow k!+1. However, past that it seems hard to say. For example, 11!+13 factorizes as 199*200587, which seems to be unpredictable behavior. I'm leaning toward thinking this was a misprint in the book and it's a much harder problem than something that should be in Elementary Number Theory. Perhaps I'm overlooking a simple, elegant solution.

The other thing is, if there were a closed-form solution, then we would have an easy formula for calculating arbitrarily large primes. Take the largest known prime p and suppose we determine that q composite numbers follow p!+1. Then p!+2+q is prime.

Answer by Johan Andersson for How many consecutive composite integers follow k!+1?

2011-02-02T14:54:12Z

This seems like an interesting problem. Prime gap problems are notoriously difficult (Compare with Cramer's conjecture) and I do not expect this to be any easier. I will therefore not give a definitive answer, but rather try to give some heuristics. The Cramer model (see for example the paper of Granville "Harald Cramer and the distribution of prime numbers") where we assume that the probability that $n$ is prime is about $1/\log n$ gives that the probability that $k!+j$ should be prime should be about $1/\log(k!)$ which by Stirling's formula is about $1/k \log k$. This would give an average prime gap of about $k\log k$.

One might reason a little bit further. Of course when we consider $k!+j$ for $2 \leq j \leq k$ we have forced these number to be composite. In general the number $k!+j$ will be composite if some prime factor of $j$ is less than $k$. We may then ask what is the probability that the number $j$ has all prime factors greater than $k$? If $k < j < k^2$ this is true if and only if $j$ is prime which has probability about $1/\log j$ which if $k < j < k (\log k)^N$ is about $1/\log k$. One might then expect the probability that the number $k^2+j$ to be prime should be the product of these probabilities or $1/(k(\log k)^2)$.

However then we have not recognized the fact that we have forced the number $k!+j$ to have no prime factor less than $k$. This means that we should look at the conditional probability that an integer $n$ is prime given that it has no prime factors less than $k$. A simple sieving argument shows the number is odd should give us $1/2$ of the numbers, forcing that the number is not divisable by 3 should give us about $2/3$ of the numbers, and so forth. In general we should have about $$\prod_{p \le k} \left(1-\frac 1 p \right) \sim \frac{e^{-\gamma}}{\log k}$$ (By Merten's formula) numbers remaining after the sieving process. This is also suggested by the use of Dirichlet's theorem. This should give us the probability $e^{\gamma}/k \log k$ that the number $k!+j$ is prime, which is up to a constant the same as suggested by the Cramer model. In both cases the average prime gap can be expected to be of the order $k \log k$, albeit with different constants.

How many consecutive composite integers follow k!+1? - MathOverflow [closed]

How many consecutive composite integers follow k!+1?

Answer by Johan Andersson for How many consecutive composite integers follow k!+1?