5
$\begingroup$

Lewis Carroll's famous game of Doublets is well known. In it you are asked to transform a given word into another by changing only one letter at a time, forming a genuine new word (not a proper name) with each letter change.

Doublets with primes is identical except that instead of playing with words you play with prime numbers, say two 3-digit primes.

Question 1. Can any 3-digit prime be transformed into any other 3-digit number following the Doublet rule?

Question 2. What is the longest distance (i.e. the largest number of links required) between two 3-digit primes?

One could ask the same questions about 4-digit primes.

$\endgroup$
6
$\begingroup$

For the first question the answer is yes, for the second question the answer is 6,

To solve the question i used both (Java and Wolfram), the idea is this i made a graph with nodes being the primes with 3-digits and there is a line between two nodes iff the primes representing the nodes are 1-Doublet(meaning with one digit change we can transfer one into another) and then we can state you question as graph theory question which are :

1) is the graph connected ?

2) what is the graph diameter ?

building the graph using Java and answering the questions using Wolfram we are done.

it seems that this is true for any number of digits primes, but i don't think there is a simple proof.

$\endgroup$
  • 6
    $\begingroup$ Once we get to $6$ digits, the prime $294001$ has no neighbor primes, and the graph is disconnected. See weakly prime numbers. $\endgroup$ – Misha Lavrov May 5 at 23:35
  • $\begingroup$ @MishaLavrov so for $4,5$ digits primes it works, i want to find what is the diameter! $\endgroup$ – Ahmad May 5 at 23:41
  • 2
    $\begingroup$ For 4 digits, the longest distance is 8, between 2441 and 9199 (and other pairs). For 5 digits, the longest distance is 10, between 88259 and 99721. $\endgroup$ – Misha Lavrov May 5 at 23:49
9
$\begingroup$

I can confirm that the corresponding graph is connected. Moreover, it has a hamiltonian cycle:

Hamiltonian cycle

$\endgroup$
  • 1
    $\begingroup$ I would like this better if you included all edges somehow. Just including the edges for the (a?) Hamiltonian cycle suggests there aren't other edges. On the other hand, it would make the graph much more complicated. $\endgroup$ – Teepeemm May 6 at 1:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.