Integer sets with distinct subset-sums

Author:
W. F. Lunnon

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

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

- 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*, Unsolved Problems in Intuitive Mathematics, vol. 1, Springer-Verlag, New York-Berlin, 1981. Problem Books in Mathematics. 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 https://doi.org/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 https://doi.org/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.

Retrieve articles in *Mathematics of Computation*
with MSC:
11B13,
94A60

Retrieve articles in all journals with MSC: 11B13, 94A60

Additional Information

Keywords:
SSD,
Conway-Guy,
Knapsack problem,
backtrack search,
divide-and-conquer,
Richardson extrapolation,
MACSYMA,
MDCF

Article copyright:
© Copyright 1988
American Mathematical Society