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.

Pages: 1 2

4 Responses to “Prime Gaps”

  1. Rutger said

    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 -- 3109
    
  2. Rutger said

    Correction, 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 -- 907
    
  3. A 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;
    };
    
    
  4. Paul said

    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]))
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: