Given an integer n, I want to find two permutations of the numbers 1 to n (inclusive) such that the sum of numbers from the two permutations at any given index is always prime.
For example:
n = 5
1 2 3 4 5
1 5 4 3 2
n = 8
1 2 3 4 5 6 7 8
2 1 4 3 8 7 6 5
Construct a bipartite graph on {0,1} x {1...n} such that (0, i) and (1, j) are connected if and only if i+j is prime.
Find a perfect matching using any standard technique, and then produce the sequences so that the matching numbers are at the same index.
Find the smallest number k>=1 such that n+k is prime.
Form pairs: (n,k), (n-1, k+1), ..., (k,n).
If k>1, repeat on the range [1,k].
E.g., n=5: 5+2=7, so we have:
5, 4, 3, 2
2, 3, 4, 5
Then we repeat for 1.
E.g. n=8: 8+3 = 11, so we have:
8, 7, 6, 5, 4, 3
3, 4, 5, 6, 7, 8
Leaving us with 2:
1, 2
2, 1
By Bertrand's postulate aka Chebyshev's theorem, for any n>1 there is a prime p s.t. n < p < 2n, and for n=1 we have 1+1=2, so we will always be able to do this.