Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
13  
$n!+2, n!+3, ..., n!+n$ are all compositie –  yoyo Aug 25 '12 at 1:53
add comment

3 Answers

up vote 5 down vote accepted

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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