# primegaps w.r.t. the m first primes / jacobsthal's function

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)); }


-
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

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