T.D. Noe 's nice one and Mathematica's "Backtrack"

[Wouter Meeussen]

A070897 is really a nice & hard sequence.
It is the first time I come accross an example that clearly demonstrates
the workings of Mathematica's "Backtrack" function.

Thanks T.D.

 %I A070897 %S A070897 1,1,1,1,2,4,8,36,40 %N A070897 Number of ways of
pairing numbers 1 to n with numbers n+1 to 2n such that each pair sums to a
prime. %e A070897 a(5)=2 because there are two ways: 1+10,2+9,3+8,4+7,6+5
and 1+6,2+9,3+10,4+7,5+8 %Y A070897 Cf. A000341. %K A070897
hard,more,nice,nonn,new %O A070897 1,5 %A A070897 T. D. Noe
(noe at sspectra.com), May 23 2002


<< DiscreteMath`Combinatorica`

listQpart2[n_]:={n-#,#}&/@Range[Floor[(n-1)/2]]

Noe[n_Integer]:=Module[{it,permoid,po},
      it=Union at Flatten[Cases[listQpart2[#],q_/;Max[q]<=2*n&&Max[q]>n]&
/@Select[Range[n+2,3*n],PrimeQ],1];
      po=Position[it,#]&/@Range[n];
      permoid=(Extract[it,#]-n)& /@(po /. {i_Integer,j_}->{i,1} );
      Length at Backtrack[permoid,UnsameQ@@#&,Length[#]===n&,All]  ]

Timing[Noe/@Range[2,16]]

{715.906 Second, {1, 1, 1, 2, 4, 8, 36, 40, 49, 126, 121, 440, 2809, 11395,
32761}}
and
Timing[Noe[17]]
{6847.84 Second, 132183}

PS.  judicious use of Backtrack could lead to some extention of many 'hard'
sequences in EIS.
it speeds up the search over an outer product like
Select[Flatten[Outer[z,Sequence@@permoid,1]]/.z->List,PermutationQ]

cheers,

Wouter Meeussen
wouter.meeussen at pandora.be