Create sets with a Goldbach-like property
GolfScript (53 chars)

~2/),3&gt;[2][1 3]]({2*:x;{:S{x&lt;},{x\-S+.&amp;}/}%}/{,}$0=n*


A major speed optimisation results from a bit of duplicate-trimming, at a cost of 3 chars:

~2/),3&gt;[2][1 3]]({2*:x;{:S{x&lt;},{x\-S+.&amp;$}/}%.&amp;}/{,}$0=n*




NB Let f(2n) be the size of the optimal set for [4..2n]. Then f(2n) &lt;= f(2n+2) &lt;= f(2n) + 1. The first inequality is obvious from the definition; the second is easily seen by taking any optimal set S_{2n} for [4..2n] and taking the union with {n+1}, or indeed with {2n+2-x} for any x in S_{2n}.

This suggests a greedy algorithm, which the first revision of this answer implements. However, that greedy algorithm turns out to be incorrect. The unique optimal set for [4..20] is {2,4,8,10}, which is not a subset of either of the two optimal sets for [4..26]: {1,3,7,11,13} and {2,4,8,12,14}.

My current solution assumes that every optimal set will contain only odd numbers or only even numbers. I haven't proven this, but given that odd + even = odd a set which mixes parities is wasting possible pairs.