Motivated by two previous questions of mine (cf. Primes arising from permutations and Primes arising from permutations (II)), here I ask a curious question which connects primes with squares.
QUESTION: Is my following conjecture true?
Conjecture. Let $n$ be any positive integer, and let $S(n)$ denote the number of permutations $\tau$ of $\{1,\ldots,n\}$ with $k^4+\tau(k)^4$ prime for all $k=1,\ldots,n$. Then $S(n)$ is always a positive square.
Via a computer, I find that $$(S(1),\ldots,S(11))=(1,1,1,4,4,4,4,64,16,144,144).$$ For example, $(1,3,2)$ is a permutation of $\{1,2,3\}$ with $$1^4+1^4=2,\ \ 2^4+3^4=97,\ \ \text{and}\ 3^4+2^4=97$$ all prime.