## Integer sets with distinct subset-sums

HTML articles powered by AMS MathViewer

- by W. F. Lunnon PDF
- Math. Comp.
**50**(1988), 297-320 Request permission

## 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$, and (Section 5) by direct search to show that these are minimal for $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 $\alpha = {\lim _{n \to \infty }}{w_n}/{2^{n - 1}}$, the Atkinson-Negro-Santoro sequence

**v**(known to give SSD sets) has $\alpha = 0.6334$, Conway-Guy (conjectured to) has $\alpha = 0.4703$, and our best generalization has $\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.

## References

- Richard K. Guy,
*Sets of integers whose subsets have distinct sums*, Theory and practice of combinatorics, North-Holland Math. Stud., vol. 60, North-Holland, Amsterdam, 1982, pp. 141–154. MR**806978** - Richard K. Guy,
*Unsolved problems in number theory*, Problem Books in Mathematics, Springer-Verlag, New York-Berlin, 1981. MR**656313**
M. Gardner, - Robert Sedgewick,
*Algorithms*, Addison-Wesley Series in Computer Science, Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1983. MR**784432** - A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász,
*Factoring polynomials with rational coefficients*, Math. Ann.**261**(1982), no. 4, 515–534. MR**682664**, DOI 10.1007/BF01457454 - Carl-Erik Fröberg,
*Numerical mathematics*, The Benjamin/Cummings Publishing Co., Inc., Menlo Park, CA, 1985. Theory and computer applications. MR**790312** - A. J. Brentjes,
*Multidimensional continued fraction algorithms*, Mathematical Centre Tracts, vol. 145, Mathematisch Centrum, Amsterdam, 1981. MR**638474**
W. F. Lunnon, - J. C. Lagarias and A. M. Odlyzko,
*Solving low-density subset sum problems*, J. Assoc. Comput. Mach.**32**(1985), no. 1, 229–246. MR**832341**, DOI 10.1145/2455.2461
M. D. Atkinson, A. Negro & N. Santoro,

*Science Fiction Puzzle Tales*, Penguin, 1981.

*MACSYMA Reference Manual*, MIT, Cambridge, 1982. A. C. Hearn (editor),

*REDUCE User’s Manual 3.1*, Rand Corporation, Santa Monica, Calif., 1984.

*MDCF Algorithms and their Applications*, Proc. Cardiff Conference on the Application of Computers to Mathematics, University College, Cardiff, 1986.

*Integer Sets with Lexicographically Ordered Subset Sums*, Technical Report no. 100, Carlton Univ., 1986.

## Additional Information

- © Copyright 1988 American Mathematical Society
- Journal: Math. Comp.
**50**(1988), 297-320 - MSC: Primary 11B13; Secondary 94A60
- DOI: https://doi.org/10.1090/S0025-5718-1988-0917837-5
- MathSciNet review: 917837