# Is there any algorithm to identify the smallest example of gap size $n-1$ between consecutive prime numbers

In contemplating Goldbach's conjecture, I became interested in gaps between successive primes. If $n<a<b<2n$ and the range $a$ to $b$ is a primeless gap, then one could ignore any primes in the range $2n-b$ to $2n-a$ for purposes of Goldbach solutions concerning the even number $2n$. That line of thought is not getting anywhere, but it did turn my attention to gaps.

There are several ways to achieve a gap between successive primes of at least $n-1$, viz: $k\mid (n!+k)$ for $2\le k\le n$. If $N$ is defined as the least common multiple of $n$ (see OEIS A003418), then $k\mid (N+k)$ for $2\le k\le n$. Finally gcd$(k,(n\# +k))>1$ for $2\le k\le n$.

These methods all work. For a gap of $n-1=5$; $n=6$, the factorial method gives the five numbers $722,723,724,725,726$ without any primes. The lcm method gives the five numbers $62,63,64,65,66$ without any primes. The primorial method gives the five numbers $32,33,34,35,36$ without any primes. But the smallest sequence of five numbers without any primes is $24,25,26,27,28$. I see that this occurs because the two odd numbers have distinct small prime factors, but I cannot see any way (other than direct examination) to generate or identify this sequence.

Added by edit: It is interesting to note that since the factorial and the lcm methods both yield sequences whose members are divisible (seriatim) by every $k$ in the applicable range, and the lcm method generates a smaller answer by virtue of casting out 'superfluous' occurrences of prime factors, then intermediate sequences of $(n-1)$ numbers lacking a prime can be obtained by subtracting various multiples of the lcm $N$ from the factorial $n!$. In the context of the example given, this generates sequences of five primeless numbers starting at $662; 602; 542; 482; 422; 362; 302; 242; 182; 122$. Further to that thought: Any number $m(n\#)$ can be the basis for such a sequence, i.e. $(m(n\#)+k)$ for $2\le k\le n$.

I have searched MSE to see if this question has been asked before, and I did not find it (which surprised me a little): Is there an algorithmic way to generate or identify the first or smallest occurrence of a prime gap of size $(n-1)$?

• no, it is an extremely difficult problem. See the table of maximal prime gaps at en.wikipedia.org/wiki/Prime_gap Evidently there is slow progress, they now have the first 78 maximal gaps. Last time I looked it was 75. They have (slightly) passed $10^{19}$ – Will Jagy Jul 27 '18 at 19:53
• primorial works both plus or minus a given number less than the first prime it doesn't have, otherwise distributivity fails ( except the prime 3 interferes in the case of 6). so 30-2 divides by 2, 30-3 divides by 3, 30-4 divides by 2, 30-5 divides by 5, and 30-6 divides by 6, that explains your earlier gap. – Roddy MacPhee Feb 28 at 11:55
• @Roddy MacPhee Very nice insight and I will have to look to see if this suffices to identify gaps that have the smallest possible members in other instances. – Keith Backman Feb 28 at 17:57
• it shouldn't at last thought, I can't remember the results they had on mersenneforum, but higher primorials have more primes to catch up with them to extend the gaps further. – Roddy MacPhee Feb 28 at 18:06
• oh and for the equidistance form of Goldbach you can eliminate divisors of n as then the other prime is composite. in fact 30 =2*15 hits all posdibilities (7,23),(11,19),(13,17) all the rest would contain a prime and composite pairing. – Roddy MacPhee Feb 28 at 19:07