A051252
David Wilson
davidwwilson at attbi.com
Wed Jun 19 05:30:48 CEST 2002
----- Original Message -----
From: "Jud McCranie" <jud.mccranie at mindspring.com>
To: "Gordon Royle" <gordon at cs.uwa.edu.au>
Cc: <seqfan at ext.jussieu.fr>
Sent: Tuesday, June 18, 2002 12:17 AM
Subject: Re: A051252
> At 08:58 AM 6/18/2002 +0800, Gordon Royle wrote:
> >Sequence A051252 is the number of ways of arranging the integers 1..2n on
a
> >circle so that the sum of any two adjacent numbers is prime.
> >
> >The numbers get large very quickly.
> >
> >But is there any proof that this can always be done?
>
> I don't know of any proof, but I expect it to be true.
I would be skeptical of a proof, given the Goldbachish character of the
problem.
I will make this observation, though.
Let Gn be the graph whose vertices are the integers 1 through 2n, and whose
edges
connect pairs of integers whose sum is prime. The problem then devolves to
counting the Hamiltonian circuits in Gn.
For a general graph, finding a single Hamiltonian circuit is NP-complete.
From
this I would suspect that, for a general graph, confirming existence or
counting
Hamiltonian circuits is just as hard. I also suspect that Gn does not have
enough
useful structure to reduce the difficulty of counting the Hamiltonian
circuits.
More information about the SeqFan
mailing list