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,3

Links

Table of n, a(n) for n=1..31.

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.

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

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 *)

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

Crossrefs

Cf. A000341.

Sequence in context: A363250 A181817 A362227 * A168342 A309515 A375551

Adjacent sequences: A000345 A000346 A000347 * A000349 A000350 A000351

Keyword

nonn,nice

Author

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

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

Status

approved