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.

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

Author

T. D. Noe, Jun 25 2002

Keywords

• nice
• nonn

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.

Examples

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

Links

• Eric Weisstein's World of Mathematics, Prime Circle.

Crossrefs

Cf. A051252, A072617, A072618.

Programs

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