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.
Advertisements
Pages: 1 2
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'] """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, []))