# What is the maximum number of consecutive composite numbers possible?

Can anyone tell me what is the maximum number of consecutive composite numbers possible? I mean can I get say 1000 consecutive natural numbers. Is there any general theorem that when I have a n-digit number there will always be p consecutive composite numbers?

-
$n!+2, n!+3, ..., n!+n$ are all compositie –  yoyo Aug 25 '12 at 1:53

Let $p_1,p_2, p_3,\dots,p_n$ be the first $n$ primes, and let $P_n$ be their product. Then the $p_{n+1}-2$ consecutive integers $P_n+2,P_n+3, \cdots, P_n+(p_{n+1}-1)$ are all composite.

For let $P_n+x$ be one of these numbers. Since $2\le x\lt p_{n+1}$, $x$ is divisible by some prime $p\le p_n$ ($x$ could itself be prime). But $P_n$ is also divisible by $p$, so $P_n+x$ is divisible by $p$. Clearly $P_n+x\gt p$, so $P_n+x$ is composite.

We can in general get a very slightly cheaper string by starting at $P_n-2$ and going backwards. These procedures get us arbitrarily long strings of consecutive composites, since there are infinitely many primes.

But one can do a lot better than $P_n$ in general. The subject of Prime Gaps has been extensively studied. You will find detailed information in this Wikipedia article.

-
Could you please hint at why these numbers are composite. It must be obvious, but I am not seeing it. Thank you. –  Sasha Aug 25 '12 at 2:33
@Sasha: I had wondered whether I should explain that! I have added a couple of sentences to the answer. Please tell me if the reason is not clear. –  André Nicolas Aug 25 '12 at 2:38
Thanks for the explanation. It's all clear. However, if $P_n = \prod_{k=1}^n p_k$, then the sequence should be $\{P_n+2, P_n+2, \ldots, P_n + p_{n+1} -1\}$, like in the wikipedia article you refer to. –  Sasha Aug 25 '12 at 2:41
You are right, I will change it, it gives us a few more consecutives in the string. –  André Nicolas Aug 25 '12 at 2:45

The Answer for your first question is - Yes, It is possible to have N consecutive composite numbers. The series -

$(N+2)!+2 , (N+2)! + 3,(N+2)!+4,...(N+2)!+(N+2)$

will give you N consecutive composite numbers.

Proof - It is easy to prove it because, N! is a multiplication of all numbers from 1 to N, so you can see

$(N+2)!+2$ will give you 2 as common factor

$(N+2)!+3$ will give you 3 as common factor

.

.

.

$(N+2)!+(N+2)$ will give you (N+2) as common factor

showing N consecutive composite numbers.

-

There is no maximum. Here is a possible ciruclar reasoning, but it should help understand why there cannot be a maximal length of consecutive composites:

It is a known theorem that there are roughly $\ln k$ many prime numbers below $k$. By roughly I mean that $$\frac{|\{1,\ldots,k\}|}{|\{p<k: p\text{ prime}\}|}\longrightarrow\frac{k}{\ln k}$$

If there was a maximal length of composite sequence, say $n$, then at least one of every $n$ numbers would have to be prime. This would mean that for all $k$ (or rather for sufficiently large $k$) we have: $$\frac{|\{1,\ldots,k\}|}{|\{p<k: p\text{ prime}\}|}\geq\frac{1}{n}$$

Recall that $n$ is a constant in this discussion, so this ratio is not going to approach $\frac{k}{\ln k}$ in the limit. This is a contradiction to the Prime number theorem, so there cannot be a maximal length for consecutive composites.

-