A071058 Number of ways of pairing odd numbers in the range 1 to n with even numbers in the range n+1 to 2n such that each pair sums to a prime.

1, 1, 1, 1, 2, 2, 4, 6, 10, 7, 21, 11, 40, 53, 215, 181, 773, 939, 3260, 4432, 23431, 15811, 80724, 67891, 429108, 434963, 2748239, 2718150, 21654009, 21580655, 107459138, 92370364, 638616984, 564878656, 5055810584, 4545704064, 35787453599, 36878092180

Offset: 1

Author

T. D. Noe, May 25 2002

Keywords

• hard
• nice
• nonn

Examples

			a(5)=2 because there are two ways: 1+10, 3+8, 6+5 and 1+6, 3+10, 5+8.
		

Links

• Martin Fuller, Table of n, a(n) for n = 1..70

Crossrefs

The product of this sequence and A071059 gives A070897.

Programs

Mathematica

a[n_] := a[n] = Module[{s1, s2, s3, s4, i, ik, km},
s1 = Select[Flatten[Outer[List, Range[1, n, 2], Range[2n, n+1, -2]], 1],
   PrimeQ[Total[#]]&];
s2 = SplitBy[s1, First];
km = Length[s2];
ik = Table[{i[k], 1, Length[s2[[k]]]}, {k, 1, km}];
s3 = Table[Table[s2[[k, i[k]]], {k, 1, km}], Evaluate[Sequence @@ ik]] //
   Flatten[#, km-1]&;
s4 = Select[s3, Length[Union[Flatten[#]]] == 2km&];
s4 // Length];
Table[Print[n, " ", a[n]]; a[n], {n, 1, 20}] (* Jean-François Alcover, Aug 10 2022 *)

PARI

a(n)=matpermanent(matrix((n+1)\2,(n+1)\2,i,j,isprime((i+j-2)*2+n+3-(n%2)))); \\ Martin Fuller, Sep 21 2023

Formula

a(2n) = A071059(2n).

Extensions

More terms from David W. Wilson, May 27 2002

a(31)-a(36) from Donovan Johnson, Aug 12 2010