9
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ I just realized that both my answer and Fabio Lucchini's (perhaps following my mistake) shifted your $n$ by one; we assumed that $n$ itself also needs to be generated. This is also how $n$ is defined in OEIS A066063. Usually I'd correct the mistake in my answer, but since the OEIS sequence and two long answers now all use the same convention, might I perhaps ask you to change the question slightly to match it? Your examples would still be valid, since in both cases you can also form $n$ itself; all you'd have to change is $m\le n$ and $\binom{L+1}2\gt50$. $\endgroup$ – joriki Jul 1 '18 at 8:10
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Indeed it looks like when $n$ is a multiple of 4, the set has symmetry around $n/4$. This is true even for my possibly suboptimal set for $n=100$. 0 and 1 must be included since if 0 weren't there, there would be no way to make 0, and if the next smallest number after 0 wasn't 1, (say it was 0, 2 or 0, 3) there would be no way to make 1. Then $n/2$ and $n/2-1$ would follow from symmetry if that were proven. Also, there may be a generalization of the symmetry to non multiples of 4. $\endgroup$ – soktinpk Jun 29 '18 at 12:44
  • $\begingroup$ @soktinpk: I've updated the answer with results up to $n=64$. $\endgroup$ – joriki Jul 1 '18 at 12:43
  • $\begingroup$ @soktinpk: I've updated the answer with results up to $n=80$. $\endgroup$ – joriki Jul 4 '18 at 13:11
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ You are right, I made a typo; the answer is now edited. $\endgroup$ – Fabio Lucchini Jun 29 '18 at 9:27
  • 1
    $\begingroup$ I see. I think the expression $\lceil{\frac{r-1}{s+1}}\rceil+2s-3$ in the odd case is slightly off. For $n=32$, both my results and your analysis further down show that $9$ elements are required ($q=3$, $k=5$), but that expression yields an upper bound of $8$. $\endgroup$ – joriki Jun 29 '18 at 9:55
  • 1
    $\begingroup$ Yes, edited another typo. Thank'you. Now for $n=32$ we get $s=6$ and $r=0$ which gives $L\leq 9$. $\endgroup$ – Fabio Lucchini Jun 29 '18 at 10:01
  • 1
    $\begingroup$ Unfortunately, this bound is not minimal: for $n=100$ it gives $|S|=18$, while in the OP soktinpk find a solution with $|S|=17$. $\endgroup$ – Fabio Lucchini Jun 29 '18 at 13:00
  • 1
    $\begingroup$ Ah, yes, I didn't check that case. I'll try to find the first $n$ at which it's not minimal. Anyway, it's a very good bound, we should perhaps enter it at OEIS. $\endgroup$ – joriki Jun 29 '18 at 13:01
1
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.