|
%I #30 Aug 19 2021 02:03:57
%S 1,1,1,2,6,10,31,76,696,4294,5772,8472,128064,147960,1684788,26114739,
%T 523452320,1029877159,1772807946,28736761941,19795838613,31445106424,
%U 1313504660737,54477761675626,105122845176663,2200119900732333,2761739099984389,83123428119278837,219734505495953342,7228968492870136475,13623311188546432233,625620139149376861330,18603738861035365389401,64952397216275572992159,3115094155636931821691880,4788927142804364353625983
%N Number of permutations f of {1,...,n} such that prime(k) + prime(f(k)) + 1 is prime for every k = 1,...,n.
%C Clearly, a(n) is also the permanent of the matrix of order n whose (i,j)-entry is 1 or 0 according as prime(i) + prime(j) + 1 is prime or not.
%C Conjecture: a(n) > 0 for all n > 0.
%C Note that there is no permutation f of {1,...,10} such that prime(k) + prime(f(k)) - 1 is prime for every k = 1,...,10.
%H Zhi-Wei Sun, <a href="https://mathoverflow.net/questions/315581">Permutations pi with p_k+p_{pi(k)}+1 prime for all k = 1,...,n</a>, Question 315581 on Mathoverflow, Nov. 17, 2018.
%e a(3) = 1, and (1,2,3) is a permutation of {1,2,3} with prime(1) + prime(1) + 1 = 5, prime(2) + prime(2) + 1 = 7 and prime(3) + prime(3) + 1 = 11 all prime.
%e a(4) = 2. In fact, (1,2,4,3) is a permutation of {1,2,3,4} with prime(1) + prime(1) + 1 = 5, prime(2) + prime(2) + 1 = 7, prime(3) + prime(4) + 1 = 13 and prime(4) + prime(3) + 1 = 13 all prime; also (1,4,3,2) is a permutation of {1,2,3,4} with prime(1) + prime(1) + 1 = 5, prime(2) + prime(4) + 1 = 11, prime(3) + prime(3) + 1 = 11 and prime(4) + prime(2) + 1 = 11 all prime.
%p b:= proc(s) option remember; (k-> `if`(k=0, 1, add(`if`(isprime(
%p ithprime(i)+ithprime(k)+1), b(s minus {i}), 0), i=s)))(nops(s))
%p end:
%p a:= n-> b({$1..n}):
%p seq(a(n), n=1..15); # _Alois P. Heinz_, Nov 17 2018
%t p[n_]:=p[n]=Prime[n];
%t a[n_]:=a[n]=Permanent[Table[Boole[PrimeQ[p[i]+p[j]+1]],{i,1,n},{j,1,n}]];
%t Do[Print[n," ",a[n]],{n,1,22}]
%o (PARI) a(n) = matpermanent(matrix(n, n, i, j, ispseudoprime(prime(i)+prime(j)+1))); \\ _Jinyuan Wang_, Jun 13 2020
%Y Cf. A000040, A321597, A321610, A321611.
%K nonn
%O 1,4
%A _Zhi-Wei Sun_, Nov 17 2018
%E a(23)-a(26) from _Alois P. Heinz_, Nov 17 2018
%E a(27)-a(28) from _Jinyuan Wang_, Jun 13 2020
%E a(29)-a(36) from _Vaclav Kotesovec_, Aug 19 2021
|
