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

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, []))
    

Leave a Reply

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: