# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1267: Prime progression

From New Scientist #2423, 29th November 2003 [link]

George: Hi, Fred! Can you find a list of 10 prime numbers in arithmetic progression?

Fred: Sounds like one for the masochists – I wouldn’t know where to start.

George: I’ll give you a start. My list has the smallest possible common difference for a series of 10, and the smallest number in the AP is smaller than the common difference.

Colin: That is all you need to know. What are George’s smallest number and common difference?

[enigma1267]

### 4 responses to “Enigma 1267: Prime progression”

1. Jim Randell 29 December 2014 at 8:51 am

The Green–Tao Theorem (2004) [ http://en.wikipedia.org/wiki/Green%E2%80%93Tao_theorem ] shows that arithmetic progressions of primes of any given length exist.

Because I didn’t know what the upper limit on the primes was going to be, I thought it would be fun to write a class that used the prime sieve that already exists in enigma.py to generate primes by increasing the size of the sieve in chunks, so I would effectively have a class that can be used to generate primes without limit. (I’ll add this to the enigma.py library).

This program assumes that the problem formulation is correct and that there is a sequence with the smallest possible common difference where the first prime in the sequences is less than the common difference. This limits the search space. It runs in 46ms.

```from itertools import count
from enigma import Primes, irange, printf

# an object to generate all primes (in chunks) by using the prime sieve
class PrimesGenerator(object):

# n = starting max for the sieve
# fn = how to increase the max value
def __init__(self, n, fn=lambda n: 2 * n):
self.chunk = fn
self.primes = Primes(n)

# extend the sieve
def extend(self, n):
self.primes.extend(n)

# compute the next chunk of primes
def expand(self):
self.extend(self.chunk(self.primes.max))

# generate all primes
def __iter__(self):

yield 2

# and use the sieve for the rest
l = 0
while True:
s = self.primes.sieve
h = len(s)

# generate primes from sieve indices [l, h)
for i in range(l, h):
if s[i]:
yield 2 * i + 3

# expand the sieve
self.expand()
# and start from the previous high point
l = h

# test for primes (may throw IndexError if n is too large)
# (call self.extend(n) first if you want to make sure it isn't)
def __contains__(self, n):
return n in self.primes

# find the progression of primes with n terms
# and the smallest common difference
def solve(n):

# generate all primes (starting with the first 1000)
primes = PrimesGenerator(1000)

# multiples of the common difference to check
ms = tuple(irange(1, n - 1))

# consider increasing d
for d in count(2, step=(1 if n < 3 else 2)):

primes.extend(n * d)
for p in primes:
if not(p < d): break

# check the sequence
if all((p + m * d) in primes for m in ms):
return (p,) + tuple(p + m * d for m in ms)

import sys
n = (10 if len(sys.argv) < 2 else int(sys.argv[1]))

s = solve(n)
printf("[n={n}] {s} d={d}", d=s[1] - s[0])
```

Solution: The smallest number is 199, and the common difference is 210.

The sequence of 10 primes is: (199, 409, 619, 829, 1039, 1249, 1459, 1669, 1879, 2089), d = 210.

For 11 primes the program finds the following sequence: (23143, 53173, 83203, 113233, 143263, 173293, 203323, 233353, 263383, 293413, 323443), d=30030. However there are sequences of 11 primes with smaller common differences. The smallest possible being 2310, starting at 60858179.

For n > 7 it has been postulated that the minimal possible common difference is primorial(n) (i.e. the product of the primes less than or equal to n), and this has been verified for n ≤ 21.

• Jim Randell 6 August 2017 at 4:05 pm

The PrimesGenerator() function was subsequently included into the enigma.py library, and then the Primes() class itself was made autoexpandable (via the expandable parameter). So the following code will suffice.

```from itertools import count
from enigma import Primes, irange, arg, printf

# find the progression of primes with n terms
# and the smallest common difference
def solve(n):
assert n > 1

# generate all primes (starting with the first 1000)
primes = Primes(1000, expandable=1)

# multiples of the common difference to check
ms = tuple(irange(1, n - 1))

# consider increasing d
for d in count(2, step=(1 if n < 3 else 2)):

for p in primes:
if not(p < d): break

# check the sequence
if all((p + m * d) in primes for m in ms):
printf("[primes.max = {primes.max}]")
return (p,) + tuple(p + m * d for m in ms)

n = arg(10, 0, int)

s = solve(n)
printf("[n={n}] {s} d={d}", d=s[1] - s[0])
```

Instead of using the Primes() class and setting the expandable parameter at line 10 the PrimesGenerator() class can be used instead.

2. Brian Gladman 30 December 2014 at 3:06 pm

This uses my own Primes class (which is a development of Jim’s class that includes support for ‘unlimited’ prime sequence generation).

```from sys import argv
from itertools import count
from number_theory import Primes

def solve(n):
for d in count(2, 2):
prms = Primes(d * n)
for p in prms:
if p >= d:
break
if all(p + k * d in prms for k in range(1, n)):
return tuple(p + k * d for k in range(n))

n = (10 if len(argv) < 2 else int(argv[1]))
s = solve(n)
print('p = {}, d = {}, seq = {}.'.format(s[0], s[1] - s[0], s))
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.