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

Question

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 chose $\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\}$.

As mentioned in a comment, you can get a lower bound of $\lceil \sqrt{n}\rceil$.

The following graph was made using the values in A066063. It doesn't have many points, but still inclines me to believe that the real answer grows asymptotically as $2\sqrt n$.

Answer 1

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.

Answer 2

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$