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.