Finding the largest set of integers over an interval where the sum of any 'k' elements is unique

Question

Consider the set $(s_1, ..., s_N) \in S$, where all $s_i$ are positive integers selected from some interval $[M, L]$ and the sum of any $k$ integers in $S$ is required to be unique and to have a distance of at least $d$ from all other possible sums of $k$ integers in the set. For example, if $k = 2$, the sum of any two randomly chosen elements, i.e. $s_a$ and $s_b$, must generate a unique sum that has a difference of at least $d$ from all other possible sums of two elements in $S$.

As a function of $k$, the minimum difference between sums $d$, and the size of the interval, $(L - M)$, what is the largest possible size of the set $S$, and what is the most efficient way to compute its elements?

Edit - I'm of course happy to hear any $d = 1$ solutions.

Edit 2 - For the $d=1$ case, is this problem NP-complete, similar to the subset-sum problem?

Answer 1

Here's a start. The number of choices of $k$ elements is $N\choose k$ (or a little more, if repeats are allowed), and each sum is between $kM$ and $kL$, so you must have $${N\choose k}\lt kL-kM+2$$ which gives you an upper bound on $N$. It doesn't tell you whether you can achieve that bound, nor an efficient way to try.

EDIT: Ah, you've changed the problem, so my answer is now relevant only to your case $d=1$. But if you divide the right side of the displayed inequality by $d$, it should apply to your more general question.

Answer 2

This is an algorithm that I am convinced is optimal, although I have not tried to prove it. First of all, we may assume that $L=0$ (consider ${s_1-L,\dots,s_N-L}$). For the algorithm I will describe, we may also asume that $d=1$.

The key is to observe that if $\{s_1,\dots,s_N\}$ is such that all sums of subsets of $k$ elements are different, so must be the sums of subsets of $m$ elements for $1\le m\le k$. This implies that $\{s_1,\dots,s_k\}$ must be the first $k$ terms of the sequence A005255. Let $n>k$ and suppose that $\{s_1,\dots,s_n\}$ is such that the sums of the subsets of $m$ elements are all different for $1\le m\le k$. Then we choose $s_{n+1}$ in such a way that for each $m$, $1\le m\le k$, the smallest possible sum of $m$ elements, one of them beeing $s_{n+1}$, is equal to the largest possible sum of $m$ terms in $\{s_1,\dots,s_n\}$ plus $1$. If the $s_j$'s are ordered in increasing order, this means $$ s_{n+1}=\max_{1\le m\le k}\Bigl(\,\sum_{j=n-m+1}^ns_j-\sum_{j=1}^{m-1}s_j\Bigr)+1. $$ It is easy to show that for all $n>k$ $$ \sum_{j=n-k}^{n-1}s_j-\sum_{j=1}^{k-1}s_j\le s_n\le2\,s_{n-1}. $$ In particular $s_n$ is almost like $2^n$.

For $d>1$, the algorithm will give $d$ times the solution with $d=1$.

The algorithm is implemented in the following Mathematica ce; you have to provide the values of $k$ and $M$.

k = 5;
M = 1000000;
s[1] = 0;
s[2] = 1;
s[n_Integer] := 
  s[n] = Max[
    Table[Sum[s[j], {j, n - m, n - 1}] - Sum[s[j], {j, m - 1}] + 
      1, {m, n - 1}]];
sol = Table[s[j], {j, k}];
If[Last[sol] <= S,
  While[next = 
    Max[Table[
      Total[Take[sol, -m]] - Total[Take[sol, m - 1]] + 1, {m, k}]]; 
   next <= S, AppendTo[sol, next]]; Print[sol], 
  Print["M is too small; try again with a larger M"]]
{0,1,2,4,7,13,24,46,88,172,337,661,1298,2550,5012,9852,19367,38073,74848,147146,289280,568708}