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

### Like this:

Like Loading...

*Related*

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.pyto 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 theenigma.pylibrary).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.

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 isprimorial(n)(i.e. the product of the primes less than or equal ton), and this has been verified forn≤ 21.This uses my own Primes class (which is a development of Jim’s class that includes support for ‘unlimited’ prime sequence generation).

My number_theory library is available http://ccgi.gladman.plus.com/wp/?page_id=1500