Create sets with a Goldbach-like property

Question

Goldbach's conjecture states that every even number > 4 is the sum of two prime numbers. Although this conjecture is not yet proven, similar results have been proven for other series of numbers. For example, every even number can be written as the sum of two practical numbers.

The Challenge

Given a number N, return a set of positive integers such that every even number in the interval [4,N] can be written as the sum of two numbers in the set. Furthermore, the set generated must contain as few elements as possible, otherwise this challenge would be trivial.

Shortest answer wins.

Detailed Example

For N=24, one possible output is {2,4,8,10,12}. This is because it contains the fewest number of elements possible (5). Also, every even number {4,6,8,... 24} can be written as the sum of exactly two of the members of the set.

4=2+2
6=2+4
...
12=8+4
14=10+4
...
24=12+12

Examples

Here are some examples. There may be many valid outputs for each input, but only a few are listed.

4:{2}
6:{2,4} or {1,3}
9:{2,4}  #pay attention to how the odd number is handled
10:{2,4,6} or {2,3,5}
12:{2,4,6}
24:{2,4,8,10,12}
26:{1,3,7,11,13}

Answer 1

GolfScript (53 chars)

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

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

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

---

NB Let f(2n) be the size of the optimal set for [4..2n]. Then f(2n) <= f(2n+2) <= 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.

Answer 2

J block, 106 characters

f=.3 :0
n=.0
while.1
do.for_z.>,{n#<>:i.y
do.if.0=$(+:2+i.<:<.-:y)-.+/~z
do.z
return.end.end.n=.>:n
end.
)

As usual for J programs, very memory hungry. The algorithm is as simple as can be: for each length n, for each combination z of n values, if that combination covers the whole set, return that combination.

Ruby, 116 112 characters

f=->x{0.upto(x){|n|(1..x).to_a.combination(n){|z|return z if
[]==4.step(x,2).to_a-z.flat_map{|i|z.map{|j|i+j}}}}}

(whitespace insignificant)

Ruby version of the algorithm, built-in deduplication, much more memory-efficient due to the use of enumerators in place of arrays (though J seems to optimise this somewhat), surprisingly not much larger than the J version.

results:

 4-5 :[2]
 6-9 :[2, 4]
10-13:[2, 4, 6]
14-21:[2, 4, 8, 10]
22-29:[2, 4, 8, 12, 14]
30-39:[2, 4, 8, 12, 16, 18]
40-45:[2, 4, 6, 12, 18, 20, 22]