A000341 Number of ways to pair up {1..2n} so sum of each pair is prime.

1, 2, 3, 6, 26, 96, 210, 1106, 3759, 12577, 74072, 423884, 2333828, 16736611, 99838851, 630091746, 4525325020, 38848875650, 342245714017, 3335164762941, 31315463942337, 241353231085002, 2350106537365732, 17903852593938447, 158065352670318614, 1815064841856534244, 20577063085601738871, 276081763499377227299

Offset

1,2

Links

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

L. E. Greenfield and S. J. Greenfield, Some Problems of Combinatorial Number Theory Related to Bertrand's Postulate, J. Integer Sequences, 1998, #98.1.2.

Formula

a(n) = permanent(m), where the n X n matrix m is defined by m(i,j) = 1 or 0, depending on whether 2i+2j-1 is prime or composite, respectively. - T. D. Noe, Feb 10 2007

Example

For n=4, there are 6 ways to pair up {1, 2, 3, 4, 5, 6, 7, 8} so that each pair sums to a prime:
1+2, 3+4, 5+8, 6+7
1+2, 3+8, 4+7, 5+6
1+4, 2+3, 5+8, 6+7
1+4, 2+5, 3+8, 6+7
1+6, 2+3, 4+7, 5+8
1+6, 2+5, 3+8, 4+7
Therefore a(4) = 6. - Michael B. Porter, Jul 19 2016

Maple

f:= proc(n) local M;
  M:= Matrix(n, n, (i, j) -> `if`(isprime(2*i+2*j-1), 1, 0));
  LinearAlgebra:-Permanent(M)
end proc:
map(f, [$1..20]); # Robert Israel, Jul 19 2016

Mathematica

a[n_] := Permanent[ Array[ Boole[ PrimeQ[2*#1 + 2*#2 - 1]] & , {n, n}]]; Table[an = a[n]; Print[an]; an, {n, 1, 20}] (* Jean-François Alcover, Oct 21 2011, after T. D. Noe, updated Feb 07 2016 *)

Prog

(PARI) permRWNb(a)=n=matsize(a)[1]; if(n==1, return(a[1, 1])); sg=1; nc=0; in=vectorv(n); x=in; x=a[, n]-sum(j=1, n, a[, j])/2; p=prod(i=1, n, x[i]); for(k=1, 2^(n-1)-1, sg=-sg; j=valuation(k, 2)+1; z=1-2*in[j]; in[j]+=z; nc+=z; x+=z*a[, j]; p+=prod(i=1, n, x[i], sg)); return(2*(2*(n%2)-1)*p)
for(n=1, 24, a=matrix(n, n, i, j, isprime(2*(i+j)-1)); print1(permRWNb(a)", ")) \\ Herman Jamke (hermanjamke(AT)fastmail.fm), May 13 2007
(PARI) a(n)=matpermanent(matrix(n, n, i, j, isprime(2*(i+j)-1))); \\ Martin Fuller, Sep 22 2023

Crossrefs

Cf. A005326, A009692.

Sequence in context: A333420 A296259 A344935 * A144857 A090445 A228346

Adjacent sequences: A000338 A000339 A000340 * A000342 A000343 A000344

Keyword

nonn,nice

Author

S. J. Greenfield (greenfie(AT)math.rutgers.edu)

Extensions

More terms from David W. Wilson

More terms from T. D. Noe, Feb 10 2007

More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), May 13 2007

More terms from Sean A. Irvine, Nov 14 2010

Status

approved