cp's OEIS Frontend

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.

%I A072616 #9 Feb 16 2025 08:32:46
%S A072616 1,1,1,1,4,8,2,5,18,2,9,100,80,224,567,200,225,2535,1573,10890,132651,
%T A072616 34476,79768,319740,42282,257337,3445032,4274240,36781568,260272120
%N 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.
%C A072616 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 A072616 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PrimeCircle.html">Prime Circle.</a>
%e A072616 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 A072616 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 A072616 Cf. A051252, A072617, A072618.
%K A072616 nice,nonn
%O A072616 1,5
%A A072616 _T. D. Noe_, Jun 25 2002