3
\$\begingroup\$

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}
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ {2,3,5} is optimal set for 10, but contains both odd and even numbers \$\endgroup\$ – Egor Skriptunoff Sep 1 '13 at 7:56
  • \$\begingroup\$ @EgorSkriptunoff, true, but there are also two all-odd and two all-even sets for the same score. {even, odd, odd} can produce 4 numbers, so can't get beyond 10, whereas {2,4,8} and {2,4,6} are solutions for 12. If you look at four-element sets then a 2-2 split in parity limits to 6 pairs (so up to 14); a 3-1 split limits to 7 pairs (up to 16); a 4-0 split limits to 10 pairs, and {2,4,8,10} achieves 9 (up to 20). The further you go, the more disadvantage there is to mixing parities. \$\endgroup\$ – Peter Taylor Sep 1 '13 at 12:09
3
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ upto(1/0.0)? It's trivial to prove that upto(x) is pessimistic. \$\endgroup\$ – Peter Taylor Aug 26 '13 at 10:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.