I am currently trying to solve the following problem:
Given a number $n \in \mathbb{N}$, find the size of a set $S$ of positive numbers $s_1, \ldots, s_k\in \mathbb{N}$, such that
$\sum_{i=1}^kS_i = n$
$\forall l$: $1 \leq l \leq n : l$ is the sum of a subset of $S$.
$S$ is minimal (but may contain the same number more than once)
What is the minimal size for $S$?
I thought that adding 1, 2, 3, $\ldots$, $k$ to the set until the sum is equal to the desired $n$ was the (simple) solution, but apparently this is not always the minimal solution to the problem. Is there a generic way of solving this problem or this type of problem?
Thanks to @snulty for pointing me in the right direction here.
The problem can be solved by converting $n$ into powers of two. Take the highest power $2^k \leq n$.
Adding the next higher power $2^{k+1}$ (or, if $n = 2^k$, $2^k$ itself) would of course mean that $\sum_{i=1}^{k+1} S_i > n$, but instead imagine adding just the difference between $n$ and $\sum_{i=1}^{k} S_i$, since elements may be added more than once.
$S$ must therefore contain $k+1$ elements, since $2^0 = 1$ is the first element added to the set.