# Minimum number of elements in $\{0, 1, 2, \dots, n\}$ that add up to all of the elements of $\{0, 1, 2, \dots, n\}$.

I was reflecting on the Goldbach conjecture when the following question came to my mind:

Let $$n$$ be a natural number. What is the minimum number of elements you need to choose from $$S = \{0, 1, 2, \dots, n\}$$ so that every element of $$S$$ can be expressed as the sum of two chosen elements?

I made some attempts to solve it, and was able to find an upper bound:

For $$k\in S$$, choose the elements \begin{aligned}0, 1, \dots, k, 2k, 3k, \dots, \Big\lfloor \frac{n}{k}\Big\rfloor k\end{aligned}. Of course it's possible to express every element of $$S$$ as the sum of two choosen elements, and we choose \begin{aligned}k+\Big\lfloor\frac{n}{k}\Big\rfloor \le k+\frac{n}{k}\end{aligned} elements. Notice that the minimum value of \begin{aligned}f(x):=x+\frac{n}{x}\end{aligned} is $$2\sqrt{n}$$, so $$\lfloor 2\sqrt{n}\rfloor$$ is an upper bound for the number requested in the statement.

I know this bound is not the answer. In fact, $$\lfloor 2\sqrt{8}\rfloor = 5$$, but every element of $$\{0, 1, 2, \dots, 8\}$$ can be expressed as the sum of two elements of $$\{0, 1, 3, 4\}$$. I would appreciate some help in this subject.

• As far as I know, it's an open problem, but I could be wrong. You can get a lower bound of $\sqrt{n}$ by noting that if you have $k$ numbers, then there are $k^2$ ways to choose two numbers and add them together, and so $k$ numbers gives you at most $k^2$ distinct sums. Thus the correct number lies somewhere between $\sqrt{n}$ and $2\sqrt{n}$. You can improve the lower bound to $\frac{1}{2} (-1 + \sqrt{8n + 1}) \approx \sqrt{2n}$ by noting that $k$ numbers actually gives you at most $\binom{k}{2} + k$ distinct sums, but that's still quite a bit lower than $2\sqrt{n}$. – Dylan Aug 13 '20 at 22:34
• Some optimal (not necessary unique) sets for lowest $n$ here (python script, exhaustive search). – Alexey Burdin Aug 13 '20 at 22:51
• It's sequence A066063 on the OEIS: oeis.org/A066063 – Dylan Aug 13 '20 at 22:52
• I extended the OEIS sequence to $n=50$ just now. – RobPratt Aug 13 '20 at 23:15

You can solve the problem via integer linear programming as follows. For $$j\in S$$, let binary decision variable $$x_j$$ indicate whether element $$j$$ is selected. Let $$P=\{j_1\in S, j_2 \in S: j_1 \le j_2\}$$ be the set of pairs of elements of $$S$$. For $$(j_1,j_2)\in P$$, let binary decision variable $$y_{j_1,j_2}$$ indicate whether both $$j_1$$ and $$j_2$$ are selected. The problem is to minimize $$\sum_{j\in S} x_j$$ subject to: \begin{align} \sum_{(j_1,j_2)\in P:\\j_1+j_2=i} y_{j_1,j_2} &\ge 1 &&\text{for i\in S} \tag1\\ y_{j_1,j_2} &\le x_{j_1} &&\text{for (j_1,j_2)\in P} \tag2\\ y_{j_1,j_2} &\le x_{j_2} &&\text{for (j_1,j_2)\in P} \tag3 \end{align} The objective minimizes the number of selected elements. Constraint $$(1)$$ forces each element of $$S$$ to be expressible as a sum of selected elements. Constraints $$(2)$$ and $$(3)$$ enforce $$y_{j_1,j_2} = 1 \implies x_{j_1} = 1$$ and $$y_{j_1,j_2} = 1 \implies x_{j_2} = 1$$, respectively.

Maybe you should use a different approach.

It can be found that sets with the least number of elements are of the following type:

$$\{0,1,a_1,\dots ,a_m,\frac{n}{2}-a_m,\dots ,\frac{n}{2}-a_1,\frac{n}{2}-1,\frac{n}{2}\}$$

or

$$\{0,1,a_1,\dots ,a_m,\frac{n}{4},\frac{n}{2}-a_m,\dots ,\frac{n}{2}-a_1,\frac{n}{2}-1,\frac{n}{2}\}$$

example $$n \leq 20$$

elements can be found easily with this set

$$\{0,1,3,\dots ,\frac{n}{2}-1,\frac{n}{2}\}$$ number of elements $$2+\frac{n}{4}$$

then

$$\{0,1\}$$ for $$0 \leq n \leq 2$$

$$\{0,1,2\}$$ for $$3 \leq n \leq 4$$

$$\{0,1,3,4\}$$ for $$5 \leq n \leq 8$$

$$\{0,1,3,5,6\}$$ for $$9 \leq n \leq 12$$

$$\{0,1,3,5,7,8\}$$ for $$13 \leq n \leq 16$$

$$\{0,1,3,5,7,9,10\}$$ for $$17 \leq n \leq 20$$

example $$n >20$$

$$\{0,1,3,4,9,10,12,13\}$$ for $$21 \leq n \leq 26$$

$$\{0,1,3,4,5,8,14,20,26,32,35,36,37,39,40\}$$ for $$73 \leq n \leq 80$$