%I #34 Aug 18 2021 01:07:50
%S 1,2,3,11,14,33,59,290,843,690,231,978,2896,2966,38252,384917,22351,
%T 68546,28245,147459,84578,17647,17647,232213,17647,792,93640,785178,
%U 5635699,11658279,67706584,351837312,233636388,26967286,35027435,242576452
%N Number of permutations f of {1,...,n} such that 3^k + 3^(f(k)) - 1 is prime for every k = 1,...,n.
%C Clearly, a(n) is the permanent of the matrix of order n whose (i,j)-entry is 1 or 0 according as 3^i + 3^j - 1 is prime or not.
%C Although the first 30 terms are positive, we have a(154) = 0 since it is easy to verify that 3^154 + 3^k - 1 is composite for every k = 1..154.
%C From _Robert Israel_, Dec 08 2019: (Start)
%C In fact 3^154 + 3^k - 1 is composite for k = 1..383, so a(n)=0 for 154 <= n <= 383.
%C Conjecture: for each n >= 154 there is m <= n such that 3^m + 3^k - 1 is composite for k = 1..n. This implies that a(n) = 0 for such n.
%C Conjecture verified for 154 <= n <= 2635. (End)
%C If we let b(n) denote the number of even permutations g of {1,...,n} with 3^k + 3^(g(k)) - 1 prime for all k = 1,...,n, then the values of b(1),b(2),...,b(11) are 1, 1, 1, 6, 8, 17, 30, 144, 422, 353, 111 respectively.
%C In the linked 2017 paper (see Conjecture 3.26), the author conjectured that for any integer a > 1 there are infinitely many primes of the form a^(2k) + a^m - 1 with k and m positive integers.
%H Zhi-Wei Sun, <a href="https://doi.org/10.1007/978-3-319-68032-3_20">Conjectures on representations involving primes</a>, in: M. Nathanson (ed.), Combinatorial and Additive Number Theory II, Springer Proc. in Math. & Stat., Vol. 220, Springer, Cham, 2017, pp. 279-310. (See also <a href="http://arxiv.org/abs/1211.1588">arXiv:1211.1588 [math.NT]</a>, 2012-2017.)
%e a(2) = 2 since both (1,2) and (2,1) are permutations of {1,2}, and 3^1 + 3^1 - 1 = 5, 3^2 + 3^2 - 1 = 17, 3^1 + 3^2 - 1 = 11 and 3^2 + 3^1 - 1 = 11 are all prime.
%p N:= 25: # to get a(1)..a(N)
%p q:= proc(i,j) if isprime(3^i+3^j-1) then 1 else 0 fi end proc:
%p M:= Matrix(N,N, q, shape=symmetric):
%p seq(LinearAlgebra:-Permanent(M[1..n,1..n]), n=1..N); # _Robert Israel_, Dec 08 2019
%t a[n_]:=a[n]=Permanent[Table[Boole[PrimeQ[3^i+3^j-1]],{i,1,n},{j,1,n}]];
%t Do[Print[n," ",a[n]],{n,1,30}]
%o (PARI) a(n) = matpermanent(matrix(n, n, i, j, ispseudoprime(3^i + 3^j - 1))); \\ _Jinyuan Wang_, Jun 13 2020
%Y Cf. A000040, A000244, A321597, A321610, A321611, A321727.
%K nonn
%O 1,2
%A _Zhi-Wei Sun_, Nov 18 2018
%E a(31) from _Jinyuan Wang_, Jun 13 2020
%E a(32)-a(36) from _Vaclav Kotesovec_, Aug 18 2021