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

niceif 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