6
$\begingroup$

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?

  • 0
    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$.2017-01-04

3 Answers 3

5

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.

  • 1
    You are right, I will change it, it gives us a few more consecutives in the string.2012-08-25
1

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.

  • 0
    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.2015-01-15
0

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

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

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.