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,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

Table of n, a(n) for n=1..30.

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

Cf. A051252, A072617, A072618.

Sequence in context: A197483 A366018 A019954 * A059627 A200603 A159591

Adjacent sequences: A072613 A072614 A072615 * A072617 A072618 A072619

Keyword

nice,nonn

Author

T. D. Noe, Jun 25 2002

Status

approved