A073364 Number of permutations p of (1,2,3,...,n) such that k+p(k) is prime for 1<=k<=n.

1, 1, 1, 4, 1, 9, 4, 36, 36, 676, 400, 9216, 3600, 44100, 36100, 1223236, 583696, 14130081, 5461569, 158180929, 96275344, 5486661184, 2454013444, 179677645456, 108938283364, 5446753133584, 4551557699844, 280114147765321, 125264064932449, 9967796169000201

Offset: 1

Author

Benoit Cloitre, Aug 23 2002

Keywords

• nonn

Comments

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

Links

• Jinyuan Wang, Table of n, a(n) for n = 1..50
• Paul Bradley, Prime Number Sums, arXiv:1809.01012 [math.GR], 2018.
• Zhi-Wei Sun, On permutations of {1, ..., n} and related topics, arXiv:1811.10503 [math.CO], 2018.

Crossrefs

Cf. A000341, A069191, A070897, A134293, A321610, A321611.

Programs

Haskell

a073364 n = length $ filter (all isprime)
                     $ map (zipWith (+) [1..n]) (permutations [1..n])
   where isprime n = a010051 n == 1  -- cf. A010051
-- Reinhard Zumkeller, Mar 19 2011

Mathematica

am[n_] := Permanent[Array[Boole[PrimeQ[2 #1 + 2 #2 - 1]]&, {n, n}]];
ap[n_] := Permanent[Array[Boole[PrimeQ[2 #1 + 2 #2 + 1]]&, {n, n}]];
a[n_] := If[n == 1, 1, If[EvenQ[n], am[n/2]^2, ap[(n-1)/2]^2]];
Array[a, 28] (* Jean-François Alcover, Nov 03 2018 *)

PARI

a(n)=sum(k=1,n!,n==sum(i=1,n,isprime(i+component(numtoperm(n,k),i))))

PARI

a(n)={matpermanent(matrix(n,n,i,j,isprime(i + j)))} \\ Andrew Howroyd, Nov 03 2018

Formula

a(2n) = A000341(n)^2 and a(2n+1) = A134293(n)^2. - T. D. Noe, Oct 16 2007

Extensions

a(10) from Mohammed Bouayoun (bouyao(AT)wanadoo.fr), Mar 14 2004

a(11) from Rick L. Shepherd, Mar 17 2004

a(12)-a(17) from John W. Layman, Jul 21 2004

More terms from T. D. Noe, Oct 16 2007