# 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. – user9072 Aug 24 '12 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.

-

Let $Q_N$ be the product of the $N$ smallest primes greater than $N$, so $Q_N$ is $O((N\log N)^N)$. Then $Q_N$ has $k=N!$ intervals of consecutive integers in which each integer shares exactly one common prime factor with $Q_N$. Thus $C(N,N!)\leq Q_N$. While the relationship is not quite linear, it does hold for every positive integer $l$ that $C(N,l(N!))\leq lQ_N$. One can try for smaller products of $N$ primes $Q$ and count smaller numbers $k$ of disjoint noncoprime intervals of length $N$ and similarly get $C(N,lk)\leq lQ$, but this will be suboptimal as other intervals of composites that contain integers coprime to $Q$ will be ignored.

Even though it is far from the actual order of growth, it should show that the growth is roughly linear in $k$, and that the main issue is the length $N$ of the interval of composites.

Gerhard "Sorry For The Long Interval" Paseman, 2016.05.01.

-
In this scheme, it seems unlikely that one of the intervals would contain one of the prime factors of $Q_N$. If, so, it would contain the largest prime factor $P$ and thus the inequalities above would need $P$ added to the right hand side to be easily proved, so the order of magnitude of the bound stays the same. Gerhard "Minding The P's And Q's" Paseman, 2016.05.01. – Gerhard Paseman May 2 at 5:21

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.