Integer sets with distinct subsetsums
Author:
W. F. Lunnon
Journal:
Math. Comp. 50 (1988), 297320
MSC:
Primary 11B13; Secondary 94A60
MathSciNet review:
917837
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: In Section 1 we introduce the problem of finding minimalheight sets of n natural numbers with distinct subsetsums (SSD), and in Section 2 review the wellknown ConwayGuy 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 AtkinsonNegroSantoro sequence v (known to give SSD sets) has , ConwayGuy (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, NorthHolland Math. Stud.,
vol. 60, NorthHolland, Amsterdam, 1982, pp. 141–154. MR 806978
(86m:11009)
 [2]
Richard
K. Guy, Unsolved problems in number theory, Unsolved Problems
in Intuitive Mathematics, vol. 1, SpringerVerlag, New YorkBerlin,
1981. Problem Books in Mathematics. MR 656313
(83k:10002)
 [3]
M. Gardner, Science Fiction Puzzle Tales, Penguin, 1981.
 [4]
Robert
Sedgewick, Algorithms, AddisonWesley Series in Computer
Science, AddisonWesley Publishing Company, Advanced Book Program, Reading,
MA, 1983. MR
784432 (86k:68037)
 [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 (84a:12002), http://dx.doi.org/10.1007/BF01457454
 [6]
CarlErik
Fröberg, Numerical mathematics, The Benjamin/Cummings
Publishing Co., Inc., Menlo Park, CA, 1985. Theory and computer
applications. 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, Multidimensional continued fraction algorithms,
Mathematical Centre Tracts, vol. 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 and A.
M. Odlyzko, Solving lowdensity subset sum problems, J. Assoc.
Comput. Mach. 32 (1985), no. 1, 229–246. MR 832341
(87i:11186), http://dx.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.
 [1]
 R. K. GUY, "Sets of integers whose subsets have distinct sums," Ann. Discrete Math., v. 12, 1982, pp. 141154. MR 806978 (86m:11009)
 [2]
 R. K. Guy, Unsolved Problems in Number Theory, SpringerVerlag, Berlin and New York, 1981. MR 656313 (83k:10002)
 [3]
 M. Gardner, Science Fiction Puzzle Tales, Penguin, 1981.
 [4]
 R. Sedgewick, Algorithms, AddisonWesley, 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. 515534. 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, MultiDimensional 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 lowdensity subset problems," J. Assoc. Comput. Mach., v. 32, 1985, pp. 229246. 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
DOI:
http://dx.doi.org/10.1090/S00255718198809178375
PII:
S 00255718(1988)09178375
Keywords:
SSD,
ConwayGuy,
Knapsack problem,
backtrack search,
divideandconquer,
Richardson extrapolation,
MACSYMA,
MDCF
Article copyright:
© Copyright 1988
American Mathematical Society
