# Permutations $\pi\in S_n$ with $p_k+p_{\pi(k)}+1$ prime for all $k=1,\ldots,n$

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

• 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$. – Zhi-Wei Sun Nov 18 '18 at 23:39
• 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! – Zhi-Wei Sun Nov 19 '18 at 1:28
• To record connections: Zhi-Wei made an OEIS entry for this sequence A321727 which already has addition terms through $a_{26}$. – Brian Hopkins Nov 19 '18 at 16:07