Prime Gaps
February 2, 2016
We reuse the primegen infrastructure from the previous exercise. Then gaps finds the prime gaps less than n:
(define (gaps n)
(let ((ps (primegen))
(gs (make-hashtable identity =)))
(let* ((prev (ps)) (prev (ps)) (curr (ps)))
(let loop ((prev prev) (curr curr) (len 0))
(cond ((= n len)
(do ((g 2 (+ g 2))) ((< n g))
(display g) (display #\tab)
(display (hashtable-ref gs g #f))
(newline)))
((hashtable-contains? gs (- curr prev))
(loop curr (ps) len))
(else (hashtable-set! gs (- curr prev) prev)
(loop curr (ps) (+ len 1))))))))
Here’s what it looks like in action:
> (gaps 50) 2 3 4 7 6 23 8 89 10 139 12 199 14 113 16 1831 18 523 20 887 22 1129 24 1669 26 2477 28 2971 30 4297 32 5591 34 1327 36 9551 38 30593 40 19333 42 16141 44 15683 46 81463 48 28229 50 31907
You can see the program at http://ideone.com/i8LT12, though it won’t run because Guile doesn’t implement R6RS-style hash tables.
In Python:
def prime_generator(): yield 2 n = 3 while True: yield n n +=2 while not odd_number_is_prime(n): n += 2 def odd_number_is_prime(odd_number): i = 3 while i <= odd_number**0.5: if not (odd_number % i): return False i += 2 return True pg = prime_generator() for gap in range(2,21,2): print "Finding gap of size", gap i = pg.next() for j in pg: if j - i == gap: print " found gap for primes", i, '--', j break i = j # output: # Finding gap of size 2 # found gap for primes 3 -- 5 # Finding gap of size 4 # found gap for primes 7 -- 11 # Finding gap of size 6 # found gap for primes 23 -- 29 # Finding gap of size 8 # found gap for primes 89 -- 97 # Finding gap of size 10 # found gap for primes 139 -- 149 # Finding gap of size 12 # found gap for primes 199 -- 211 # Finding gap of size 14 # found gap for primes 293 -- 307 # Finding gap of size 16 # found gap for primes 1831 -- 1847 # Finding gap of size 18 # found gap for primes 1913 -- 1931 # Finding gap of size 20 # found gap for primes 3089 -- 3109Correction, prime generator should be initiated inside the [for gap] loop.
def prime_generator(): yield 2 n = 3 while True: yield n n +=2 while not odd_number_is_prime(n): n += 2 def odd_number_is_prime(odd_number): i = 3 while i <= odd_number**0.5: if not (odd_number % i): return False i += 2 return True for gap in range(2,21,2): print "Finding gap of size", gap pg = prime_generator() i = pg.next() for j in pg: if j - i == gap: print " found gap for primes", i, '--', j break i = j # output: # Finding gap of size 2 # found gap for primes 3 -- 5 # Finding gap of size 4 # found gap for primes 7 -- 11 # Finding gap of size 6 # found gap for primes 23 -- 29 # Finding gap of size 8 # found gap for primes 89 -- 97 # Finding gap of size 10 # found gap for primes 139 -- 149 # Finding gap of size 12 # found gap for primes 199 -- 211 # Finding gap of size 14 # found gap for primes 113 -- 127 # Finding gap of size 16 # found gap for primes 1831 -- 1847 # Finding gap of size 18 # found gap for primes 523 -- 541 # Finding gap of size 20 # found gap for primes 887 -- 907A perl 6 version – keeps track of higher gaps until they need to be displayed!
my ($p,$max_disp,%f) = (2,2); say "1\t2"; for (3,5 ... *).grep(*.is-prime) -> $i { unless %f{$i-$p} { %f{$i-$p} = $p; while %f{$max_disp} { say "$max_disp\t%f{$max_disp}"; $max_disp+=2; } }; $p = $i; };In Python. Using a dict to record the minimal gaps. The prime generator can be initialized once outside the main loop. The function pairwise is from the itertools doc and lazyprime is from an earlier exercise.
maxgap = 50 primepairs = pairwise(lazyprime()) gaps = {} for target_gap in range(2, maxgap+1, 2): while target_gap not in gaps: prime, nextprime = next(primepairs) gap = nextprime - prime if gap <= maxgap and gap not in gaps: gaps[gap] = prime print("{:10d} {:20d}".format(target_gap, gaps[target_gap]))