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 prime 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$

2 Answers 2

Reset to default
9
$\begingroup$

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

Hamiltonian cycle

$\endgroup$
1
  • 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, 2019 at 1:30
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$
3
  • 7
    $\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, 2019 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, 2019 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, 2019 at 23:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .