Home > Mathematica, Mathematics > Salesman on a Circle

## Salesman on a Circle

I explore a puzzle about arranging a set of integers (1,2,3,…14) in a circle such that the any pair of numbers next to each have the property that their sum is prime and the absolute difference is prime. I came across this from a tweet by Professor Strogatz (the link is here).

This is the “Travelling Salesman” problem in disguise.  The mindless brute force approaches of  testing permutations (all the pairs) and finding gives an insight into the scalability issue of this problem. The issue of whether a solution exists for the small scale was resolved by finding it! Whether it s unique is a harder but fortunately the enormity of comparisons can be whittled down.

After a little thought, the property defines the way in which the integers are linked. It is a bipartite graph as the odd numbers must link to even numbers. This can be seen from odd+odd=even =composite (as >2); even+even=even =composite (>2). This immediately reduces the number of comparisons.  The resulting graph provided a visualization that allowed me to “search and find” the Hamiltonian cycle, the solution to the problem.

Mathematica provided a very nice way of doing this and allowing visualization. `FindHamiltonianCyle` from the `GraphUtilities` package found the same cycle: reassuring but I did enjoy looking at the graph and working through (e.g. it is certain that the edges of vertices with degree 2 must be in the cycle).

The graph is illustrated in the figure below:

The Hamiltonian cycle is highlighted in red:

The solution is now easily visualized:

The graph was generated using the following code:
``` odd = Range[1, 13, 2]; even = Range[2, 14, 2]; prt[u_] := PrimeQ@(Plus @@ u) && PrimeQ[Abs[Differences@u][[1]]]; graph = Join @@ (Cases[#,x_?(prt@# &) :> (x[[1]] \[UndirectedEdge] x[[2]])] & /@ Outer[List, odd, even]); ```

I am sure there are better ways. I also have not explored what algorithm Mathematica uses. However, I enjoyed this puzzle.

Note:

There are 28 ways  (number of ways 12 o’clock position can be filled x number of orientations =14 x 2)of  representing the same cycle. I merely chose one…

The following animation takes a random layout of the graph and manipulates it to “reveal” the Hamiltonian cycle” (red edges), i.e. changes the layout of the cycle from a tangle to a convex polygon.

The CDF is available here. You can untangle the messy graph yourself (needs CDF Player plugin).