I'm wondering if it's possible to write a theorem to prove or disprove the possibility of arranging a sequence of numbers (1,2,…n) such that the sum of any two numbers adds up to a prime number.
An Example:
Input: Say n=7. The sequence is 1,2,3,4,5,6,7
Output: 7,6,5,2,1,4,3
Here are a few numbers where a program I wrote seems to fail for
n=71
solution sequence:
36 37 52 61 18 19 54 55 58 45 56 11 26 27 44 53 60 67 6 7 10 13 30 31 48 49 64 3 4 15 16 21 22 25 28 33 34 39 40 43 46 51 62 65 66 71 2 5 8 9 14 17 20 23 24 29 32 35 38 41 42 47 50 63 68 69 70 1 12 59
But unable to fit: 57
n=50
solution sequence:
19 12 49 30 31 48 11 50 3 4 15 38 41 42 47 6 7 10 13 18 23 24 29 32 35 44 45 2 5 8 9 14 17 20 21 22 25 28 33 34 39 40 43 46 1 36
But unable to fit: 37 27 26 16
Successful attempts:
n=17
3 4 7 10 13 6 11 12 17 2 5 8 9 14 15 16
n=25
23 24 19 12 11 18 25 6 7 10 13 16 3 4 15 2 5 8 9 14 17 20 21 22 1
Here is the program (very dirty I warn you!) I wrote to be able to generate the above output. Hint: Change max to the number you want and try it out.
Best Answer
Not an answer but a comment on the problem:
I think the enumeration of such rearranged sequences is a graph theory question. Consider the undirected graph $G_n$ whose nodes are the numbers from $1$ to $n$. Draw an edge between $a$ and $b$ if $a+b$ is prime. Then by Bertrand's postulate you get a connected graph.
Arrangements of the numbers such that the sum of any two consecutive numbers is prime correspond to Hamiltonian paths of $G_n$. An example for $n=8$:
Note that the graph is bipartite. This gives you methods to find prime arrangements in $O(1.5^n)$ rather than $O(n!)$ as required for the brute force approach.
However I doubt that it really helps to prove for which numbers such an arrangement exists.