Converting prime numbers

Question

Possible Duplicate:
Help with algorithm problem from SPOJ

Came across this interview question. Given two n-digit prime numbers, convert the first prime number to the second changing one digit at a time. The intermediate numbers also need to be prime. This needs to be done in the minimum number of steps (checking for primality and changing a digit are considered steps)

E.g. convert 1033 to 8179 (1033->1733->3733->.......->8179)

Answer 1

This is (a special case of) the shortest path problem. You're looking for a minimal path between two specified vertices, through the graph where the vertices are the primes, and vertices are connected by an edge if and only if they differ at exactly one digit when expressed in base 10. All edges have weight 1.

In the absence of a better idea for the particular structure of this special case: for 4 digits this can surely be completed in negligible time with your favourite path-finding algorithm.

Edit: oops, just noticed that "checking for primality" is a step.

I no longer understand the question. How many numbers do you have to "check for primality" in order to produce the chain 1033 -> 1733 -> 3733? If I use a sieve to find all primes less than 10000, how many "steps" has that taken?

Answer 2

The best approach is probably depth-first search with iterative deepening, since the minimum number of steps is requested. The initial depth would be the number of digits that are different between the two numbers.

Answer 3

This can be thought as a graph problem. I would try something along these lines:

• Generate all N-digit prime numbers (P) without the start prime (A) and end prime (B).
• Compute hamming distance from A to all P, pick ones that has distance of 1, set them as children of A.
• Repeat this until all primes from P has put into the graph or a path to B has been found.
• Take the shortest path from A to B.

Answer 4

Nice challenge for a rainy Monday evening (it is here, anyway!). This can be done using Dijkstra's algorithm. The first step is to create a graph containing all 4-digit primes. Then use Dijkstra's algorithm to find the shortest path between the start/end primes. Here's an implementation in Python:

#! /usr/bin/python -tt

# run as: findpath start end

import sys

(start, end) = map(int, sys.argv[1:3])

# http://primes.utm.edu/lists/small/10000.txt
f = open("10000.txt", "r")
lines = f.readlines()
f.close
lines = lines[4:-1] # remove header/footer
all = "".join(lines) # join lines
all = all.split()
all = map(int, all)

# only want the 4-digit primes
fourdigit = [p for p in all if 1000 <= p and p <= 9999]

# returns digits in a number
digits = lambda x: map(int, str(x))

# cache of digits for each prime
digits_for_nums = {}

# returns digits in a number (using cache)
def digits_for_num(x):
    global digits_for_nums
    if x not in digits_for_nums:
        digits_for_nums[x] = digits(x)
    return digits_for_nums[x]

# returns 1 if digits are same, 0 otherwise
diff = lambda pair: 1 if pair[0] == pair[1] else 0

# computes number of identical digits in two numbers
def distance(a, b):
    pair = (a, b)
    pair = map(digits_for_num, pair)
    pair = zip(pair[0], pair[1])
    pair = map(diff, pair)
    same = sum(pair)
    return same

# adjacency list representation of graph of primes
edges = {}

# construct graph
for a in fourdigit:
    edges[a] = []
    for b in fourdigit:
        if distance(a, b) == 3:
            edges[a].append(b)

infinity = sys.maxint

def smallest():
    global dist, Q
    minimum = infinity
    which = None
    for v in Q:
        if dist[v] <= minimum:
            which = v
            minimum = dist[v]
    return which

# Dijkstra's algorithm
dist = {}
previous = {}
Q = edges.keys()
for v in Q:
    dist[v] = infinity
    previous[v] = None
dist[start] = 0
while len(Q) > 0:
    u = smallest()
    if dist[u] == infinity:
        break
    Q.remove(u)
    for v in edges[u]:
        alt = dist[u] + 1
        if alt < dist[v]:
            dist[v] = alt
            previous[v] = u

# get path between start/end nodes
num = end
path = [num]
while num != start:
    num = previous[num]
    path.insert(0, num)
print path