As usual, let $S_n$ be the symmetric group of all permutations of $\{1,\ldots,n\}$.

QUESTION: Is my following conjecture true?

Conjecture. For any positive integer $n$, there is a permutation $\pi\in S_n$ such that $p_k+p_{\pi(k)}+1$ is prime for every $k=1,\ldots,n$, where $p_j$ denotes the $j$-th prime.

Let $a_n$ denote the number of permutations $\pi\in S_n$ with $p_k+p_{\pi(k)}+1$ prime for all $k=1,\ldots,n$. Via Mathematica, I find that \begin{gather}a_1=a_2=a_3=1,\ a_4=2,\ a_5=6,\ a_6=10,\ a_7=31,\ a_8=76, \\a_9=696,\ a_{10}=4294,\ a_{11}=5772,\ a_{12}=8472,\ a_{13}=128064,\ a_{14}=147960, \\a_{15}=1684788,\ a_{16}=26114739,\ a_{17}=523452320,\ a_{18}=1029877159, \\a_{19}=1772807946,\ a_{20}=28736761941,\ a_{21}=19795838613, \ a_{22}=31445106424. \end{gather} For example, $(1,2,4,3)$ is a permutation of $\{1,2,3,4\}$ with $$p_1+p_1+1=5,\ p_2 + p_2 + 1 = 7,\ p_3+p_4+1 = 13,\ p_4+p_3+1 = 13$$ all prime, and $(1,4,3,2)$ is a permutation of $\{1,2,3,4\}$ with $$p_1+p_1+1=5,\ p_2+p_4+1 = 11,\ p_3+p_3+1=11,\ p_4+p_2+ 1 = 11$$ all prime.

I note that there is no permutation $\pi\in S_{10}$ with $p_k+p_{\pi(k)}-1$ prime for all $k=1,\ldots,10$.

  • $\begingroup$ Via a computer I note that there is no positive integer $n\le10^7$ with $p_n+p_k-1$ composite for all $k=1,\ldots,n$. $\endgroup$ – Zhi-Wei Sun Nov 18 '18 at 23:39
  • $\begingroup$ I'd like to call an integer sequence $a(1),a(2),\ldots$ (with inifinitely many terms) nice if for each $n=1,2,3,\ldots$ there is a permutation $(b(1),\ldots,b(n))$ of $(a(1),\ldots,a(n))$ such that all the sums $a(1)+b(1),\ldots,a(n)+b(n)$ are terms of the sequence. We can restate the conjecture as follows: The sequence $p_n+1\ (n=1,2,3,\ldots)$ is nice! $\endgroup$ – Zhi-Wei Sun Nov 19 '18 at 1:28
  • $\begingroup$ To record connections: Zhi-Wei made an OEIS entry for this sequence A321727 which already has addition terms through $a_{26}$. $\endgroup$ – Brian Hopkins Nov 19 '18 at 16:07

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.