A072616 - OEIS

%I #8 Nov 21 2012 14:38:41

%S 1,1,1,1,4,8,2,5,18,2,9,100,80,224,567,200,225,2535,1573,10890,132651,

%T 34476,79768,319740,42282,257337,3445032,4274240,36781568,260272120

%N 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.

%C 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.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PrimeCircle.html">Prime Circle.</a>

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

%t 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

%Y Cf. A051252, A072617, A072618.

%K nice,nonn

%O 1,5

%A _T. D. Noe_, Jun 25 2002