most recent 30 from http://mathoverflow.net 2013-05-22T17:35:37Z http://mathoverflow.net/feeds/question/105408 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/105408/consecutive-composite-numbers Jake Wellens 2012-08-24T18:32:21Z 2012-08-24T23:23:10Z

<p>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]$.)</p> <p>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)$.</p> <p>So, we have $C(N,k) \leq C(kN, 1) \leq (kN+1)!+kN+1$.</p> <p>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?</p> <p>The gap between primes is something like $O(\log(N))$, and so maybe $C(N,k)$ grows sort of like $O(ke^N)$?</p>

http://mathoverflow.net/questions/105408/consecutive-composite-numbers/105416#105416 Douglas Zare 2012-08-24T19:54:47Z 2012-08-24T19:54:47Z

<p><a href="http://mathworld.wolfram.com/PrimeGaps.html" rel="nofollow">Mathworld</a> 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.</p> <p>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. </p>

http://mathoverflow.net/questions/105408/consecutive-composite-numbers/105431#105431 Gerhard Paseman 2012-08-24T23:23:10Z 2012-08-24T23:23:10Z

<p>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.</p> <p>Gerhard "Ask Me About Jacobsthal's Function" Paseman, 2012.08.24</p>