The problem can be describe in the following way:

Given a positive integer $N$, we need to find a methods to generate a set of integers A, so that for any integer $1 \leq k \leq N$, we can find two integers $x, y \in A$, such that $x - y = k$.

An example for problem is the following: $N=9$, we can generate a set $A:=\{-3, -2, -1, 0, 3, 6\}$. Clearly, the size of $A=6$.

We naively prove that the minimal size of $|A| = \sqrt(2N)$. However, we can't find a method to generate an $A$ that can reach this theoretical minimal. The best methods we find can only reach $|A| = 2 \sqrt(N)$.

Is there any methods that can reach the theoretical minimal $\sqrt(2N)$? If not, what is the minimal size that any methods can reach?

Given a positive integer $N$, what is the size of the smallest set of integers $A$ such that, for any integer $1 \leq k \leq N$, we can find two integers $x, y \in A$ such that $x - y = k$? (An alternative way to write this condition is to ask that $\{1, \ldots, N\} \subseteq A-A$.) For example, for $N=9$, we could take $A=\{-3, -2, -1, 0, 3, 6\}$, which achieves $|A|=6$.

It easy to see that $|A| \geq \sqrt{2N}$, as at most $\binom {|A|} 2 \leq |A|^2/2$ differences can be formed from the elements of $A$. I can also construct suitable sets $A$ with $|A| = 2 \sqrt N$.

Is the lower bound $\sqrt{2N}$ asymptotically correct? If not, what is the correct lower bound?

The problem can be describe in the following way.

Given a positive integer N, we need to find a methods to generate a set of integers A, so that for any integer 1 <= k <= N, we can find two integers x, y \in A, such that x - y = k.

A example for this is: N=9, we can generate a set A={-3, -2, -1, 0, 3, 6}. This size of A is 6.

We naively prove that the minimal size of |A| = \sqrt(2N). However, we can't find a methods to generate set A that can reach this theoretical minimal. The best methods we find can only reach |A| = 2 \sqrt(N).

Is there any methods that can reach the theoretical minimal \sqrt(2N)? If not, what is the minimal size that any methods can reach?

The problem can be describe in the following way:

Given a positive integer $N$, we need to find a methods to generate a set of integers A, so that for any integer $1 \leq k \leq N$, we can find two integers $x, y \in A$, such that $x - y = k$.

An example for problem is the following: $N=9$, we can generate a set $A:=\{-3, -2, -1, 0, 3, 6\}$. Clearly, the size of $A=6$.

We naively prove that the minimal size of $|A| = \sqrt(2N)$. However, we can't find a method to generate an $A$ that can reach this theoretical minimal. The best methods we find can only reach $|A| = 2 \sqrt(N)$.

Is there any methods that can reach the theoretical minimal $\sqrt(2N)$? If not, what is the minimal size that any methods can reach?