From: israel@math.ubc.ca (Robert Israel) Subject: Re: Combinatorics Problem Date: 10 Feb 1999 01:07:39 GMT Newsgroups: sci.math Keywords: maximal sets of integers with all subset sums distinct In article <36BE6D36.4662@owlnet.rice.edu>, Brian David Rothbach writes: |> QSCGZ wrote: |> > |> > { biggest subset S of {1,2,..,n} such that all subsets of S |> > have different sums } |> > |> > Brian Rothbach wrote: |> > >age(1)=1 |> > >age(2)=2 |> > 4: 3,5,6,7 |> > 5: 6,9,11,12,13 (or 3,6,11,12,13) |> > 6: 11,17,20,22,23,24 |> > 7: 20,31,37,40,42,43,44 |> We ran a computer and got the lowest for 8 to be 84 with I looked up your sequence in Neil Sloane's On-Line Encyclopedia of Integer Sequences and found: %I A005318 M1075 %S A005318 1,2,4,7,13,24,44,84,161,309,594,1164,2284,4484,8807,17305,34301, %T A005318 68008,134852,267420,530356,1051905,2095003,4172701,8311101,16554194 %N A005318 Conway-Guy sequence: a(n+1)=2a(n)-a(n-[1/2 + sqrt(2n)]). %R A005318 ADM 12 143 1982. JRM 15 149 1983. CRP 296 345 1983. MSH 84 59 1983. %O A005318 1,2 %A A005318 njas %D A005318 Conway & Guy, Solution of a problem of Erdos, Colloq. Math. 20 (1969), p. 307 (a preliminary announcement). The ADM reference is the main paper. %K A005318 nonn,easy None of the references were easily available to me at the moment, so I tried a search on MathSciNet. After unsuccessfully looking for papers by Conway and Guy, I got the idea of searching for "Conway-Guy" in Review Text, and found the references below. [reformatted -- djr] [1] 98k:11014 Bohman, Tom A construction for sets of integers with distinct subset sums. Electron. J. Combin. 5 (1998), no. 1, Research Paper 3, 14 pp. (electronic). (Reviewer: Yuri Bilu) 11B75 (05D10) [2] 97b:11027 Bohman, Tom A sum packing problem of Erdös and the Conway-Guy sequence. Proc. Amer. Math. Soc. 124 (1996), no. 12, 3627--3636. (Reviewer: Bruce Landman) 11B75 [3] 89c:05067 Foster, Ronald M. The Foster census. R. M. Foster's census of connected symmetric trivalent graphs. With a foreword by H. S. M. Coxeter. With a biographical preface by Seymour Schuster. With an introduction by I. Z. Bouwer, W. W. Chernoff, B. Monson and Z. Star. Edited and with a note by Bouwer. Charles Babbage Research Centre, Winnipeg, MB, 1988. viii+240 pp. ISBN: 0-919611-19-2 (Reviewer: Norman Biggs) 05C99 [4] 89a:11019 Lunnon, W. F. Integer sets with distinct subset-sums. Math. Comp. 50 (1988), no. 181, 297--320. (Reviewer: Béla Uhrin) 11B13 (94A60) [5] 86m:11009 Guy, Richard K. Sets of integers whose subsets have distinct sums. Theory and practice of combinatorics, 141--154, North-Holland Math. Stud., 60, North-Holland, Amsterdam-New York, 1982. (Reviewer: H. G. Meijer) 11A99 (11B75) [6] 81a:10067 Uberman, V. I.; \v Sle\u \i nikov, V. I. {\cyr Issledovanie plotnosti additivnykh detektiruyushchikh chislovykh sistem s pomoshch\cprime yu ČTsVM}. (Russian) [Research on the density of additive detecting number systems by means of a computer] Preprint 10-78. Akad. Nauk Ukrain. SSR, Fiz.-Tekhn. Inst. Nizkikh Temperatur, Kharkov, 1978. 60 pp. (Reviewer: Richard K. Guy) 10L10 Robert Israel israel@math.ubc.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada V6T 1Z2 ============================================================================== From: Dave Rusin Subject: I Sloaned it Date: Mon, 1 Mar 1999 17:17:02 -0600 (CST) Newsgroups: [missing] To: richard@math.niu.edu Keywords: Conway-Guy sequence Well, Sloane's tables give a hit which suggests a recursive formula for g(n). Hit space bar if you want to see it. SPOILER %I A005318 M1075 %S A005318 1,2,4,7,13,24,44,84,161,309,594,1164,2284,4484,8807,17305,34301, %T A005318 68008,134852,267420,530356,1051905,2095003,4172701,8311101,16554194 %N A005318 Conway-Guy sequence: a(n+1)=2a(n)-a(n-[1/2 + sqrt(2n)]). %R A005318 ADM 12 143 1982. JRM 15 149 1983. CRP 296 345 1983. MSH 84 59 1983. %O A005318 1,2 %A A005318 njas %D A005318 Conway & Guy, Solution of a problem of Erdos, Colloq. Math. 20 (1969), p. 307 (a preliminary announcement). The ADM reference is the main paper. %K A005318 nonn,easy Getting more information than that required more than the customary amount of sleuthing. First, Sloane expands the references to these: Colloq. Math.=Colloquium Mathematicum (Warsaw) ADM=Annals Discrete Math JRM=Journal of Recreational Mathematics CRP=Comptes Rendus, Paris MSH=Mathematiques et Sciences Humaine But interestingly, MathSciNet has no references to any of these except CRP: 84e:05006 Kreweras, Germain; Alvarez Rodriguez, Miguel-Angel Pondération entičre minimale de ${N}$ telle que pour tout $k$ toutes les $k$-parties de ${N}$ aient des poids distincts. (French) [Minimal integer weighting of ${\bf N}$ such that for any $k$ all the $k$-subsets of ${\bf N}$ have unequal weights] C. R. Acad. Sci. Paris Sér. I Math. 296 (1983), no. 8, 345--347. 05A05 Authors' summary: "A mapping s: N{arrr}N is exhibited such that for any integer k ( >= 0) all the sums of values on the k-subsets of N are unequal. It is proved that s can be defined by s{sub}0=0, s{sub}1=1 and s {sub}(n+1)=2s{sub}n - s{sub}(n - p(n)), where (p{sub}1p{sub}2 ... p{sub}n ... ) is the sequence (1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 6 6 ... ), and that the sequence s is minimal in the sense that s{sub}(n+1) is the smallest possible value for given s{sub}0, ... ,s{sub}n." I did find one other reference in Zentrallblatt, to the ADM source: (Note a pagination discrepancy). 511.10038 Guy, Richard K. Sets of integers whose subsets have distinct sums. (English) [J] Ann. Discrete Math. 12, 141-154 (1982). Keywords: sums of integers; subsets with distinct sums; Conway-Guy sequence Classification: *11B83 Special sequences of integers and polynomials 05A99 Classical combinatorial problems I had to look that up by hand; according to the review, it's the same problem. That review also refers to the Notices AMS 15, 1968 p345 by Conway and Guy. Just for laughs: there's a paper by one J. Wolfskill reviewed a few pages earlier in the same Zbl.