MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Consecutive composite numbers

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)$?

-
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 at 19:36

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.

-

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.