4

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.

Community
  • 1
PhiNotPi
  • 2,661
  • 3
  • 23
  • 36

1 Answers1

2

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.

Carl Feynman
  • 101
  • 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 07:39