

A051252


Number of essentially different ways of arranging numbers 1 through 2n around a circle so that sum of each pair of adjacent numbers is prime.


25



1, 1, 1, 2, 48, 512, 1440, 40512, 385072, 3154650, 106906168, 3197817022, 82924866213, 4025168862425, 127854811616691
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,4


COMMENTS

Jud McCranie reports that he was able to find a solution for each n <= 225 (2n <= 450) in just a few seconds.  Jul 05 2002
Is there a proof that this can always be done?
The Mathematica program for this sequence uses backtracking to find all solutions for a given n. To verify that at least one solution exists for a given n, the backtracking function be made to stop when the first solution is found. Solutions have been found for n <= 48.  T. D. Noe, Jun 19 2002
This sequence is from the prime circle problem. There is no known proof that a(n) > 0 for all n. However, for many n (see A072618 and A072676), we can prove that a(n) > 0. Also, the sequence A072616 seems to imply that there are always solutions in which the odd (or even) numbers are in order around the circle.  T. D. Noe, Jul 01 2002
Prime circles can apparently be generated for any n using the Mathematica programs given in A072676 and A072184.  T. D. Noe, Jul 08 2002
The following seems to always produce a solution: Work around the circle starting with 1 but after that always choosing the largest remaining number that fits. For example, if n = 4 this gives 1, 6, 7, 4, 3, 8, 5, 2. See A088643 for a sequence on a related idea.  Paul Boddington, Oct 30 2007
See A228917 for a similar conjecture on twin primes.  ZhiWei Sun, Sep 08 2013
See A242527 for a similar problem on the set of numbers {0 through (n1)}.  Stanislav Sykora, May 30 2014
James Tilley and Stan Wagon report that all terms up to n = 10^6 are nonzero. Charles R Greathouse IV, Feb 05 2016


REFERENCES

R. K. Guy, Unsolved Problems in Number Theory, second edition, Springer, 1994. See section C1.


LINKS

Table of n, a(n) for n=1..15.
S. Sykora, On NeighborProperty Cycles, Stan's Library, Volume V, 2014.
Eric Weisstein's World of Mathematics, Prime Circle.


EXAMPLE

One arrangement for 2n=6 is 1,4,3,2,5,6 and this is essentially unique, so a(3)=1.


MATHEMATICA

$RecursionLimit=500; try[lev_] := Module[{t, j}, If[lev>2n, (*then make sure the sum of the first and last is prime*) If[PrimeQ[soln[[1]]+soln[[2n]]]&&soln[[2]]<=soln[[2n]], (*Print[soln]; *) cnt++ ], (*else append another number to the soln list*) t=soln[[lev1]]; For[j=1, j<=Length[s[[t]]], j++, If[ !MemberQ[soln, s[[t]][[j]]], soln[[lev]]=s[[t]][[j]]; try[lev+1]; soln[[lev]]=0]]]]; For[lst={}; n=1, n<=7, n++, s=Table[{}, {2n}]; For[i=1, i<=2n, i++, For[j=1, j<=2n, j++, If[i!=j&&PrimeQ[i+j], AppendTo[s[[i]], j]]]]; soln=Table[0, {2n}]; soln[[1]]=1; cnt=0; try[2]; AppendTo[lst, cnt]]; lst (* T. D. Noe *)


PROG

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


CROSSREFS

Cf. A000341, A070897, A072616, A072617, A072618, A072676, A072184, A103839, A227050, A228917, A242527, A242528.
Sequence in context: A101362 A215186 A058090 * A231654 A005429 A035606
Adjacent sequences: A051249 A051250 A051251 * A051253 A051254 A051255


KEYWORD

nonn,nice


AUTHOR

Jud McCranie


EXTENSIONS

a(14)a(15) from Max Alekseyev, Sep 19 2013


STATUS

approved



