The following is a generalization of this old question .
Let $n\ge 2$, $[n]=\{1,\ldots,n\}$. For which distinct $a,b\in[n]$ is it possible to list $[n]$ in some order $x_1,\ldots,x_n$ such that $x_1=a$, $x_n=b$ and $x_i+x_{i+1}$ is prime for $1\le i\le n-1$?
Note that there is no wrap-around: $x_1+x_n$ does not need to be prime.
In the language of graph theory: Define a graph with vertex set $[n]$ and edge $vw$ whenever $v+w$ is prime. For which distinct $a,b$ is there a hamiltonian path from $a$ to $b$?
There are some easy necessary conditions:
- If $n$ is odd, $a$ and $b$ are both odd.
- If $n$ is even, $a$ and $b$ have opposite parity.
- Neither of these cases holds: $n=5,\{a,b\}=\{1,3\}$ and $n=6,\{a,b\}=\{1,2\}$.
Conjecture. These necessary conditions are also sufficient.
Solutions for $n=7$:
1 4 7 6 5 2 3
1 2 3 4 7 6 5
1 4 3 2 5 6 7
3 2 1 4 7 6 5
3 4 1 2 5 6 7
5 2 3 4 1 6 7
I verified the conjecture up to $n=750$ with a very stupid program. A clever program could go much further. I also checked the case $\{a,b\}=\{1,n\}$ up to $n=33000$ and the case $\{a,b\}=\{1,2\}$ up to $n=20000$.
