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

1, 1, 2, 3, 5, 12, 2, 3, 65, 248, 448, 1792, 4288, 6468, 27068, 29752, 106066, 447982, 1250762, 6304196, 46613084, 126391780, 504582496, 2270372946, 3028652541, 8941959118, 36442298864, 175008626450, 318369805106, 1974700703920, 6654020288821, 48819526290634, 150577775767875, 574885284627624, 3058310882340228, 15949743649457780

Offset: 1

Author

Zhi-Wei Sun, Nov 19 2018

Keywords

• nonn

Comments

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.

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).

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.

Examples

			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.
		

Links

• Jing Run Chen, On the representation of a larger even integer as the sum of a prime and the product of at most two primes, Sci. Sinica 16 (1973), pp. 157-176.
• Zhi-Wei Sun, Chen primes and permutations, Question 315679 on Mathoverflow, Nov. 19, 2018.
• Zhi-Wei Sun, On permutations of {1, ..., n} and related topics, arXiv:1811.10503 [math.CO], 2018.

Crossrefs

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

Programs

Mathematica

Permanent[m_List]:=With[{v = Array[x, Length[m]]},Coefficient[Times @@ (m.v), Times @@ v]];
a[n_]:=a[n]=Permanent[Table[Boole[PrimeQ[Prime[i]*Prime[j]-2]],{i,1,n},{j,1,n}]];
Do[Print[n," ",a[n]],{n,1,27}]

PARI

a(n) = matpermanent(matrix(n, n, i, j, ispseudoprime(prime(i)*prime(j) - 2))); \\ Jinyuan Wang, Jun 13 2020

Extensions

a(28)-a(29) from Jinyuan Wang, Jun 13 2020

a(30)-a(36) from Vaclav Kotesovec, Aug 20 2021