login
Number of permutations f of {1,...,n} such that prime(k)*prime(f(k)) - 2 is prime for every k = 1,...,n.
1

%I #25 Aug 20 2021 02:28:59

%S 1,1,2,3,5,12,2,3,65,248,448,1792,4288,6468,27068,29752,106066,447982,

%T 1250762,6304196,46613084,126391780,504582496,2270372946,3028652541,

%U 8941959118,36442298864,175008626450,318369805106,1974700703920,6654020288821,48819526290634,150577775767875,574885284627624,3058310882340228,15949743649457780

%N Number of permutations f of {1,...,n} such that prime(k)*prime(f(k)) - 2 is prime for every k = 1,...,n.

%C Conjecture: a(n) > 0 for all n > 0. Moreover, for each n > 0, there is an even permutation f of {1,...,n} with prime(k)*prime(f(k)) - 2 prime for all k = 1,...,n. Also, for any integer n > 2, there is an odd permutation f of {1,...,n} with prime(k)*prime(f(k)) - 2 prime for all k = 1,...,n.

%C If we let b(n) denote the number of even permutations f of {1,...,n} with prime(k)*prime(f(k)) - 2 prime for all k = 1,...,n, then (b(1),...,b(11)) = (1,1,1,1,3,6,1,1,33,125,226).

%C In 1973 J.-R. Chen proved that there are infinitely many primes p with p + 2 a product of at most two primes, such primes p are now called Chen primes.

%H Jing Run Chen, <a href="https://doi.org/10.1142/9789814542487_0019">On the representation of a larger even integer as the sum of a prime and the product of at most two primes</a>, Sci. Sinica 16 (1973), pp. 157-176.

%H Zhi-Wei Sun, <a href="https://mathoverflow.net/questions/315679">Chen primes and permutations</a>, Question 315679 on Mathoverflow, Nov. 19, 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.

%e a(7) = 2. The only even permutation of {1,...,7} meeting the requirement is (1,5,7,4,2,6,3) with prime(1)*prime(1) - 2 = 2, prime(2)*prime(5) - 2 = 31, prime(3)*prime(7) - 2 = 83, prime(4)*prime(4) - 2 = 47, prime(5)*prime(2) - 2 = 31, prime(6)*prime(6) - 2 = 167 and prime(7)*prime(3) - 2 = 83 all prime. Also, the only odd permutation of {1,...,7} meeting the requirement is (1,5,7,6,2,4,3) with prime(1)*prime(1) - 2 = 2, prime(2)*prime(5) - 2 = 31, prime(3)*prime(7) - 2 = 83, prime(4)*prime(6) - 2 = 89, prime(5)*prime(2) - 2 = 31, prime(6)*prime(4) - 2 = 89 and prime(7)*prime(3) - 2 = 83 all prime.

%t Permanent[m_List]:=With[{v = Array[x, Length[m]]},Coefficient[Times @@ (m.v), Times @@ v]];

%t a[n_]:=a[n]=Permanent[Table[Boole[PrimeQ[Prime[i]*Prime[j]-2]],{i,1,n},{j,1,n}]];

%t Do[Print[n," ",a[n]],{n,1,27}]

%o (PARI) a(n) = matpermanent(matrix(n, n, i, j, ispseudoprime(prime(i)*prime(j) - 2))); \\ _Jinyuan Wang_, Jun 13 2020

%Y Cf. A000040, A109611, A257926, A321597, A321610, A321611, A321727, A321805.

%K nonn

%O 1,3

%A _Zhi-Wei Sun_, Nov 19 2018

%E a(28)-a(29) from _Jinyuan Wang_, Jun 13 2020

%E a(30)-a(36) from _Vaclav Kotesovec_, Aug 20 2021