A007865 Number of sum-free subsets of {1, ..., n}.

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

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 Conf. 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: A147227 A147063 A357640 * 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 a(35) by Robert Israel, Nov 16 2005

a(36)-a(37) from Alec Mihailovs (alec(AT)mihailovs.com) (using Robert Israel's procedure), Nov 16 2005

a(38) from Eric W. Weisstein, Nov 17 2005

a(39)-a(42) from Eric W. Weisstein, Nov 28 2005, using Paul Abbott's Mathematica code

Status

approved