12
$\begingroup$

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);   for(k=1,200,     p1=prime(k);s1=2^(k-1);     forstep(j=p1,#vn,p1,vn[j]+=s1 );     ); }        
    \\ return the list of increasing primegaps using all primes  \\ up to the prime p {primegapMAX_p(p,maxn=#vn,maxl=10)=local(a,s1,list,j1,pn_1);   s1 = vn[p]*2; pn_1=0; \\ nextprime(p+1)-1;   list=vectorv(maxl);   j1=0;k0=0;   for(k=p,maxn,   \\ ignore m_primegap at 1; begin at k=p         if(j1>=maxl,break());         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]);                   k0=0);         k0++       );   list = VE(list,j1);   return(Mat(list)); }  
  • 0
    @joriki: I see I misread it. Then it seems you still don't need any precomputed primes larger than $p_m$. For example, 11 divides 209, but 209 still counts as prime for this purpose when m=4.2011-08-21

1 Answers 1

5

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$.

  • 0
    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...2011-08-21