Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

Maybe I don't see the obvious here; but well.
I looked at an old discussion concerning prime gaps. I now tried to ask a somehow opposite way:

Assume the set $\small P(m)$ of first m primes $\small \{p_1,p_2, \ldots,p_m\}$ . Then consider consecutive natural numbers from a to b inclusive which are all divisible by at least one of the primes in $ \small P(m)$. Let's call such an interval of numbers composite from $ \small P(m)$ an "m_primegap" $ \small G_m(b)$ ending at b. How long can an contiguous interval $\small G_m(b) = b+1-a $ become?

First I thought this is simple: just not bigger than $\small p_{m+1}-1$, because that set of primes covers completely the first $p_{m+1}-1$ numbers and the covering scheme looks somehow "optimally" distributed/exhausting - but that's not true, which can be seen with examples in small numbers.

Then the next impression from heuristic is, that it might not overstep $ \small 2 p_m$ - recalling that there is a prime between n and 2n - but thinking longer about this I don't trust that this is an argument after the first, much more intuitive idea, is already wrong. I've programmed a little routine in Pari/GP but the progression of m_primegaps is too slow and we need huge a to look for interesting m_primegaps.

A couple of small m and $ \small p_m$ shall give some impression.

For $ \small m=4$ ($ \small p_m=7$) I get the following table. I indexed for the upper bound b of the gap instead of a here:

$ \small \qquad \begin{array} {rr} gap & b & \text {first occurence, ending at b)}\\ \hline 4 & 11 \\ 6 & 29 \\ 8 & 97 \\ 10 & 209 \\ ?? & ??? \end{array} $

and no longer gap than $ \small 11-1=10$ seem to occur. For $ \small m=5,p_m=11$ we get an example for a 5_primegap of 14, which is bigger than $ \small 13-1=12$ but no bigger gap seem to occur. (I've used a precomputed list of factors of n for the first 1e7 natural numbers):

$ \small \qquad \begin{array} {rr} gap & b \\ \hline 2 & 13 \\ 4 & 17 \\ 6 & 29 \\ 8 & 97 \\ 14 & 127 \\ ?? & ??? \end{array} $

For $ \small p_m=23$ I get

$ \small \qquad \begin{array} {rr} gap & b \\ \hline 6 & 29 \\ 8 & 97 \\ 14 & 127 \\ 18 & 541 \\ 28 & 1361 \\ 34 & 60077 \\ ?? & ??? \end{array} $
and for the primes 67,71,79 I get the following table
$ \small \qquad \begin{array} {rr} gap & b \\ \hline 2 & 73 \\ 6 & 79 \\ 8 & 97 \\ 14 & 127 \\ 18 & 541 \\ 20 & 907 \\ 22 & 1151 \\ 34 & 1361 \\ 36 & 18839 \\ 48 & 28277 \\ 50 & 132817 \\ 54 & 395377 \\ 64 & 524591 \\ ?? & ??? \end{array} $

where we see, that the requirement for precomputed primes for the needed lists is bigger than suitable for some initial heuristics. Some upper limit should be related to the primorial-function for the prime $\small p_m$. So my question again: is there an unconditional upper bound for the maximal m_primegap, and if, what is it?

[update] one unconditional bound for the length of a m_primegap should be given by the observation, that the sequence of m_primegaps is periodic with the primorial of $ \small p_m $ ; so one unconditional upper bound is given by a finite number (well, such a bound is not much efficient...).

What I'm finally after is an argument/a proof that m_primegaps of size $ \small \gt p_{m+1}-1$ can only occur if $ \small b> p_m^2 $ (I've to state this a bit more precise)

If someone likes to play around: here is usable code in Pari/GP. I show it here because I found it fairly nontrivial to prevent excessive need of resources

\\ the primefactors of the numbers n is precomputed using the 
\\ most simple prime-sieve method, where the primefactors are
\\ encoded as bits in a natural number:
\\ a number n containing 3,5,7 as prime-factors is encoded as 2^2+2^3+2^4
\\ maxlimit for b is 2*1e6 (= length of the list)
\\ maxlimit for p_m is given by m=200
{ vn=vector(2000000,r,0);
    forstep(j=p1,#vn,p1,vn[j]+=s1 );
    ); }      

\\ return the list of increasing primegaps using all primes 
\\ up to the prime p
  s1 = vn[p]*2; pn_1=0; \\ nextprime(p+1)-1;
  for(k=p,maxn,   \\ ignore m_primegap at 1; begin at k=p
        if(vn[k] % s1 ==0,   \\ no prime lowerequal p_m is contained in number k
                  if(k0>pn_1,pn_1=k0;j1++;  list[j1]=[k0,k]);
  list = VE(list,j1);
  return(Mat(list)); }

share|cite|improve this question
In your first table, aren't 91 and 203 not divisible by any of 2,3, or 5? It looks like you could just work mod primorial$(p_m)$ and find the largest gap. For $p_m=5,$ the largest gap is 6, from 1 to 7 and again from 23 to 29. – Ross Millikan Aug 21 '11 at 16:45
It's $2p_{m-1}$ up to $p_m=17$, but I don't see how to prove that in general. – joriki Aug 21 '11 at 17:19
@Ross: yes, 91 and 203 are divisible by; so they are -so to say- "P(m)-composite" and part of the m_prime gap (=length of contiguous interval of P(m)-composites). Or did I misread you here? – Gottfried Helms Aug 21 '11 at 17:51
@Gottfried Helms: I thought you were only considering divisibility by primes less than or equal to $p_m$, so they should stop the "prime-free" gap. This accounts for my remark about working mod primorial$(p_m)$. Did I not understand what you are after? – Ross Millikan Aug 21 '11 at 17:54
@Ross: It seems to me this is merely a misunderstanding about whether to include $7$ as a divisor in the table for $m=4$, $p_m=7$. Since $p_m$ was included in $P(m)$, I think Gottfried is right to count $91$ and $203$ as divisible by one of the primes under consideration, and hence "$P(m)$-composite" -- I don't think there's any deeper misunderstanding with respect to what the question is about. – joriki Aug 21 '11 at 18:05
up vote 4 down vote accepted

There are several upper and lower bounds in this paper. I'd mentioned in a comment that the maximal gap is $2p_{m-1}$ up to $p_m=17$; it turns out that this is a lower bound which gives the exact value of the maximal gap up to $p_m=19$, whereas for $p_m=23$ the maximal gap is $40>2\cdot19$.

share|cite|improve this answer
Wow, thank you - the article is much interesting. I seem to stumble often on problems which are far too deep for my number theoretic abilities, it is really a pity... – Gottfried Helms Aug 21 '11 at 23:38

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.