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:

primepuzzle11

The Hamiltonian cycle is highlighted in red:

primepuzzle12

The solution is now easily visualized:
primepuzzle13

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).

Advertisements
Categories: Mathematica, Mathematics
  1. June 20, 2013 at 11:13 am
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: