# Constructing a small set of numbers whose differences cover $\{1,\ldots,n\}$

Let $$n\in\mathbb N$$.

Given a set $$S\subset\mathbb N$$, let $$\Delta(S) = \{a-b\mid a,b\in S\}$$ denote its set of differences.

I'm interested in finding a small set $$S_n$$ such that $$\{1,\ldots,n\}\subseteq\Delta(S_n)$$.

For example, if $$n=8$$ we can use

$$S_8 =\{1,2,4,8,9\}.$$

How can we construct a small $$S_n$$ efficiently? (Efficiently should ideally be $$O(|S_n|)$$ time, but any $$o(n)$$ time would be interesting.)

How does the smallest $$|S_n|$$ grow as a function of $$n$$? (As a guess, I'd like to say $$|S_n|=O(\sqrt n)$$ should be possible?)

One example of such a set is $$S_n = \{0,1,2,\dots,k\} \cup \{k,2k,3k,\dots,k^2\}$$ where $$k=\lceil \sqrt{n} \rceil$$. It follows that $$|S_n|=O(\sqrt{n})$$, and $$S_n$$ can be constructed in $$O(\sqrt{n})$$ time.

• This seems to give an easy 2-approx for $|S_n|$. Any thoughts on whether this can be improved?
– M A
Sep 6 at 7:48
• @MA, If you want to know how small $|S_n|$ can be, that sounds like a good question for Math.SE. I'm not sure that it is a matter of computer science.
– D.W.
Sep 6 at 8:15
• Isn't finding an optimal solution (or a $c$-approx. for $c<2$) a matter of computer science? I asked here because I am interested in something I can program, I'm not sure that Math.SE. is the right place for that.
– M A
Sep 6 at 10:08
• @MA, yes, you are right. If it were me, I would ask first on Math.SE, as many constructions are easily implementable and difference sets are well studied in mathematics, but it is up to you. In any case, this is a new question and should be asked separately.
– D.W.
Sep 7 at 6:27