login
A073364
Number of permutations p of (1,2,3,...,n) such that k+p(k) is prime for 1<=k<=n.
12
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,4
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
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.
FORMULA
a(2n) = A000341(n)^2 and a(2n+1) = A134293(n)^2. - T. D. Noe, Oct 16 2007
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 *)
PROG
(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
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
Benoit Cloitre, Aug 23 2002
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
STATUS
approved