login
A072616
Number of essentially different ways of arranging numbers 1 through 2n around a circle so that the sum of each pair of adjacent numbers is prime and the odd (or even) numbers are in order.
4
1, 1, 1, 1, 4, 8, 2, 5, 18, 2, 9, 100, 80, 224, 567, 200, 225, 2535, 1573, 10890, 132651, 34476, 79768, 319740, 42282, 257337, 3445032, 4274240, 36781568, 260272120
OFFSET
1,5
COMMENTS
A restricted form of the prime circle problem whose sequence is A051252. Note that a(2)=1 because the two solutions are essentially the same. The number of solutions is the same for odd or even numbers in order because a solution having the odd numbers in order can be converted to a solution having even numbers in order by subtracting 1 from even numbers and adding 1 to odd numbers. For example, {1, 2, 3, 8, 5, 6, 7, 4, 9, 10} becomes {2, 1, 4, 7, 6, 5, 8, 3, 10, 9}. Is the number of solutions always positive? See A072617 for some simple solutions to the prime circle problem.
LINKS
Eric Weisstein's World of Mathematics, Prime Circle.
EXAMPLE
a(5) = 4 because there are four ways: {1,2,3,8,5,6,7,4,9,10}, {1,2,3,8,5,6,7,10,9,4}, {1,4,3,8,5,6,7,10,9,2} and {1,10,3,8,5,6,7,4,9,2}.
MATHEMATICA
maxN=14; $RecursionLimit=500; try[lev_] := Module[{t, j}, If[lev>2n, (*found a solution*)(*Print[soln]; *) cnt++, (*else append another number to the soln list*) t=soln[[lev-1]]; If[OddQ[lev], (*odd level*) soln[[lev]]=lev; try[lev+1]; soln[[lev]]=0, For[j=1, j<=Length[s[[t]]], j++, (*even level*) If[ !MemberQ[soln, s[[t]][[j]]], soln[[lev]]=s[[t]][[j]]; try[lev+1]; soln[[lev]]=0]]]]]; For[lst={}; n=1, n<=maxN, n++, s=Table[{}, {2n}]; For[i=1, i<=2n, i=i+2, For[j=1, j<=2n, j++, If[i!=j&&PrimeQ[i+j]&&PrimeQ[Mod[i+2, 2n]+j], AppendTo[s[[i]], j]]]]; soln=Table[0, {2n}]; soln[[1]]=1; cnt=0; try[2]; AppendTo[lst, cnt]]; lst
CROSSREFS
KEYWORD
nice,nonn
AUTHOR
T. D. Noe, Jun 25 2002
STATUS
approved