

A321597


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


7



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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.
ZhiWei Sun, Primes arising from permutations, Question 315259 on Mathoverflow, Nov. 14, 2018.
ZhiWei 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 A055878 A331654
Adjacent sequences: A321594 A321595 A321596 * A321598 A321599 A321600


KEYWORD

nonn,more


AUTHOR

ZhiWei 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



