In the SPOJ problem PPATH we are given two four-digit prime numbers and we have to convert, in the least possible steps, the first prime into the second one by changing a single digit at a time and at each step the number should be prime. We have to output 'IMPOSSIBLE' if the primes cannot be converted in said fashion.
However, solutions to the problem in which the impossible case is not even considered have been accepted, which leads one to conjecture that every four-digit prime can be converted into any other four-digit prime in the specified manner. I was unable to prove it. Is it true? How can we prove it formally? Also, is there a general result for n-digit primes?
For four digit number this can be verified exhaustively through a program but for n digit we will have to prove it theoretically.