For which $n$ is there a permutation such that the sum of any two adjacent elements is a prime? For which $n$ is it possible to find a permutation of the numbers from $1$ to $n$ such that the sum of any two adjacent elements of the permutation is a prime?
For example: For $n=4$ the permutation $(1,2,3,4)$ has sums $1+2=3$, $2+3=5$, $3+4=7$,and $4+1=5$.
For $n=16$ the permutation $(1,2,3,4,7,6,5,14,15,16,13,10,9,8,11,12)$ has sums of adjacent elements $(3,5,7,11,13,11,19,29,31,29,23,19,17,19,23,13)$.

Here are constructions with few sums.
The permutation $(12, 1, 10, 3, 8, 5, 6, 7, 4, 9, 2, 11)$ has adjacent sums equal to $11$, $13$, or $23$. 
The permutation $(12, 1, 10, 3, 8, 5, 6, 7, 4, 9, 2, 11, 18, 13, 16, 15, 14, 17)$ has adjacent sums equal to $11$, $13$,$29$, or $31$. 
If you have two pairs of twin primes $p$, $p+2$, $q$, $q+2$ with $q \gt 2p$ then the permutation of $q-p$
$$(p+1, 1, p-1, 3, ... p-2, 2, p, \\ q-p, p+2, q-p-2, p+4, ... p+5, q-p-3, p+3,  q-p-1 )$$
has sums in $\{p,p+2,q,q+2\}$.
Heuristically, all but finitely many even numbers $n$ [Edit: that are divisible by $6$, as Aaron Meyerowitz and Mario Carneiro pointed out] should be expressible as a difference between a twin prime $p$ and a twin prime $q$ so that $q \gt 2p$.
