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

%I #40 Jun 13 2020 09:55:21

%S 1,1,1,4,1,9,4,36,36,676,400,9216,3600,44100,36100,1223236,583696,

%T 14130081,5461569,158180929,96275344,5486661184,2454013444,

%U 179677645456,108938283364,5446753133584,4551557699844,280114147765321,125264064932449,9967796169000201

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

%C 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

%H Jinyuan Wang, <a href="/A073364/b073364.txt">Table of n, a(n) for n = 1..50</a>

%H Paul Bradley, <a href="https://arxiv.org/abs/1809.01012">Prime Number Sums</a>, arXiv:1809.01012 [math.GR], 2018.

%H Zhi-Wei Sun, <a href="https://arxiv.org/abs/1811.10503">On permutations of {1, ..., n} and related topics</a>, arXiv:1811.10503 [math.CO], 2018.

%F a(2n) = A000341(n)^2 and a(2n+1) = A134293(n)^2. - _T. D. Noe_, Oct 16 2007

%t am[n_] := Permanent[Array[Boole[PrimeQ[2 #1 + 2 #2 - 1]]&, {n, n}]];

%t ap[n_] := Permanent[Array[Boole[PrimeQ[2 #1 + 2 #2 + 1]]&, {n, n}]];

%t a[n_] := If[n == 1, 1, If[EvenQ[n], am[n/2]^2, ap[(n-1)/2]^2]];

%t Array[a, 28] (* _Jean-François Alcover_, Nov 03 2018 *)

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

%o (PARI) a(n)={matpermanent(matrix(n,n,i,j,isprime(i + j)))} \\ _Andrew Howroyd_, Nov 03 2018

%o (Haskell)

%o a073364 n = length $ filter (all isprime)

%o $ map (zipWith (+) [1..n]) (permutations [1..n])

%o where isprime n = a010051 n == 1 -- cf. A010051

%o -- _Reinhard Zumkeller_, Mar 19 2011

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

%K nonn

%O 1,4

%A _Benoit Cloitre_, Aug 23 2002

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

%E a(11) from _Rick L. Shepherd_, Mar 17 2004

%E a(12)-a(17) from _John W. Layman_, Jul 21 2004

%E More terms from _T. D. Noe_, Oct 16 2007