# How can I find the smallest set such that all even integers $4≤x≤N$ can be written as the sum of two elements in the set?

Given a positive integer N, I want to create a set of positive integers such that any even number $4,6,8,...N$ can be written as the sum of two elements in the set. I also want the set to be as small as possible.

For example, with $N=24$, the set {${2,4,8,10,14}$} is one possible result. The set has $5$ elements, and no set with fewer elements has the desired property.

4=2+2
6=2+4
8=4+4
10=2+8
12=2+10=4+8
14=4+10
16=2+14=8+8
18=4+14=8+10
20=10+10
22=8+14
24=10+14


This example was found by hand. Is there a faster, more "mathematical" way?

This question is related to a challenge I created at codegolf.SE. I decided that the underlying mathematics was pretty interesting and that I wanted to learn more about it.

• $\{4\}$ will do it or $\{4;~8\}$ – Paracosmiste Aug 25 '13 at 21:08
• Won't {2, n-2} in fact do it for all sets? – Don Larynx Aug 25 '13 at 21:53
• @Jossie I'm not sure what you mean. Can you elaborate? – PhiNotPi Aug 25 '13 at 21:57
• You said "the sum of two elements in the set. I also want the set to be as small as possible." So use the set {$2, N-2$} to satisfy this property. – Don Larynx Aug 25 '13 at 22:02

It seems to me that the restriction to sets of even numbers doesn't add anything to the problem. So lets consider the following more natural problem: find a set $S$ of numbers, of minimum size, such that every number in the set $\{1,...,n\}$ is the sum of two elements of $S$. This problem is equivalent to the original problem with $n=N/2$. Just double every element of $S$ to get a solution of the original problem.
Let $s$ be the number of elements in $S$. The number of pairs of elements in $S$ is $s \choose{2}$, and this must be greater than or equal to $n$. So $s>O(\sqrt{n})$. And the next paragraph gives an example showing that this bound can be attained, so we know $s=O(\sqrt{n})$.
For convenience, assume $n$ is a perfect square. If it isn't, rounding up to the next perfect square will give a solution that's only too big by $O(1)$. The solution is the set of integers $\{0,...,\sqrt{n}-1\} \cup \{0, \sqrt{n}, 2 \sqrt{n}, ... , n-\sqrt{n}\}$. Any number can be given by the sum of a number in the first set and a number on the second set. As promised, $s=2\sqrt{n}=O(\sqrt{n})$. I wouldn't be surprised if this could be improved by a small constant factor.
• The conventional way of writing the lower bound would be $s = \Omega(\sqrt n)$, and of writing the tight bound would be $s = \Theta(\sqrt n)$. Also you're making a non properly justified assumption in your reduction, which is that the original problem has no input values for which all optimal sets include an odd number. – Peter Taylor Aug 26 '13 at 7:39