Integer sets with distinct subset-sums

Source abstract

In Section 1 we introduce the problem of finding minimal-height sets of n natural numbers with distinct subset-sums (SSD), and in Section 2 review the well-known Conway-Guy sequence u , conjectured to yield a minimal SSD set for every n . We go on (Section 3) to prove that u certainly cannot be improved upon by any "greedy" sequence, to verify numerically (Section 4) that it does yield SSD sets for n > 80 n > 80 , and (Section 5) by direct search to show that these are minimal for n ⩽ 8 n \leqslant 8 . There is a brief interlude (Section 6) on the problem of decoding the subset from its sum. In Section 7 generalizations of u are constructed which are asymptotically smaller: Defining the Limit Ratio of a sequence w to be α = lim n → ∞ w n / 2 n − 1 \alpha = {\lim _{n \to \infty }}{w_n}/{2^{n - 1}} , the Atkinson-Negro-Santoro sequence v (known to give SSD sets) has α = 0.6334 \alpha = 0.6334 , Conway-Guy (conjectured to) has α = 0.4703 \alpha = 0.4703 , and our best generalization has α = 0.4419 \alpha = 0.4419 . We also (Section 8) discuss when such sequences have the same α \alpha , and (Section 9) how α \alpha may efficiently be computed to high accuracy.