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.
 A: 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.
A: 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$
