Find smallest set of natural numbers whose pairwise sums include 0..n Given a positive integer $n$, how do you find the smallest set of nonnegative integers $S$ such that for each integer $m$, where $0\leq m<n$, there exist two (not necessarily distinct) members of set $S$, say $x$ and $y$ such that $x+y=m$.
For example, consider the case $n=50$. Suppose the length of $S$ is $L$. 
For a lower bound, if the elements of $S$ have pairwise distinct sums, then there are $\dbinom{L+1}{2}$ sums (the plus 1 is because numbers can be added to themselves). Thus, $$\binom{L+1}{2}\geq50\implies L\geq10$$.
I can acheive $L=12$ with the set {0, 1, 2, 3, 7, 10, 15, 18, 22, 23, 24, 25} (done with very inefficient program which searches randomly among all sets). For $L=10$, I feel like it should be impossible; we only have to show that more than 5 numbers can be expressed as a sum in more than 1 way, which should be able to be done through some casework. However, is $L=11$ possible? I think so.
Similarly, for $n=100$, I have $L=17$ from my program: {0, 1, 3, 4, 9, 11, 16, 20, 25, 30, 34, 39, 41, 46, 47, 49, 50}. But the lower bound only gives $L\geq 14$, so at least $L=15$ or $L=16$ should be possible. 
In general, how do you do it efficiently for any given $n$?

Let $n+4=s^2+r$ with $r,s\in\Bbb N$ and $0\leq r\leq 2s$.
Then an upper bound is given by
$$L\leq
\begin{cases}
\lceil{\frac rs}\rceil+2s-3&2\mid s\\
\lceil{\frac{r+1}{s+1}}\rceil+2s-3&2\nmid s
\end{cases}$$
which gives $L\leq 12$ for $n=50$ and $L\leq 18$ for $n=100$.
In general, for large $n$ this gives $L=O(\sqrt n)$.
A set $S$ corresponding to this upper bound is given by
\begin{align}
S
&=\{i\in\Bbb N:0\leq i<q-1\}\\
&\cup\{(q-1)+jq:0\leq j\leq k-1\}\\
&\cup\{i\in\Bbb N:(q-1)+(k-1)q<i\leq 2(q-1)+(k-1)q\}
\end{align}
for suitable values of $q$ and $k$.
Then $|S|=k+2(q-1)$ and then summing each pair of its elements we get all the natural number less or equals to $2(2(q-1)+(k-1)q)=2\max S$.
Consequently, we choose
$$k=\left\lceil\frac{n+4}{2q}\right\rceil-1$$
The function
$$\frac{n+4}{2q}-1+2(q-1)$$
attains a minimum at $q=\frac{\sqrt{n+4}}2$.
If $n+4=s^2+r$ and $s=2t+b$ with $r\leq 2s$ and $0\leq b\leq 1$, then
$$t\leq\frac{\sqrt{n+4}}2<t+1$$
For $q=t$ we get
\begin{align}
|S_t|
&=\left\lceil\frac{n+4}{2t}\right\rceil+2t-3\\
&=\left\lceil\frac{s^2+r}{s-b}\right\rceil+s-b-3\\
&=\left\lceil\frac{r+b}{s-b}\right\rceil+2s-3
\end{align}
while for $q=t+1$
\begin{align}
|S_{t+1}|
&=\left\lceil\frac{n+4}{2t+2}\right\rceil+2t+2-3\\
&=\left\lceil\frac{s^2+r}{s-b+2}\right\rceil+s-b-3\\
&=\left\lceil\frac{r+4-3b}{s+2-b}\right\rceil+2s-3
\end{align}
Since $|S_t|\leq|S_{t+1}|$ if and only if $b(2s+1)\leq 2s-r$, the formula on the top is proved.
