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,2

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.

Links

Table of n, a(n) for n=1..36.

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.

Example

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.

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}]

Prog

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

Crossrefs

Cf. A000040, A001359, A006512, A014574.

Sequence in context: A307374 A173279 A277440 * A083720 A369925 A055878

Adjacent sequences: A321594 A321595 A321596 * A321598 A321599 A321600

Keyword

nonn,more

Author

Zhi-Wei Sun, Nov 14 2018

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

Status

approved