I stumbled upon the following problem/question that feels like it should have been solved long ago, but that I can't find an answer to.
Let $n \in \mathbb{N}$ be an arbitrary number and let $S_n \subseteq \lbrace 1, \ldots, n\rbrace$ be such that for every $i \in \mathbb{N}$ it either holds $i \in S_n$ or that there are $a, b \in S$ with $a + b = i$. For example, for $n = 9$, the set $S_9 := \lbrace 1, 3, 4, 5\rbrace$ fulfills the requirements because $1 \in S, 2 = 1 + 1, 3 \in S, 4 \in S, 5 \in S, 6 = 3 + 3, 7 = 4 + 3, 8 = 4+4$ and $9 = 4 + 5$.
The question now is the following: Does there exist a sequence of sets $(S_n)_{n \in \mathbb{N}}$ such that for each $n \in \mathbb{N}$ the set $S_n$ fullfills the requirements above and $|S_n| = \mathcal{O}(\sqrt{n})$?
The question for $|S_n| = \mathcal{O}(\sqrt{n})$ stems from the fact that $\mathcal{O}(\sqrt{n})$ is a natural lower bound because a set of size $\mathcal{O}(\sqrt{n})$ allows for $\mathcal{O}(n)$ combinations.
Naturally, the next question would be: Can such a set $S_n$ with $|S_n| = \mathcal{O}(\sqrt{n})$ be constructed efficiently for every $n$?
The question bears some similarity with complete sequences, however, it does not match the definition entirely, because there are the following differences:
- In a complete sequence more than one number may be used to represent each number.
- In a complete sequence no number may be used twice, e.g. $2$ may not be represented as $1 + 1$.
Yes, that's possible. Define
$$S_n=\{1,2,3,\ldots,\lceil\sqrt{n}\rceil,2\times\lceil\sqrt{n}\rceil,3\times\lceil\sqrt{n}\rceil,\ldots,(\lceil\sqrt{n}\rceil-1)\times\lceil\sqrt{n}\rceil\}.$$
Integers from $1$ to $\lceil\sqrt{n}\rceil$ are directly in $S_n$, the ones from $\lceil\sqrt{n}\rceil+1$ to $\lceil\sqrt{n}\rceil + \lceil\sqrt{n}\rceil = 2\lceil\sqrt{n}\rceil$ are the sum of $\lceil\sqrt{n}\rceil$ and one of $1,2,3,\ldots,\lceil\sqrt{n}\rceil$, a.s.o.
The last representable number as the sum of 2 elements of $S_n$ is
$$(\lceil\sqrt{n}\rceil-1)\times\lceil\sqrt{n}\rceil + \lceil\sqrt{n}\rceil = \lceil\sqrt{n}\rceil\times\lceil\sqrt{n}\rceil \ge \sqrt{n}\times \sqrt{n} = n,$$
so we covered all necessary sums. As $|S_n|=2\lceil\sqrt{n}\rceil-2$, this concludes the proof.