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.
Programming Praxis 
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; };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))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.
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.
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!
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