SPOJ PPATH, Conversione di un dato primo di 4 cifre in un altro numero a 4 cifre

Question

Nel problema SPOJ PPATH ci vengono dati due numeri primi a quattro cifre e dobbiamo convertire, nel minor tempo possibile, il primo primo nel secondo cambiando una singola cifra alla volta e ad ogni passaggio il numero dovrebbe essere primo. Dobbiamo produrre 'IMPOSSIBLE' se i numeri primi non possono essere convertiti in modo detto.

Tuttavia, le soluzioni al problema in cui il caso impossibile non è nemmeno considerato sono state accettate, il che porta a congetturare che ogni primo di quattro cifre può essere convertito in qualsiasi altro primo di quattro cifre nel modo specificato. Non ero in grado di dimostrarlo. È vero? Come possiamo dimostrarlo formalmente? Inoltre, c'è un risultato generale per i numeri primi di n cifre?

Answer 1

Per il numero di quattro cifre questo può essere verificato in modo esaustivo attraverso un programma ma per n cifra dovremo dimostrarlo in teoria.

Answer 2

Bene, quindi si ha un grafico non orientato con i vertici come numeri primi a 4 cifre e un bordo che collega due numeri che differiscono in 1 cifra. Ti viene chiesto di trovare il percorso più vicino da un vertice all'altro. Il risultato IMPOSSIBILE verrà prodotto se non sarai in grado di trovare tale percorso. Ciò significherebbe che il grafico ha più di un componente connesso. Se si dimostra che questo grafico ha un componente connesso, garantirà l'esistenza del percorso.

Non so come dimostrarlo in modo formale ma è molto facile controllare se il grafico sopra descritto ha solo un componente connesso. È possibile scrivere un algoritmo e il suo risultato può essere interpretato come una prova per un caso specifico di grafici a 4 cifre.