I am interested in the following problem. An arbitrary integer $n \geq 2$ is given. Find the minimum integer $m \geq 1$ such that there exist integers $0\lt a_1\lt a_2\lt \cdots \lt a_m$ satisfying the following property: for every integer $k \in \{2,\ldots,n\}$ there exist $i,j \in \{1,\ldots,m\}$ such that $k = a_i + a_j$.

To illustrate, let $n=5$. We are forced to take $a_1=1$, so that $2=a_1+a_1$. Then, we are forced to take $a_2=2$, so that $3 = a_1+a_2$. We get $4 = a_2+a_2$ ``for free''. Finally, we need to take $a_3=3$ to get $5=a_2+a_3$ or $a_3=4$ to get $5=a_1+a_3$. In any case, we see that $n=5$ corresponds to $m=3$.

My question: what is $m$ for arbitrary $n$? And if you do not know the answer: can you provide a non-trivial lower bound for $m$? Or do you know a problem which is equivalent or very similar to this one?

  • $\begingroup$ What do you call nontrivial? There are only $(m+1)$-choose-$2$ pairs selected from $m$ numbers, so a lower bound on $m$ is given by ${m+1\choose2}\ge n-1$. $\endgroup$ – Gerry Myerson Jul 21 at 2:53
  • $\begingroup$ Is it oeis.org/A066063 $\endgroup$ – Gerry Myerson Jul 21 at 3:01
  • $\begingroup$ Are you still here, Berry? $\endgroup$ – Gerry Myerson Jul 22 at 13:16

One strategy is to have your set $\{1,2,3,\ldots k,2k,3k,4k\ldots\}$ If you go up to $k^2$ you can get all sums up to $k^2+k$ with $2k$ numbers in the set. It means for numbers up to $n$ you choose $k$ so that $$k^2+k=n\\k=\frac 12(-1+\sqrt{1+4n})\approx \sqrt n\\m \approx 2\sqrt n$$ I don't know if this is optimal, but it is a target for others to shoot at.

Added: For a lower bound, note that there are at most $\frac 12m(m+1)$ sums possible. We then need $$\frac 12m(m+1) \ge n\\ (m+\frac 12)^2 \ge 2n+\frac 14\\ m \ge \sqrt{2n+\frac 14}-\frac 12$$ which shows the above is close. It is a factor $\sqrt 2$ higher because some of the sums match.

  • $\begingroup$ Nice observation, but indeed not what I'm looking for. I suppose your answer bounds $m$ from above, while (if $m$ cannot be found exactly) I'm only interested in (non-trivial) lower bounds for $m$. I updated my question accordingly. $\endgroup$ – Berry van Peer Jul 20 at 15:07

This is one variant of the postage stamp problem. OEIS sequence A001212 gives several values and references.

  • $\begingroup$ That sequence is not the right variant though. $\endgroup$ – orlp Jul 21 at 0:46
  • $\begingroup$ OK, I guess the difference is that you require exactly (instead of at most) two positive summands. $\endgroup$ – Rob Pratt Jul 21 at 0:52

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.