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]

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