## Prime Chains

### July 4, 2017

We studied word chains in a previous exercise; for instance, you can convert HEAD to TAIL by the word chain HEAD, HEAL, TEAL, TELL, TALL, TAIL in which each word differs from its predecessor by a single letter. Today’s exercise is similar, but asks you to find the chain from one prime number to another, with all intermediate numbers also prime, by changing one digit at a time; for instance, the chain 71549, 71569, 71069, 11069, 10069, 10067 converts 71549 to 10067.

Your task is to write a program to find prime chains. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 2 Responses to “Prime Chains”

1. Paul said

In Python. This is taken from the book Python Algorithms by Hetland. In the book code is given for finding chains of words from a dictionary. I only had to change the method “variants”. The A* method is used to find the shortest path with a distance heuristic that counts the number of mismatches in the numbers.

```def a_star(G, s, t, h):
P, Q = {}, [(h(s), None, s)]                # Pred and queue w/heuristic
while Q:                                    # Still unprocessed nodes?
d, p, u = heappop(Q)                    # Node with lowest heuristic
if u in P: continue                     # Already visited? Skip it
P[u] = p                                # Set path predecessor
if u == t: return d - h(t), P           # Arrived! Ret. dist and preds
for v in G[u]:                          # Go through all neighbors
w = G[u][v] - h(u) + h(v)           # Modify weight wrt heuristic
heappush(Q, (d + w, u, v))          # Add to queue, w/heur as pri
return inf, None                            # Didn't get to t

class PrimeChain(object):

def __init__(self):
self.M = {}

def variants(self, strn):
va = list(strn)
for i, c in enumerate(va):
digits = "123456789" if i == 0 else "0123456789"
for d in digits:
if d == c:
continue
va[i] = d
newstrn = "".join(va)
if is_prime(int(newstrn)):
yield newstrn
va[i] = c

def __getitem__(self, strn):
if strn not in self.M:
self.M[strn] = dict.fromkeys(self.variants(strn), 1)
return self.M[strn]

def heuristic(self, u, v):
return sum(a != b for a, b in zip(u, v))

def chain(self, s, t, h=None):
if h is None:
def h(v):
return self.heuristic(v, t)
_, P = a_star(self, s, t, h)
if P is None:
return [s, None, t]
u, p = t, []
while u is not None:
p.append(u)
u = P[u]
p. reverse()
return p

G = PrimeChain()
print(G.chain("71549", "10067"))
p1 = 76520965667
p2 = 59340926171
print(G.chain(str(p1), str(p2)))

"""
['71549', '71569', '71069', '11069', '10069', '10067']
['76520965667', '70520965667', '70540965667', '79540965667', '79040965667',
'79040965657', '79040965651', '79040966651', '79040966671', '59040966671',
'59040926671', '590409261 71', '59340926171']
"""
```
2. Rutger said

Hi,

Created a Depth-First search algorithm. This, off-course, goes bananas without a proper heuristic on getting closer to the target prime. This was done using the Hamming distance. Also set a limit of max depth (best) = 100 due to recursion depth limits.

Also found out that the is_prime function has many calls with the same argument, so cached the results using memoization.

I recon BFS would be a better approach judging from your solutions, anyway here’s my result:

```import random
import string

def memoize(f):
memo = {}
def helper(x):
if x not in memo:
memo[x] = f(x)
return memo[x]
return helper

@memoize
def is_prime(number):
# wheel / trial division
for i in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199):
if not (number % i):
return False
i = 203
while i <= number**0.5:
if not (number % i):
return False
i += 2
return True

digits_with_0 = string.digits
digits_without_0 = string.digits.replace("0", "")

def prime_neighbours(number):
n = str(number)
result = []
for i,v in enumerate(n):
if i == 0:
digits = digits_without_0
else:
digits = digits_with_0
for d in digits:
neighbour = list(n)
if d != neighbour[i]:
neighbour[i] = d
p = int("".join(neighbour))
if is_prime(p):
result.append(p)
return result

best = 100

def find_chain(current_chain, target, solutions):
global best
# if random.random() < 0.1:
# print(best, current_chain)
solutions = []
n = prime_neighbours(current_chain[-1])
# add hamming distance for sorting
z = [(sum(c1 == c2 for c1, c2 in zip(list(str(p1)), list(str(target)))), p1) for p1 in n]
z.sort(reverse=True)
for dummy, p2 in z:
if len(current_chain) + 1 < best and p2 not in current_chain:
if p2 == target:
solutions.append(current_chain + [p2])
print("#", len(solutions[-1]), solutions[-1])
best = len(current_chain)+1
else:
for s in find_chain(current_chain+[p2], target, solutions):
solutions.append(s)
return solutions

start = 71549
end = 10067

print(find_chain([start], end, []))
```