### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,158)
- misc (2)
- project euler (2)
- puzzle (40)
- site news (44)
- tantalizer (42)
- teaser (3)

### Site Stats

- 178,002 hits

Advertisements

Programming Enigma Puzzles

29 December 2014

Posted by on **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]

Advertisements

%d bloggers like this:

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.The

PrimesGenerator()function was subsequently included into theenigma.pylibrary, and then thePrimes()class itself was made autoexpandable (via theexpandableparameter). So the following code will suffice.Instead of using the

Primes()class and setting theexpandableparameter at line 10 thePrimesGenerator()class can be used instead.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