## Prime Gaps

### February 2, 2016

We studied maximal prime gaps in a recent exercise. In today’s exercise we will look at minimal prime gaps — the smallest gap of a given size. For instance, the minimal prime gap of 2 is the gap from 3 to 5, the minimal prime gap of 4 is the gap from 7 to 11, the minimal prime gap of 6 is the gap from 13 to 19, and so on.

Your task is to write a program that finds minimal prime gaps. 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

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