

A007865


Number of sumfree 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 sumfree sets, then A326083 counts sumclosed sets, which is different from sumfull sets (A093971).  Gus Wiseman, Jul 08 2019


REFERENCES

S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 180183.


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. 6179.
Steven R. Finch, Several Problems Concerning SumFree Sets [Broken link]
Steven R. Finch, Several Problems Concerning SumFree Sets [From the Wayback machine]
Ben Green and Imre Z. Ruzsa, Sumfree sets in abelian groups, arXiv:math/0307142 [math.CO], 2004.
A. A. Sapozhenko, The CameronErdős conjecture, Discrete Math., 308 (2008), 43614369.
Eric Weisstein's World of Mathematics, SumFree 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 sumfree subset, the empty set, so a(0)=1; {1} has two sumfree 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 > nq, t)={}), S3S)); a[n]:= nops(S3S) od: seq(a[n], n=0..35); # Code for computing (the number of) sumfree 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 sumfull 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

Peter J. Cameron


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



