MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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.

share|cite|improve this answer

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.

share|cite|improve this answer
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.

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

share|cite|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

Your Answer


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.