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?

  • 17
    $\begingroup$ $n!+2, n!+3, ..., n!+n$ are all compositie $\endgroup$ – yoyo Aug 25 '12 at 1:53
  • $\begingroup$ Although the $[n! + 2, n! + n]$ range guarantees $n-1$ consecutive composites, one would probably find many more much sooner. For example: $n! = 3628800$, but there are already 111 composites starting from $370262$, and 113 starting from $492114$. $\endgroup$ – BoLe Jan 4 '17 at 9:56

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.

  • $\begingroup$ Could you please hint at why these numbers are composite. It must be obvious, but I am not seeing it. Thank you. $\endgroup$ – Sasha Aug 25 '12 at 2:33
  • 1
    $\begingroup$ @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. $\endgroup$ – André Nicolas Aug 25 '12 at 2:38
  • $\begingroup$ 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. $\endgroup$ – Sasha Aug 25 '12 at 2:41
  • 1
    $\begingroup$ You are right, I will change it, it gives us a few more consecutives in the string. $\endgroup$ – 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.

  • $\begingroup$ your sequence has $N+1$ consecutive composites, not $N$, which is more than required. you don't need to start the sequence at $(N+2)!+2$; starting at $(n+1)!+2$ suffices. $\endgroup$ – symplectomorphic Jan 15 '15 at 2:18

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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