
COMMENTS

Conjecture: a(n) > 0 for all n > 4. In other words, for each n = 5,6,... there is a permutation i_1,...,i_n of 1,...,n such that i_1i_2, i_2i_3, ..., i_{n1}i_n and i_ni_1 are all prime.
Note that this conjecture is different from the prime circle problem in A051252 though they look similar.
On August 30 2013, YongGao Chen (from Nanjing Normal University) confirmed the conjecture for n > 12 as follows: If n = 2*k then G_n contains a Hamiltonian cycle (1,3,5,2,7,9,...,2k5,2k3,2k,2k2,2k4,2k1,2k6,2k8,...,6,4);
if n = 2*k + 1 then G_n contains a Hamiltonian cycle
(1,3,5,2,7,9,...,2k5,2k,2k3,2k1,2k+1,2k2,2k4,...,6,4).
We have got Chen's approval to include his proof here.


EXAMPLE

a(5) = 1 since G_5 contains the unique Hamiltonian cycle (1,4,2,5,3).
a(6) = 2 since G_6 contains exactly two Hamiltonian cycles: (1,3,5,2,4,6) and (1,4,2,5,3,6).
a(7) = 4 since G_7 contains exactly four Hamiltonian cycles: (1,3,5,2,7,4,6), (1,3,5,7,2,4,6), (1,4,2,7,5,3,6) and (1,4,7,2,5,3,6).
a(8) = 16 since G_8 contains exactly 16 Hamiltonian cycles: (1,3,5,2,7,4,6,8), (1,3,5,7,2,4,6,8), (1,3,6,4,2,7,5,8), (1,3,6,4,7,2,5,8), (1,3,6,8,5,2,7,4), (1,3,6,8,5,7,2,4), (1,3,8,5,2,7,4,6), (1,3,8,5,7,2,4,6), (1,4,2,7,5,3,6,8), (1,4,2,7,5,3,8,6), (1,4,2,7,5,8,3,6), (1,4,7,2,5,3,6,8), (1,4,7,2,5,3,8,6), (1,4,7,2,5,8,3,6), (1,6,4,2,7,5,3,8), (1,6,4,7,2,5,3,8).
a(9) > 0 since (1,3,5,7,9,2,4,6,8) is a Hamiltonian cycle in G_9.
a(10) > 0 since (1,3,5,2,4,6,9,7,10,8) is a Hamiltonian cycle in G_{10}.
a(11) > 0 since (1,3,5,10,8,11,9,2,7,4,6) is a Hamiltonian cycle in G_{11}.
a(12) > 0 since (1,3,8,10,5,2,7,4,6,11,9,12) is a Hamiltonian cycle in G_{12}.
