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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.