[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

356.0. "A Hamiltonian Graph" by TOOLS::STAN () Thu Oct 17 1985 16:45

(Ernst Straus)

For n>1, draw a graph with the vertices 1,2,...,2n and join
two vertices i,j with an edge just if i+j is prime.
Is this graph Hamiltonian?
T.RTitleUserPersonal
Name
DateLines
356.1TOOLS::STANSat Oct 19 1985 01:0517
In case the graph theoretic formulation makes you scared of this problem,
here's the recreational math formulation:

Can you place the numbers from 1 to 2n in a circle so that each pair
of adjacent numbers sum to a prime?

For example, for n=4, we place the 8 numbers as follows:

	1 - 2 - 3 - 8 - 5 - 6 - 7 - 4

[Note that 1+4 is required to be a prime too.]

Does anyone out there have an urge to create such a path for
various n?  (Hamiltonian path algorithms can be found in
Nijenhuis and Wilf as well as various graph theory books, if you don't
feel like writing your own algorithm.  A straightforward backtrack 
algorithm should work too.)