OFFSET
1,6
COMMENTS
Conjecture 1: The number a(n) is always a square, and a(n) = 0 only for n = 7.
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.
Each such permutation corresponds to a pair of perfect matchings in the bipartite graph with edges connecting odd i (excluding i=1 in the odd n case) to even j whenever i^2 + j^2 is prime. Hence, a(n) equals the square of permanent of the reduced adjacency matrix of this graph. See my PARI code for the formula. - Max Alekseyev, Oct 17 2025
LINKS
Max Alekseyev, Table of n, a(n) for n = 1..64
Zhi-Wei Sun, Primes arising from permutations (II), Question 315341 on Mathoverflow, Nov. 14, 2018.
Zhi-Wei Sun, A mysterious connection between primes and squares, Question 315351 on Mathoverflow, Nov. 15, 2018.
EXAMPLE
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.
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.
MATHEMATICA
V[n_]:=V[n]=Permutations[Table[i, {i, 1, n}]]
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}]
PROG
(PARI) a(n) = matpermanent(matrix(n, n, i, j, ispseudoprime(i^2 + j^2))); \\ Jinyuan Wang, Jun 13 2020
(PARI) a321610(n) = matpermanent( matrix(n\2, n\2, i, j, isprime( (2*(i+n%2)-1)^2 + (2*j)^2) ) )^2; \\ Max Alekseyev, Oct 17 2025
CROSSREFS
KEYWORD
nonn
AUTHOR
Zhi-Wei Sun, Nov 14 2018
EXTENSIONS
a(12)-a(25) from Jud McCranie, Nov 15 2018
a(26)-a(28) from Jud McCranie, Nov 19 2018
a(29)-a(30) from Jinyuan Wang, Jun 13 2020
a(31)-a(36) from Vaclav Kotesovec, Aug 19 2021
STATUS
approved