Find smallest set of natural numbers whose pairwise sums include 0..n

Question

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$?

Answer 1

Here are results for $n$ up to $80$, where $\min$ is the lower bound you derive from the binomial coefficient, $\max$ is the upper bound that Fabio Lucchini derived in his answer, and $L=|S|$ is the size of a minimal generating set. Actual subsets $S$ are only shown for the last entry for any given $L$, since this subset also works for all smaller $n$.

\begin{array}{c|c|c|c|l} n&\min&\max&L&S\\\hline 2&2&2&2&\{0,1\}\\ 3&3&3&3\\ 4&3&3&3&\{0,1,2\}\\ 5&3&4&4\\ 6&4&4&4\\ 7&4&4&4\\ 8&4&4&4&\{0,1,3,4\}\\ 9&4&5&5\\ 10&5&5&5\\ 11&5&5&5\\ 12&5&5&5&\{0,1,3,5,6\}\\ 13&5&6&6\\ 14&5&6&6\\ 15&6&6&6\\ 16&6&6&6&\{0,1,3,5,7,8\}\\ 17&6&7&7\\ 18&6&7&7\\ 19&6&7&7\\ 20&6&7&7&\{0,1,2,5,8,9,10\}\\ 21&7&8&8\\ 22&7&8&8\\ 23&7&8&8\\ 24&7&8&8\\ 25&7&8&8\\ 26&7&8&8&\{0,1,2,5,8,11,12,13\}\\ 27&7&9&9\\ 28&8&9&9\\ 29&8&9&9\\ 30&8&9&9\\ 31&8&9&9\\ 32&8&9&9&\{0,1,2,5,8,11,14,15,16\}\\ 33&8&10&10\\ 34&8&10&10\\ 35&8&10&10\\ 36&9&10&10\\ 37&9&10&10\\ 38&9&10&10\\ 39&9&11&10\\ 40&9&11&10&\{0,1,3,4,9,11,16,17,19,20\}\\ 41&9&11&11\\ 42&9&11&11\\ 43&9&11&11\\ 44&9&11&11\\ 45&10&12&11\\ 46&10&12&11&\{0,1,2,3,7,11,15,19,21,22,24\}\\ 47&10&12&12\\ 48&10&12&12\\ 49&10&12&12\\ 50&10&12&12\\ 51&10&12&12\\ 52&10&12&12\\ 53&10&13&12\\ 54&10&13&12&\{0,1,2,3,7,11,15,19,23,25,26,28\}\\ 55&11&13&13\\ 56&11&13&13\\ 57&11&13&13\\ 58&11&13&13\\ 59&11&13&13\\ 60&11&13&13\\ 61&11&14&13\\ 62&11&14&13\\ 63&11&14&13\\ 64&11&14&13&\{0,1,3,4,9,11,16,21,23,28,29,31,32\}\\ 65&11&14&14&\\ 66&12&14&14&\\ 67&12&14&14&\\ 68&12&14&14&\\ 69&12&15&14&\\ 70&12&15&14&\\ 71&12&15&14&\\ 72&12&15&14&\{0,1,3,4,9,11,16,20,25,27,32,33,35,36\}\\ 73&12&15&15&\\ 74&12&15&15&\\ 75&12&15&15&\\ 76&12&15&15&\\ 77&12&16&15&\\ 78&13&16&15&\\ 79&13&16&15&\\ 80&13&16&15&\{0,1,3,4,5,8,14,20,26,32,35,36,37,39,40\}\\ \end{array}

Here's the code I used to generate these results. It loops over $n$, making use of the solution for $n-1$ in each step. It first checks whether the set for $n-1$ also works for $n$. If not, it tries finding a new set also containig $L$ numbers, at first using only elements up to $\lfloor\frac n2\rfloor + 2$. Only if that doesn't work does it try all combinations with $L$ elements all the way up to $n$. If that also doesn't work, it increases $L$. This way, it spends almost all its time only on the values of $n$ where $L$ needs to be incremented; for all other values of $n$ it quickly finds a solution without having to search the entire space.

The least $n$ for which Fabio Lucchini's upper bound is not tight is $n=39$, for which the $10$-element set $\{0,1,3,4,9,11,16,17,19,20\}$ is sufficient whereas the upper bound is $11$.

The sequence $L(n)$ is OEIS A066063, and the only information in that entry is the lower bound you already found. Usually, OEIS is quite good at collecting information about sequences, so it's likely that nothing else was known.

Answer 2

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.

Answer 3

Here is the casework to show that for $n=50$, $L$ indeed has to be greater than $10$, assuming joriki's suggestion:

all minimal solutions contain $0$,$1$,$\lceil\frac n2\rceil-1$ and $\lceil\frac n2\rceil$

Since ${11 \choose 2} =55$, we just need to show that we can get at least $6$ 'matches' for any set of numbers.

OK, so by joriki's suggestion, we need $0,1,24,25$. So immediately we have one match: $24+1=25+0$

Now for the cases:

I) If we add $2$, we have two more: $1+1=2+0$ and $24+2=25+1$

To make 47, we need to either add $23$ or $22$:

I.A) Add $23$. Then we can add $23+1=24+0$, $24+2=25+1$, and $23+25=24+24$, so we have our $6$ matches

I.B) Add $22$. We can add $22+2=24+0$ (4 matches now)

To make $5$, we need to add $3$, $4$, or $5$:

I.B.i) Add $3$: $2+1=3+0$ and $24+3=25+2$ Got our $6$

I.B.ii) Add $4$: $2+2=4+0$ and $22+4=24+2$. Also $6$

I.B.iii) Add $5$: $22+5=25+2$. OK, need one more ... well, to create $45$ we need to add either $20$ (which gives $20+2=22+0$) or $21$ ($21+1=22+0$), so done here as well

OK, so adding $2$ definitely leads to $6$ matches. So, let's not add $2$ ... but now we need $3$ to create $3$:

II) Add $3$

Again, to create $47$, we have to add either $23$ or $22$:

II.A) Add $23$. We can add $24+24=23+25$, $23+1=24+0$, and $23+3=25+1$, so 4 matches now.

To create $5$, we need to add either $4$ or $5$:

II.A.i) Add $4$. Then we have $3+1=4+0$ and $23+4=25+3$. Done

II.A.ii) Add $5$. We have $5+1=3+3$ and $23+5=25+3$ Done

II.B) Add $22$. We can add $22+3=25+0$ and $22+3=24+1$ (3 matches now)

To make $5$, we need tpo add $4$ or $5$:

II.B.i) Add $4$. This gives $1+3=4+0$, $24+4=25+3$, and $22+4=25+1$ Done

II.B.ii) Add $5$. This gives $1+5=3+3$, $22+5=24+3$, so need just one more. But to create $45$ we need to add $21$ ($21+1=22+0$), or $20$ ($20+3=22+1$), so done here as well

.. and that concludes all cases. So, yes, as you suspected, for $n=25$ we have $L>10$

And frankly, seeing how quickly these possible matches increase, my guess is that for $n=50$, $L=12$