Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Integer sets with distinct subset-sums

Author: W. F. Lunnon
Journal: Math. Comp. 50 (1988), 297-320
MSC: Primary 11B13; Secondary 94A60
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.

References [Enhancements On Off] (What's this?)

  • [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.

Similar Articles

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

American Mathematical Society