4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ $\{4\}$ will do it or $\{4;~8\}$ $\endgroup$ – Paracosmiste Aug 25 '13 at 21:08
  • $\begingroup$ Won't {2, n-2} in fact do it for all sets? $\endgroup$ – Don Larynx Aug 25 '13 at 21:53
  • $\begingroup$ @Jossie I'm not sure what you mean. Can you elaborate? $\endgroup$ – PhiNotPi Aug 25 '13 at 21:57
  • $\begingroup$ 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. $\endgroup$ – Don Larynx Aug 25 '13 at 22:02
2
$\begingroup$

I'm going to reduce this to a more natural problem, and then give a solution of that one. My solution isn't provably the best, but it's within a constant factor.

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Peter Taylor Aug 26 '13 at 7:39

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.