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

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 , and (Section 5) by direct search to show that these are minimal for . 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 , the Atkinson-Negro-Santoro sequence **v** (known to give SSD sets) has , Conway-Guy (conjectured to) has , and our best generalization has . We also (Section 8) discuss when such sequences have the same , and (Section 9) how may efficiently be computed to high accuracy.

**[1]**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****[2]**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****[3]**M. Gardner,*Science Fiction Puzzle Tales*, Penguin, 1981.**[4]**Robert Sedgewick,*Algorithms*, Addison-Wesley Series in Computer Science, Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1983. MR**784432****[5]**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**, https://doi.org/10.1007/BF01457454**[6]**Carl-Erik Fröberg,*Numerical mathematics*, The Benjamin/Cummings Publishing Co., Inc., Menlo Park, CA, 1985. Theory and computer applications. MR**790312****[7]***MACSYMA Reference Manual*, MIT, Cambridge, 1982.**[8]**A. C. Hearn (editor),*REDUCE User's Manual 3.1*, Rand Corporation, Santa Monica, Calif., 1984.**[9]**A. J. Brentjes,*Multidimensional continued fraction algorithms*, Mathematical Centre Tracts, vol. 145, Mathematisch Centrum, Amsterdam, 1981. MR**638474****[10]**W. F. Lunnon,*MDCF Algorithms and their Applications*, Proc. Cardiff Conference on the Application of Computers to Mathematics, University College, Cardiff, 1986.**[11]**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**, https://doi.org/10.1145/2455.2461**[12]**M. D. Atkinson, A. Negro & N. Santoro,*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

DOI:
https://doi.org/10.1090/S0025-5718-1988-0917837-5

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

Article copyright:
© Copyright 1988
American Mathematical Society