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 , 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]**R. K. GUY, "Sets of integers whose subsets have distinct sums,"*Ann. Discrete Math.*, v. 12, 1982, pp. 141-154. MR**806978 (86m:11009)****[2]**R. K. Guy,*Unsolved Problems in Number Theory*, Springer-Verlag, Berlin and New York, 1981. MR**656313 (83k:10002)****[3]**M. Gardner,*Science Fiction Puzzle Tales*, Penguin, 1981.**[4]**R. Sedgewick,*Algorithms*, Addison-Wesley, Reading, Mass., 1983. MR**784432 (86k:68037)****[5]**A. K. Lenstra, H. W. Lenstra & L. LovÁsz, "Factoring polynomials with rational coefficients,"*Math. Ann.*, v. 261, 1982, pp. 515-534. MR**682664 (84a:12002)****[6]**C.-E. Fröberg,*Numerical Mathematics*, Benjamin Cummings, Menlo Park, Calif., 1985. MR**790312 (86h:65001)****[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,*Multi-Dimensional Continued Fraction Algorithms*, Math. Centre Tracts 145, Mathematisch Centrum, Amsterdam, 1981. MR**638474 (83b:10038)****[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 & A. M. Odlyzko, "Solving low-density subset problems,"*J. Assoc. Comput. Mach.*, v. 32, 1985, pp. 229-246. MR**832341 (87i:11186)****[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