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]

Advertisements

3 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):
    
        # start with 2
        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)):
    
        # start with the first prime, p < d
        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.

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

Leave a Comment

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: