cp's OEIS Frontend

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

%I A073364 #40 Jun 13 2020 09:55:21
%S A073364 1,1,1,4,1,9,4,36,36,676,400,9216,3600,44100,36100,1223236,583696,
%T A073364 14130081,5461569,158180929,96275344,5486661184,2454013444,
%U A073364 179677645456,108938283364,5446753133584,4551557699844,280114147765321,125264064932449,9967796169000201
%N A073364 Number of permutations p of (1,2,3,...,n) such that k+p(k) is prime for 1<=k<=n.
%C A073364 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 A073364 Jinyuan Wang, <a href="/A073364/b073364.txt">Table of n, a(n) for n = 1..50</a>
%H A073364 Paul Bradley, <a href="https://arxiv.org/abs/1809.01012">Prime Number Sums</a>, arXiv:1809.01012 [math.GR], 2018.
%H A073364 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 A073364 a(2n) = A000341(n)^2 and a(2n+1) = A134293(n)^2. - _T. D. Noe_, Oct 16 2007
%t A073364 am[n_] := Permanent[Array[Boole[PrimeQ[2 #1 + 2 #2 - 1]]&, {n, n}]];
%t A073364 ap[n_] := Permanent[Array[Boole[PrimeQ[2 #1 + 2 #2 + 1]]&, {n, n}]];
%t A073364 a[n_] := If[n == 1, 1, If[EvenQ[n], am[n/2]^2, ap[(n-1)/2]^2]];
%t A073364 Array[a, 28] (* _Jean-François Alcover_, Nov 03 2018 *)
%o A073364 (PARI) a(n)=sum(k=1,n!,n==sum(i=1,n,isprime(i+component(numtoperm(n,k),i))))
%o A073364 (PARI) a(n)={matpermanent(matrix(n,n,i,j,isprime(i + j)))} \\ _Andrew Howroyd_, Nov 03 2018
%o A073364 (Haskell)
%o A073364 a073364 n = length $ filter (all isprime)
%o A073364                      $ map (zipWith (+) [1..n]) (permutations [1..n])
%o A073364    where isprime n = a010051 n == 1  -- cf. A010051
%o A073364 -- _Reinhard Zumkeller_, Mar 19 2011
%Y A073364 Cf. A000341, A069191, A070897, A134293, A321610, A321611.
%K A073364 nonn
%O A073364 1,4
%A A073364 _Benoit Cloitre_, Aug 23 2002
%E A073364 a(10) from Mohammed Bouayoun (bouyao(AT)wanadoo.fr), Mar 14 2004
%E A073364 a(11) from _Rick L. Shepherd_, Mar 17 2004
%E A073364 a(12)-a(17) from _John W. Layman_, Jul 21 2004
%E A073364 More terms from _T. D. Noe_, Oct 16 2007