A000348 Number of ways to pair up {1^2, 2^2, ..., (2n)^2 } so sum of each pair is prime.

1, 1, 2, 4, 12, 9, 72, 160, 428, 2434, 3011, 10337, 126962, 264182, 783550, 5004266, 34340141, 176302123, 1188146567, 4457147441, 7845512385, 132253267889, 1004345333251, 3865703506342, 40719018858150, 213982561376958, 1266218151414286, 10976172953868304, 59767467676582641, 512279001476451101, 6189067229056357433

Offset: 1

Author

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

Keywords

• nonn
• nice

Links

• B. K. Agarwala and F. C. Auluck, Statistical mechanics and partitions into non-integral powers of integers, Proc. Camb. Phil. Soc., 47 (1951), 207-216. [Annotated scanned copy]
• 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.

Crossrefs

Cf. A000341.

Programs

Mathematica

a[n_] := Permanent[Table[Boole[PrimeQ[(2*i)^2 + (2*j - 1)^2]], {i, 1, n}, {j, 1, n}]]; Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 1, 22}] (* Jean-François Alcover, Jan 06 2016, after T. D. Noe *)

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)^2+(2*j-1)^2));print1(permRWNb(a)", ")) \\ Herman Jamke (hermanjamke(AT)fastmail.fm), May 13 2007

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)^2+(2j-1)^2 is prime or composite, respectively. - T. D. Noe, Feb 10 2007

Extensions

a(11)-a(16) from David W. Wilson

a(17)-a(22) from T. D. Noe, Feb 10 2007

a(23)-a(24) from Herman Jamke (hermanjamke(AT)fastmail.fm), May 13 2007

More terms from Sean A. Irvine, Nov 14 2010