Enigmatic Code

Programming Enigma Puzzles

Enigma 1216: Chain of primes

From New Scientist #2372, 7th December 2002 [link]

I have constructed a chain of ten 2-digit prime numbers. The ten primes that I have used are all different and except in the case of the first prime in the chain each prime’s first digit is the same as the previous prime’s second digit. In addition the fourth prime is the reverse of the first prime, and the tenth prime is the reverse of the seventh prime.

What (in this order) are the third, sixth and ninth primes in this chain?

[enigma1216]

Advertisements

3 responses to “Enigma 1216: Chain of primes

  1. Jim Randell 22 July 2015 at 9:30 am

    This Python 3 program constructs all possible length 10 chains, and then checks the additional conditions. It runs in 84ms.

    from enigma import Primes, printf
    
    # generate chains of length <n>
    # each element must be different
    def chains(n, ns, s):
      if n == 0:
        yield s
      else:
        for x in ns:
          if not(s) or (x[0] == s[-1][-1] and x not in s):
            yield from chains(n - 1, ns, s + [x])
    
    # the elements in the chain
    primes = list(str(n) for n in Primes(99).generate(10))
          
    # consider chains of length 10
    for s in chains(10, primes, []):
    
      # the 4th element is the reverse of the 1st element
      if not(s[3] == s[0][::-1]): continue
    
      # the 10th element is the reverse of the 7th element
      if not(s[9] == s[6][::-1]): continue
    
      printf("{s}", s=tuple(map(int, s)))
    

    Solution: The third prime in the chain is 73. The sixth prime in the chain is 19. The ninth prime in the chain is 17.

    The entire chain is: (13, 37, 73, 31, 11, 19, 97, 71, 17, 79).

    • geoffrounce 23 July 2015 at 8:57 pm
      # Preliminary analysis
      # The complete list of two-digit prime numbers is 11, 13, 17, 19, 23, 29,
      # 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 and 97.
      
      # Prime numbers starting with 2,4,5,6, or 8 can be eliminated from the chain,
      # as these digits will not form the last digit of any prime numbers.
      
      # This leaves a prime list of 11, 13, 17, 19, 31, 37, 71, 73, 79 and 97
      # from which to form the chain for the solution.
      
      from itertools import permutations
      
      for p in permutations((11,13,17,19,31,37,71,73,79,97)):
        a, b, c, d, e, f, g, h, i, j = p
        
        # find 1st and last digits of all ten primes
        a1, a2 = a // 10, a % 10;   b1, b2 = b // 10, b % 10;   c1, c2 = c // 10, c % 10;
        d1, d2 = d // 10, d % 10;   e1, e2 = e // 10, e % 10;   f1, f2 = f // 10, f % 10;
        g1, g2 = g // 10, g % 10;   h1, h2 = h // 10, h % 10;   i1, i2 = i // 10, i % 10;
        j1, j2 = j // 10, j % 10
        
        # check last digit of one prime is first digit of the next prime
        if a2 == b1 and b2 == c1 and c2 == d1 and d2 == e1 \
          and e2 == f1 and f2 == g1 and g2 == h1 and h2 == i1 and i2 == j1:
            
          # check 4th prime(d) is reverse of 1st prime(a)
          if a2 == d1 and a1 == d2:
              
            # check tenth prime(j) is reverse of 7th prime(g)
            if j1 == g2 and j2 == g1:
              print( 'Third prime = {}, Sixth prime = {}, Ninth Prime = {}'.format (c,f,i))
              print ('Prime Chain is ', a, b, c, d, e, f, g, h, i ,j )
              break   # we are told there is only one chain
                  
      # Third prime = 73, Sixth prime = 19, Ninth Prime = 17
      # Prime Chain is  13 37 73 31 11 19 97 71 17 79
      
      
  2. Brian Gladman 24 July 2015 at 5:12 pm
    from number_theory import Primes
    from collections import defaultdict
    from itertools import permutations
    
    # two digit primes
    pr = Primes().list(10, 100)
    # for each prime, list those that can follow it
    pf = defaultdict(list)
    # the set of prime pairs with the same two digits
    rset = set()
    for p, q in permutations(pr, 2):
      if p % 10 == q // 10:
        pf[p] += [q]
      if str(p) == str(q)[::-1]:
        rset.update([(p, q), (q, p)])
        
    def prime_seq(chain):
      # do we have a chain of 10?
      if len(chain) == 10:
        yield chain
      else:
        # otherwise choose from primes that can follow the
        # last in the chain that is not already present
        for p in pf[chain[-1]]:
          if p not in chain:
            yield from prime_seq(chain + [p])
    
    # start the chain with any prime that is reversible
    for p, _ in rset:
      for s in prime_seq([p]):
        # the fourth is the reverse of the first and the
        # seventh is the reverse of the tenth
        if set([(s[0], s[3]), (s[6], s[9])]) <= rset:
          fs = 'The primes are {0[2]:}, {0[5]:} and {0[8]:} {0:}'
          print(fs.format(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: