# Generate $1$, …,$n$ as pairwise differences of a set of numbers

Given $n \in \mathbb N$, I'm interested in sets $S \subset \mathbb Z$ such that the numbers $1$, $2$, ..., $n$ can be obtained as differences between pairs of elements in $S$.

I'd like to find the minimum size of $S$ given $n$. Call that $f(n)$. I'd also like to know if the sets $S$ can be restricted to be of the form $S \subset \{1,2,...n+1\}$ without loss of optimality (where "optimality" means smallest size).

For example, $f(6) = 4$ (found by exhaustive search). One optimal set for $n=6$ is $\{1,2,5,7\}$ (note that $2-1=1$, $7-5=2$, $5-2=3$, $5-1=4$, $7-2=5$ and $7-1=6$). This set is of the form $S \subset \{1,2,...n+1\}$.

So, my questions are:

1. Is there some formula for $f(n)$, or an algorithm to construct an optimal $S$?
2. Can a minimum-size set always be found that is a subset of $\{1,2,...,n+1\}$?

Even if the answers are not known, any pointer in these directions will be helpful.

• This is similar to Golomb rulers but those have all differences distinct instead of accounting for all differences. – Ross Millikan Nov 25 '17 at 1:45
• Instead try minimal sparse rulers. The answer to question 2 is presumably "yes" since you can check $2^{n-1}$ cases and choose the minimal cases – Henry Nov 25 '17 at 1:53
• @Henry Spot-on, thanks! – Luis Mendo Nov 25 '17 at 1:58
• The difference seems to be that sparse rulers impose the condition $S \subset \{1,2,...n+1\}$ by definition. Removing that condition can result in smaller sets that still generate all numbers $1$, ..., $n$, as shown in the linked Wikipedia article – Luis Mendo Nov 25 '17 at 2:15