# Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

by W. F. Lunnon
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, Science Fiction Puzzle Tales, Penguin, 1981.
• 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
• MACSYMA Reference Manual, MIT, Cambridge, 1982. A. C. Hearn (editor), REDUCE User’s Manual 3.1, Rand Corporation, Santa Monica, Calif., 1984.
• A. J. Brentjes, Multidimensional continued fraction algorithms, Mathematical Centre Tracts, vol. 145, Mathematisch Centrum, Amsterdam, 1981. MR 638474
• W. F. Lunnon, MDCF Algorithms and their Applications, Proc. Cardiff Conference on the Application of Computers to Mathematics, University College, Cardiff, 1986.
• 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, 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