Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $C(N,k)$ be the smallest positive integer $x$ such that $[1,x]\subset \mathbb{Z}$ contains $k$ disjoint intervals $I_1, ..., I_k$ of $N$ consecutive integers that are all composite. (For example, $C(2,2)=15$, with $I_1=[8,9]$ and $I_2=[14, 15]$.)

I am interested in the asymptotic behavior of $C(N,k)$ for various fixed values of $k$. Clearly $C(N,1) \leq (N+1)!+N+1$. Also if $M$ divides $N$, and we have $k$ disjoint intervals of $N$ consecutive composites, we can break each interval up into $N/M$ disjoint intervals of $M$ consecutive composites, giving a total of $kN/M$ intervals, and so $C(M, kN/M) \leq C(N, k)$.

So, we have $C(N,k) \leq C(kN, 1) \leq (kN+1)!+kN+1$.

However, these bounds give $15=C(2,2)\leq C(4,1)=27\leq 5!+5=125$, which doesn't seem very tight. Can anyone come up with better bounds or asymptotics?

The gap between primes is something like $O(\log(N))$, and so maybe $C(N,k)$ grows sort of like $O(ke^N)$?

share|improve this question
1  
Yes, I think what you say should be true and likely provable. The true growth should however be slower I think, maybe about $\exp(\sqrt{N})$ or so, as the size of the large prime gaps is expected to be $(\log x)^2$ around $x$; this however should be out of reach of current technology. –  quid Aug 24 '12 at 19:36
add comment

2 Answers

Mathworld mentions some conjectures including that $C(N,1) \sim \exp(\sqrt n)$ (Cramér and Shanks) and a slightly different growth $C(N,1) \sim \sqrt n \exp(\sqrt n)$ conjectured by Wolf.

You can translate upper bounds on prime gaps to lower bounds on $C(N,1)$, and lower bounds on prime gaps to upper bounds on $C(N,1),$ so I'm not sure that it is worth studying these separately. To construct upper bounds on $C(N,k)$ (which is not great notation since most people will read it as the quite different $N \choose k$) I think you can use slight modifications for the constructions which give lower bounds on prime gaps.

share|improve this answer
add comment

One thing I would like to see more of is an analysis of the distribution of integers coprime to a large integer (totients of?) M. If M has k distinct prime factors, one can get M/2 as an upper bound to C(k, factorial(k)/2) using the Chinese remainder theorem. You might find Jacobsthal's function (an approach to evaluating C(k,1)) a useful diversion.

Gerhard "Ask Me About Jacobsthal's Function" Paseman, 2012.08.24

share|improve this answer
    
Actually, it isn't that easy as for small primes some of the intervals may overlap. It should be true if all the distinct prime factors are larger than k. Gerhard "Correct Me About Jacobsthal's Function" Paseman, 2012.08.24 –  Gerhard Paseman Aug 24 '12 at 23:28
    
Further, one of the intervals might include an actual prime. However, it would be the first interval, and there are likely intervals of totients of M which are also composite to make up for the first interval. Anyway, it is easy to find lots of such intervals. Gerhard "Ask Me About System Design" Paseman, 2012.08.24 –  Gerhard Paseman Aug 24 '12 at 23:46
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.