I got this problem from Rustan Leino, who got it from Jay Misra, who got it from Gerard Huet.

I solved it and wrote up my solution.

Devise an algorithm that, given an even number $N$, partitions the integers from $1$ to $N$ into pairs such that the sum of the two numbers in each pair is a prime number.

You will probably find it useful to know that for any $k > 1$, there exists a prime number $p$ such that $k < p < 2k$. (This is Bertrand's Postulate, which Chebyshev proved.)

The algorithm is defined recursively on $N$, as follows. If $N = 0$, use the empty partition. Otherwise, since Bertrand's Postulate holds, you can find a prime number $p$ such that $N < p < 2N$. Let $q = p - N$, and observe that $0 < q < N.$ Since $p$ is prime and exceeds 2, $p$ is odd and thus $q$ is odd and $q-1$ is even. Call the algorithm recursively to partition the integers $1$ to $q-1$. To this partition, add the pairs $(q, N),$ $(q+1, N-1),$ $(q+2, N-2),$ $\ldots,$ $([q+N-1]/2, [q+N+1]/2).$ Each of these added pairs has sum $q+N$, which equals the prime number $p$. So, the updated partition retains the property that the sum of each pair is prime. The resulting partition also contains each integer between $1$ and $N$ exactly once. So, this is the desired partition.