Summing Pairs of Numbers to Primes


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.)

Solution     Reveal