# How many consecutive composite integers follow k!+1?

I wrote a program for myself in Mathematica to generate the answer for the first 300, which was really easy, but I can't find a pattern. The results are here. This is a problem in Underwood Dudley's Elementary Number Theory, 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 the answer is m-2. This is quite clearly not the answer based on the link I provided. My logic was that any number of the form k!+n will be composite when 1<n<m. That is true. However, it is not the end of the story. Any ideas?

Edit: For anyone curious, this is problem 2 part (b) in section 23.2 of the Second Edition of Underwood Dudley's Elementary Number Theory. Part (a) asks what the smallest integer n is such that n+1, n+2, n+3, and n+4 are all composite.

Second edit: Milcak's comment made me realize that, given some arbitrary n, we can write k!+n=k!+i+j so long as i+j=n. I'm thinking about this now...

Third edit: Here is another problem with the concept for me. I feel like the primes less than or equal to k should help us predict the divisbility of k!+i, and indeed they do, not when i is a prime greater than k. For example, 11!+13=199*200587. That sort of behavior seems unpredictable to me.

-
You might want to take a look to the OEIS sequence (oeis.org/A037153) – Esteban Crespi Feb 2 '11 at 12:17

Let us write $N(k)$ for the number of consecutive composite numbers following $k! + 1$.

If $m$ is the smallest prime greater than $k$, then for all $n$ with $1 < n < m$, $n$ must be divisible by some prime $p$ with $p \leq k$ (for otherwise $n$ would be a nonempty product of primes each of which is at least $m$, so $n \geq m$). Then $p$ divides both $k!$ and $n$ so $k! + n$ is divisible by $p$ and has size at least $2p$, so is composite.

All this is to say that your argument is correct as far as it goes: what it establishes is the inequality

$N(k) \geq m -2$.

(In particular, since $m \geq k+1$, it follows that $N(k) \geq k-1$, a weaker but more commonly made observation.) Note that if $k = 2$, then the number of consecutive composites following $2! + 1 = 3$ is $1$: $4$ is composite, but $5$ is prime. Here $m = 3$ and $m-2 = 1$. Thus, your inequality is sharp when $k = 2$, i.e., it is an equality.

Now, as your computations show, it is usually the case that $N(k)$ is strictly larger than $m-2$, often much larger. This is not surprising: the above argument guarantees that the first $m-2$ numbers after $k! + 1$ will all be composite. After that it doesn't tell us anything. But most numbers are not prime: in a sense made precise by the Prime Number Theorem, if you choose a number randomly from the interval $[1,N]$, the chance it is prime is $\frac{1}{\log N}$, so if you choose a sufficiently large number at random, then the chance that it is prime is very close to zero, so we certainly expect several more values after $k! + (m-2)$ to be composite for most values of $k$. However, we are far from being able to predict exactly where the primes and composites will fall.

All this is to say that at least from an elementary perspective, I would be surprised if you were expected to say anything more than $N(k) \geq m -2$. (You didn't directly quote the statement of the problem, but whatever it is, I am guessing that this inequality, or perhaps even $N(k) \geq k-1$, is the intended answer.)

One could of course try to do better: for instance, surely there are infinitely many values of $k$ for which $N(k) > m-2$, and with sufficient knowledge and technique in analytic number theory one could probably prove that. (I'd be interested to see people try!) But I think it is exceedingly unlikely that there will be any kind of simple formula or expression for $N(k)$ in general, so you shouldn't be disappointed not to have found one!

-
Also, the related question: are there infinitely many k for which N(k) = m-2? – ShreevatsaR Feb 2 '11 at 10:25
@ShreevatsaR: sure, that's an interesting question too. It seems much harder, though... – Pete L. Clark Feb 2 '11 at 14:57

Let me just point out that also $k!-2$, $k!-3$, ..., $k!-k$ are all composite.

-

Bertrand's postulate gives a crude upper bound on $N(k),$ the largest number of consecutive composite numbers following $k!+1.$

For $n>3$ there exists a prime $p$ such that $n<p<2n-2$ and so there is a prime $$k!+1< p < 2 k!,$$

but the first $(k-1)$ of $k!+2,k!+3, \ldots, 2k!-1$ are certainly composite and so

$$N(k) \le k! - k -1.$$

An additional observation is that if $k! \pm 1$ are not factorial primes then Bertrand's postulate says that there is a prime

$$k!-k-1 < p < 2k! -2k -4$$

and so, taking into account Andrea's observation, the first such prime must be $\ge k!+k+1,$ but also $\le 2k! -2k -5.$ Hence we have for $k>3$

$$N(k) \le (2k!-2k-5)-(k!+2) = k! -2k-7,$$

a slight improvement for the bound in the absence of factorial primes.

-

$k! + n$ is composite for all $n$ until $n$ is a prime larger than $k$. Otherwise, $n$ must be divisible by a prime smaller or equal to k.

There is no general formula for the distance to a prime, so we can only give an inequality or look at the average maximum $n$.

-