A321610 - OEIS

%I #25 Aug 19 2021 01:58:37

%S 1,1,1,1,1,4,0,16,4,144,64,81,256,5184,1600,25600,8100,183184,108900,

%T 5924356,342225,9066121,11356900,106853569,105698961,16119349444,

%U 1419933124,69792129124,14251584400,613950602500,304388337796,25042678198756,10080904401936,1179245283899881,1045903153861476,31082438574307129

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

%C Conjecture 1: The number a(n) is always a square, and a(n) = 0 only for n = 7.

%C Conjecture 2: For any positive integer n, there is a permutation tau of {1,...,n} such that k^2 + k*tau(k) + tau(k)^2 is prime for every k = 1,...,n.

%C See also A321597 and A321611 for similar conjectures.

%H Zhi-Wei Sun, <a href="https://mathoverflow.net/questions/315341">Primes arising from permutations (II)</a>, Question 315341 on Mathoverflow, Nov. 14, 2018.

%H Zhi-Wei Sun, <a href="https://mathoverflow.net/questions/315351">A mysterious connection between primes and squares</a>, Question 315351 on Mathoverflow, Nov. 15, 2018.

%e a(3) = 1, and (1,3,2) is a permutation of {1,2,3} with 1^2 + 1^2 = 2, 2^2 + 3^2 = 13 and 3^2 + 2^2 all prime.

%e a(5) = 1, and (1,3,2,5,4) is a permutation of {1,2,3,4,5} with 1^2 + 1^2 = 2, 2^2 + 3^2 = 13, 3^2 + 2^2 = 13, 4^2 + 5^2 = 41 and 5^2 + 4^2 = 41 all prime.

%t V[n_]:=V[n]=Permutations[Table[i,{i,1,n}]]

%t Do[r=0;Do[Do[If[PrimeQ[i^2+Part[V[n],k][[i]]^2]==False,Goto[aa]],{i,1,n}];r=r+1;Label[aa],{k,1,n!}];Print[n," ",r],{n,1,11}]

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

%Y Cf. A000040, A000290, A321597, A321611.

%K nonn,more

%O 1,6

%A _Zhi-Wei Sun_, Nov 14 2018

%E a(12)-a(25) from _Jud McCranie_, Nov 15 2018

%E a(26)-a(28) from _Jud McCranie_, Nov 19 2018

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

%E a(31)-a(36) from _Vaclav Kotesovec_, Aug 19 2021