## Maximal Prime Gaps

### January 8, 2016

Although the prime numbers are fascinating in their own right, sometimes it is interesting and instructive to look at the gaps between successive prime numbers. For instance, here is a table that shows how the maximal prime gap grows:

```2    1
3    2
7    4
23   6
89   8
113  14
523  18
887  20```

At each step the table shows a prime number and the gap to the next prime number; for instance, at prime 7 the gap to the next prime number, 11, is 4. The table only shows those instances where the prime gap increases. Note that the increases are not steady; for instance, a gap of 14 appears before a gap of 10 or 12.

Your task is to write a program that creates the table shown above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 6 Responses to “Maximal Prime Gaps”

1. Let’s try Perl 6 again… The “…” is a lazy sequence…

```my \$mg = 0;
my \$p = 2;
for (3,5 ... *).grep(*.is-prime) -> \$i {
if \$i-\$p > \$mg {
\$mg = \$i-\$p;
say "\$p\t\$mg";
};
\$p = \$i;
};
```
2. Paul said

In Python. primegen is a lazy prime generator and pairwise is from the itertools documentation.

```gap = 0
for prime, nextprime in pairwise(primegen()):
newgap = nextprime - prime
if newgap > gap:
gap = newgap
print("{:20d} {:10d}".format(prime, gap))
```
3. danaj said

Perl 5, pretty fast (~6 seconds to get to 288).

```use ntheory ":all";
my(\$l,\$m) = (2,0);
forprimes {
if (\$_-\$l > \$m) {
\$m = _-\$l;
printf "%12d %4d\n",\$l,\$m;
}
\$l = \$_;
} 1e13;
```

We could alternately use the simple prime iterator, object prime iterator, or the prime array from that package, but forprimes is the fastest method.

4. mvaneerde said

Not part of the exercise, but I will offer a proof that the ascending-prime-gap sequence is infinite.

1. The sequence has at least two terms: 1 and 2. These terms come from the prime gaps (2 => 3) and (3 => 5) respectively.

2. If the sequence has n terms, it also has an (n + 1)th term. Let the nth term be G, with n >= 2. Consider the sequence (G + 2)! + 2, (G + 2)! + 3, (G + 2! + 4, …, (G + 2)! + (G + 2). This sequence has length G + 1, and every term in the sequence is composite (in particular, (G + i)! + i is divislble by i). So there is an (n + 1)th term.

5. sidhu1f said

Fun mathematical fact about gaps between primes: if p and q are successive primes (p < q) then q-p-1 is either 0 or 1 or a prime number!

6. Yuri said

Java Script

```var maxValue = 1000; // maximum value of prime number
var lastPrime = 2; // last prime number value
var gap = 0
for(var i = 2; i <= maxValue; i++) {
if(primeTrue(i)) {
if(gap < i-lastPrime ){
document.write(lastPrime + " ; " + (i-lastPrime)+ "<BR/>");
gap = i-lastPrime;
};
lastPrime = i;
}; //end of "if" condition
}; //end of cicle

//Checking of prime number : true or false
function primeTrue(number) {
for(var j=2; j < number; j++ ){
if (number % j == 0){ return false};
};
return true;
}; // end of function
```

==========================================

Result on screen:

2 ; 1
3 ; 2
7 ; 4
23 ; 6
89 ; 8
113 ; 14
523 ; 18
887 ; 20