A321597 Number of permutations tau of {1,...,n} such that k*tau(k) + 1 is prime for every k = 1,...,n.

1, 2, 1, 6, 1, 24, 9, 38, 36, 702, 196, 7386, 3364, 69582, 45369, 885360, 110224, 14335236, 640000, 19867008, 11009124, 1288115340, 188485441, 17909627257, 4553145529, 363106696516, 149376066064, 11141446425852, 990882875761, 371060259505399, 16516486146304, 1479426535706319, 497227517362801, 102319410607145600, 32589727661167504, 12597253470226980096

Offset: 1

Author

Zhi-Wei Sun, Nov 14 2018

Keywords

• nonn
• more

Comments

Conjecture: (i) a(n) > 0 for all n > 0. Similarly, for any integer n > 2, there is a permutation tau of {1,...,n} such that k*tau(k) - 1 is prime for every k = 1,...,n.

(ii) For any integer n > 2, there is a permutation tau of {1,...,n} such that k + tau(k) - 1 and k + tau(k) + 1 are twin prime for every k = 1,...,n.

Obviously, part (ii) of this conjecture implies the twin prime conjecture. P. Bradley proved in arXiv:1809.01012 that for any positive integer n there is a permutation tau of {1,...,n} such that k + tau(k) is prime for every k = 1,...,n.

Examples

			a(3) = 1, and (1,3,2) is a permutation of {1,2,3} with 1*1 + 1 = 2, 2*3 + 1 = 7 and 3*2 + 1 = 7 all prime.
a(5) = 1, and (1,5,4,3,2) is a permutation of {1,2,3,4,5} with 1*1 + 1 = 2, 2*5 + 1 = 11, 3*4 + 1 = 13, 4*3 + 1 = 13 and 5*2 + 1 = 11 all prime.
		

Links

• Paul Bradley, Prime number sums, arXiv:1809.01012 [math.GR], 2018.
• Zhi-Wei Sun, Primes arising from permutations, Question 315259 on Mathoverflow, Nov. 14, 2018.
• Zhi-Wei Sun, On permutations of {1, ..., n} and related topics, arXiv:1811.10503 [math.CO], 2018.

Crossrefs

Cf. A000040, A001359, A006512, A014574.

Programs

Mathematica

V[n_]:=V[n]=Permutations[Table[i,{i,1,n}]]
tab={};Do[r=0;Do[Do[If[PrimeQ[i*Part[V[n],k][[i]]+1]==False,Goto[aa]],{i,1,n}];r=r+1;Label[aa],{k,1,n!}];tab=Append[tab,r],{n,1,11}]

PARI

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

Extensions

a(12)-a(26) from Alois P. Heinz, Nov 17 2018

a(27)-a(30) from Jinyuan Wang, Jun 13 2020

a(31)-a(36) from Vaclav Kotesovec, Aug 19 2021