MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

closed as too localized by Pete L. Clark, Douglas Zare, Chandan Singh Dalawat, Willie Wong, Dmitri Pavlov Feb 3 '11 at 5:05

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

I suspect that all Dudley expects by way of an answer is something like, "at least $k-1$". – Gerry Myerson Feb 2 '11 at 8:46
That's what I'm leaning toward. It seems pretty dang hard to predict anything past m-2, where m is as I defined it (the least prime greater than or equal to k). – Willy Feb 2 '11 at 9:08
Note that this question has been cross-posted at math.SE (and I have answered it there, essentially elaborating on Gerry's comment). Please note that undergraduate homework questions are off-topic for this site, c.f. the FAQ. – Pete L. Clark Feb 2 '11 at 10:02
Noted. My mistake. – Willy Feb 2 '11 at 10:14
Link to question:… – François G. Dorais Feb 2 '11 at 15:06

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.

share|cite|improve this answer

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