The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 56th year, we are closing in on 350,000 sequences, and we’ve crossed 9,700 citations (which often say “discovered thanks to the OEIS”).

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A007865 Number of sum-free subsets of {1, ..., n}. 47
 1, 2, 3, 6, 9, 16, 24, 42, 61, 108, 151, 253, 369, 607, 847, 1400, 1954, 3139, 4398, 6976, 9583, 15456, 20982, 32816, 45417, 70109, 94499, 148234, 200768, 308213, 415543, 634270, 849877, 1311244, 1739022, 2630061, 3540355, 5344961, 7051789, 10747207, 14158720, 21295570, 28188520 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,2 COMMENTS More precisely, subsets of {1,...,n} containing no solutions of x+y=z. There are two proofs that a(n) is 2^{n/2}(1+o(1)), as Paul Erdős and I conjectured. In sumset notation, number of subsets A of {1,...,n} such that the intersection of A and 2A is empty. Using the Mathematica program, all such subsets can be printed. - T. D. Noe, Apr 20 2004 The Sapozhenko paper has many additional references. If this sequence counts sum-free sets, then A326083 counts sum-closed sets, which is different from sum-full sets (A093971). - Gus Wiseman, Jul 08 2019 REFERENCES S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 180-183. LINKS Fausto A. C. Cariboni, Table of n, a(n) for n = 0..88, (terms up to a(70) from Per Hakan Lundow) P. J. Cameron and P. Erdős, On the number of integers with various properties, in R. A. Mullin, ed., Number Theory: Proc. First Con. of Canad. Number Theory Assoc. Conf., Banff, De Gruyter, Berlin, 1990, pp. 61-79. Steven R. Finch, Several Problems Concerning Sum-Free Sets [Broken link] Steven R. Finch, Several Problems Concerning Sum-Free Sets [From the Wayback machine] Ben Green and Imre Z. Ruzsa, Sum-free sets in abelian groups, arXiv:math/0307142 [math.CO], 2004. A. A. Sapozhenko, The Cameron-Erdős conjecture, Discrete Math., 308 (2008), 4361-4369. Eric Weisstein's World of Mathematics, Sum-Free Set FORMULA a(n) = A050291(n)-A088810(n) = A085489(n)-A088811(n) = A050291(n)+A085489(n)-A088813(n). - Reinhard Zumkeller, Oct 19 2003 EXAMPLE {} has one sum-free subset, the empty set, so a(0)=1; {1} has two sum-free subsets, {} and {1}, so a(1)=2. a(2) = 3: 0,1,2. a(3) = 6: 0,1,2,3,13,23. a(4) = 9: 0,1,2,3,4,13,14,23,34. MAPLE S3S:= {{}}: a[0]:= 1: for n from 1 to 35 do S3S:= S3S union map(t -> t union {n}, select(t -> (t intersect map(q -> n-q, t)={}), S3S)); a[n]:= nops(S3S) od: seq(a[n], n=0..35); # Code for computing (the number of) sum-free subsets of {1, ..., n} - Robert Israel MATHEMATICA SumFreeSet[ 0 ] = {{}}; SumFreeSet[ n_ ] := SumFreeSet[ n ] = Union[ SumFreeSet[ n - 1 ], Union[ #, {n} ] & /@ Select[ SumFreeSet[ n - 1 ], Intersection[ #, n - # ] == {} & ] ] As a check, enter Length /@ SumFreeSet /@ Range[ 0, 30 ] Alternatively, use NestList. n = 0; Length /@ NestList[ (++n; Union[ #, Union[ #, {n} ] & /@ Select[ #, Intersection[ #, n - # ] == {} & ] ]) &, {{}}, 30 ] (* from Paul Abbott, based on Robert Israel's Maple code *) Timing[ n = 0; Last[ Reap[ Nest[ (++n; Sow[ Length[ # ] ]; Union[ #, Union[ #, {n} ]& /@ Select[ #, Intersection[ #, n - # ] == {} & ] ]) &, {{}}, 36 ] ] ] ] (* improved code from Paul Abbott, Nov 24 2005 *) Table[Length[Select[Subsets[Range[n]], Intersection[#, Total/@Tuples[#, 2]]=={}&]], {n, 1, 10}] (* Gus Wiseman, Jul 08 2019 *) PROG (PARI) \\ good only for n <= 25: sumfree(v) = {for(i=1, #v, for (j=1, i, if (setsearch(v, v[i]+v[j]), return (0)); ); ); return (1); } a(n) = {my(nb = 0); forsubset(n, s, if (sumfree(Set(s)), nb++); ); nb; } \\ Michel Marcus, Nov 08 2020 CROSSREFS See A085489 for another version. Cf. A211316, A211317, A093970, A093971 (number of sum-full subsets of 1..n). Cf. A050291, A103580, A151897, A308546, A326020, A326080, A326083. Sequence in context: A147364 A147227 A147063 * A052812 A213331 A218153 Adjacent sequences:  A007862 A007863 A007864 * A007866 A007867 A007868 KEYWORD nonn,nice AUTHOR EXTENSIONS More terms from John W. Layman, Oct 21 2000 Extended through 2630061 by Robert Israel, Nov 16 2005; two further terms from Alec Mihailovs (alec(AT)mihailovs.com) (using Robert Israel's procedure), Nov 16 2005 7051789 from Eric W. Weisstein, Nov 17 2005 10747207, 14158720, 21295570, 28188520 from Eric W. Weisstein, Nov 28 2005, using Paul Abbott's Mathematica code STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified December 1 14:10 EST 2021. Contains 349430 sequences. (Running on oeis4.)