# Minimum number of integers $a_1,…,a_m$ needed to express $2,…,n$ as $a_i + a_j$

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?

• 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$. – Gerry Myerson Jul 21 at 2:53
• Is it oeis.org/A066063 – Gerry Myerson Jul 21 at 3:01
• Are you still here, Berry? – 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.
• 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. – Berry van Peer Jul 20 at 15:07