In Question 315259 (cf. Primes arising from permutations) I asked a question on primes arising from permutations which looks quite challenging.

Here I pose a new question in this direction which does not involve upper bounds for the least prime in an arithmetic progression with common difference $n$.

QUESTION: Is my following conjecture true?

**Conjecture**. (i) For each $n=1,2,3,\ldots$, there is a permutation $\pi_n$ of $\{1,\ldots,n\}$ such that $k^2+k\pi_n(k)+\pi_n(k)^2$ is prime for every $k=1,\ldots,n$.

(ii) For any positive integer $n\not=7$, there is a permutation $\pi_n$ of $\{1,\ldots,n\}$ such that $k^2+\pi_n(k)^2$ is prime for every $k=1,\ldots,n$.

(iii) For each $n=1,2,3,\ldots$, the number of permutations $\pi_n$ of $\{1,\ldots,n\}$ with $k^2+\pi_n(k)^2$ prime for all $k=1,\ldots,n$, is always a square.

I have checked this conjecture for $n$ up to $11$. For example, $(6,3,2,5,4,1)$ is the unique permutation of $\{1,\ldots,6\}$ meeting the requirement in part (i) with $n=6$, and $(1,3,2,5,4)$ is the unique permutation of $\{1,\ldots,5\}$ meeting the requirement in part (ii) with $n=5$. Part (iii) of the conjecture looks quite mysterious!

Let $r(n)$ be the number of permutations $\pi_n$ of $\{1,\ldots,n\}$ meeting the requirement in part (i), and let $s(n)$ be the number of permutations $\pi_n$ of $\{1,\ldots,n\}$ meeting the requirement in part (ii). Then $$(r(1),\ldots,r(11))=(1,1,3,1,5,1,17,9,21,16,196)$$ and $$(s(1),\ldots,s(11))=(1,1,1,1,1,4,0,16,4,144,64).$$

thatmysterious happens... $\endgroup$ – Ilya Bogdanov Nov 15 '18 at 9:02