3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ $r(2n)$ might be a square too. $\endgroup$ – Zhi-Wei Sun Nov 15 '18 at 0:48
  • 1
    $\begingroup$ The argument from my answer to mathoverflow.net/questions/315351 confirms (iii) as well, so nothing that mysterious happens... $\endgroup$ – Ilya Bogdanov Nov 15 '18 at 9:02
  • 1
    $\begingroup$ ...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. $\endgroup$ – Ilya Bogdanov Nov 15 '18 at 9:26
  • $\begingroup$ 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. $\endgroup$ – Wojowu Nov 15 '18 at 9:57
  • $\begingroup$ 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. $\endgroup$ – Jud McCranie Nov 16 '18 at 4:38

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.