login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A228626 Number of Hamiltonian cycles in the undirected simple graph G_n with vertices 1,...,n which has an edge connecting vertices i and j if and only if |i-j| is prime. 7
0, 0, 0, 0, 1, 2, 4, 16, 60, 186, 433, 2215, 11788, 76539, 414240, 2202215, 9655287, 69748712, 444195809, 3703859949, 26688275292, 201673532931, 1265944917365, 11801735916539, 92511897525830, 753795624276096, 5237677221537738, 41074291450736424, 280906738160126067 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,6

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_1-i_2|, |i_2-i_3|, ..., |i_{n-1}-i_n| and |i_n-i_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, Yong-Gao 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,...,2k-5,2k-3,2k,2k-2,2k-4,2k-1,2k-6,2k-8,...,6,4);

if n = 2*k + 1 then G_n contains a Hamiltonian cycle

  (1,3,5,2,7,9,...,2k-5,2k,2k-3,2k-1,2k+1,2k-2,2k-4,...,6,4).

We have got Chen's approval to include his proof here.

LINKS

Table of n, a(n) for n=1..29.

S. Sykora, On Neighbor-Property Cycles, Stan's Library, Volume V, 2014. See Table II.

Index entries for sequences related to graphs, Hamiltonian

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

MATHEMATICA

Table[Length[FindHamiltonianCycle[Graph[Flatten[Table[If[PrimeQ[Abs[i - j]], i \[UndirectedEdge] j, {}], {i, 1, n}, {j, i + 1, n}]]], Infinity]], {n, 1, 15}] (* Robert Price, Apr 04 2019 *)

PROG

(C++) listed in the link (S. Sykora)

CROSSREFS

Cf. A000040, A051239, A051252, A185645, A227050, A242527, A242528.

Sequence in context: A153954 A275764 A053349 * A152876 A153963 A153960

Adjacent sequences:  A228623 A228624 A228625 * A228627 A228628 A228629

KEYWORD

nonn,hard

AUTHOR

Zhi-Wei Sun, Aug 28 2013

EXTENSIONS

a(9)-a(17) from Alois P. Heinz, Aug 28 2013

a(18)-a(19) from Stanislav Sykora, May 30 2014

a(20)-a(29) from Max Alekseyev, Jul 04 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 16 17:04 EST 2019. Contains 329201 sequences. (Running on oeis4.)