A321766 Number of permutations f of {1,...,n} such that 3^k + 3^(f(k)) - 1 is prime for every k = 1,...,n.

1, 2, 3, 11, 14, 33, 59, 290, 843, 690, 231, 978, 2896, 2966, 38252, 384917, 22351, 68546, 28245, 147459, 84578, 17647, 17647, 232213, 17647, 792, 93640, 785178, 5635699, 11658279, 67706584, 351837312, 233636388, 26967286, 35027435, 242576452

Offset: 1

Author

Zhi-Wei Sun, Nov 18 2018

Keywords

• nonn

Comments

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.

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.

From Robert Israel, Dec 08 2019: (Start)

In fact 3^154 + 3^k - 1 is composite for k = 1..383, so a(n)=0 for 154 <= n <= 383.

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.

Conjecture verified for 154 <= n <= 2635. (End)

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.

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.

Examples

			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.
		

Links

• Zhi-Wei Sun, Conjectures on representations involving primes, 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 arXiv:1211.1588 [math.NT], 2012-2017.)

Crossrefs

Cf. A000040, A000244, A321597, A321610, A321611, A321727.

Programs

Maple

N:= 25: # to get a(1)..a(N)
q:= proc(i,j)  if isprime(3^i+3^j-1) then 1 else 0 fi end proc:
M:= Matrix(N,N, q, shape=symmetric):
seq(LinearAlgebra:-Permanent(M[1..n,1..n]), n=1..N); # Robert Israel, Dec 08 2019

Mathematica

a[n_]:=a[n]=Permanent[Table[Boole[PrimeQ[3^i+3^j-1]],{i,1,n},{j,1,n}]];
Do[Print[n," ",a[n]],{n,1,30}]

PARI

a(n) = matpermanent(matrix(n, n, i, j, ispseudoprime(3^i + 3^j - 1))); \\ Jinyuan Wang, Jun 13 2020

Extensions

a(31) from Jinyuan Wang, Jun 13 2020

a(32)-a(36) from Vaclav Kotesovec, Aug 18 2021