cp's OEIS Frontend

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

%I A000341 #44 Sep 22 2023 05:15:14
%S A000341 1,2,3,6,26,96,210,1106,3759,12577,74072,423884,2333828,16736611,
%T A000341 99838851,630091746,4525325020,38848875650,342245714017,3335164762941,
%U A000341 31315463942337,241353231085002,2350106537365732,17903852593938447,158065352670318614,1815064841856534244,20577063085601738871,276081763499377227299
%N A000341 Number of ways to pair up {1..2n} so sum of each pair is prime.
%H A000341 Martin Fuller, <a href="/A000341/b000341.txt">Table of n, a(n) for n = 1..36</a>
%H A000341 L. E. Greenfield and S. J. Greenfield, <a href="https://cs.uwaterloo.ca/journals/JIS/green.html">Some Problems of Combinatorial Number Theory Related to Bertrand's Postulate</a>, J. Integer Sequences, 1998, #98.1.2.
%F A000341 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
%e A000341 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:
%e A000341 1+2, 3+4, 5+8, 6+7
%e A000341 1+2, 3+8, 4+7, 5+6
%e A000341 1+4, 2+3, 5+8, 6+7
%e A000341 1+4, 2+5, 3+8, 6+7
%e A000341 1+6, 2+3, 4+7, 5+8
%e A000341 1+6, 2+5, 3+8, 4+7
%e A000341 Therefore a(4) = 6. - _Michael B. Porter_, Jul 19 2016
%p A000341 f:= proc(n) local M;
%p A000341   M:= Matrix(n,n,(i,j) -> `if`(isprime(2*i+2*j-1),1,0));
%p A000341   LinearAlgebra:-Permanent(M)
%p A000341 end proc:
%p A000341 map(f, [$1..20]); # _Robert Israel_, Jul 19 2016
%t A000341 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 *)
%o A000341 (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)
%o A000341 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
%o A000341 (PARI) a(n)=matpermanent(matrix(n,n,i,j,isprime(2*(i+j)-1))); \\ _Martin Fuller_, Sep 22 2023
%Y A000341 Cf. A005326, A009692.
%K A000341 nonn,nice
%O A000341 1,2
%A A000341 S. J. Greenfield (greenfie(AT)math.rutgers.edu)
%E A000341 More terms from _David W. Wilson_
%E A000341 More terms from _T. D. Noe_, Feb 10 2007
%E A000341 More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), May 13 2007
%E A000341 More terms from _Sean A. Irvine_, Nov 14 2010