## Maximal Prime Gaps

### January 8, 2016

We use the `primegen` incremental Sieve of Eratosthenes from a previous exercise:

```(define (gaps)
(let ((ps (primegen)))
(let loop ((prev-prime (ps)) (prev-gap 0))
(let* ((prime (ps)) (gap (- prime prev-prime)))
(when (< prev-gap gap)
(display prev-prime) (display #\tab)
(display gap) (newline))
(loop prime (max gap prev-gap))))))```

And here it is in action:

```> (gaps)
2	1
3	2
7	4
23	6
89	8
113	14
523	18
887	20
1129	22
1327	34
9551	36
15683	44
19609	52
31397	72
155921	86
360653	96
370261	112
492113	114
1349533	118
1357201	132
2010733	148
4652353	154```

You can see the program assembled at http://ideone.com/i6yjaX, but it won’t run because the necessary macros aren’t available on ideone.

Looking at the table, you can see that the largest prime gap less than 216 is 72, which means that you could easily store a table of the 6542 primes less than 216 in 6542 bytes by storing the gaps between them, which takes only half the space of storing the primes themselves. Having such a table available gives a compact way to quickly perform trial division up to 232, even faster than a 2,3,5,7-wheel.

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