# Primes arising from permutations (II)

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).$$

• $r(2n)$ might be a square too. – Zhi-Wei Sun Nov 15 '18 at 0:48
• The argument from my answer to mathoverflow.net/questions/315351 confirms (iii) as well, so nothing that mysterious happens... – Ilya Bogdanov Nov 15 '18 at 9:02
• ...and the same happens for $r(2n)$, since all even numbers should map to all odd ones. This is what breaks in the odd case here: there may be diffetent pairs of odd numbers providng a prime. – Ilya Bogdanov Nov 15 '18 at 9:26
• Affirmative answer to (i) or (ii) would imply that for every $k$, a degree $2$ polynomial $x^2+k^2$ or $x^2+xk+k^2$ takes a prime value. I am willing to bet this is an open problem. – Wojowu Nov 15 '18 at 9:57
• You confirmed conjectures (ii) and (iii) through n=11. Here are the number of partitions for conjecture (iii) for n=12 through 25": 81, 256, 5184, 1600, 25600, 8100, 183184, 108900, 5924356, 342225, 9066121, 11356900, 106853569, 105698961 - they are all squares. – Jud McCranie Nov 16 '18 at 4:38