|
| |
|
|
A007865
|
|
Number of sum-free subsets of {1, ..., n}.
|
|
8
| |
|
|
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; 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 Erdos 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.
The subsequence of primes begins: 2, 3, 61, 151, 607, 308213, 415543, no others through a(70). [From Jonathan Vos Post, May 27 2010]
|
|
|
REFERENCES
| P. J. Cameron and P. Erdos, 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.
S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 180-183.
A. A. Sapozhenko, The Cameron-Erdos conjecture, Discrete Math., 308 (2008), 4361-4369.
|
|
|
LINKS
| Per Hakan Lundow, Table of n, a(n) for n = 0..70
S. R. Finch, Several Problems Concerning Sum-Free Sets
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
| Maple code from Robert Israel for computing (the number of) sum-free subsets of {1, ..., n}: 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);
|
|
|
MATHEMATICA
| Mathematica code from Paul Abbott based on Robert Israel's Maple code: 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 ]
Improved Mathematica code from Paul Abbott Nov 24 2005: Timing[ n = 0; Last[ Reap[ Nest[ (++n; Sow[ Length[ # ] ]; Union[ #, Union[ #, {n} ]& /@ Select[ #, Intersection[ #, n - # ] == {} & ] ]) &, {{}}, 36 ] ] ] ]
|
|
|
CROSSREFS
| See A085489 for another version.
Cf. A093970, A093971 (number of sum-full subsets of 1..n).
Sequence in context: A147364 A147227 A147063 * A052812 A062114 A094768
Adjacent sequences: A007862 A007863 A007864 * A007866 A007867 A007868
|
|
|
KEYWORD
| nonn,nice
|
|
|
AUTHOR
| Peter Cameron (P.J.Cameron(AT)qmw.ac.uk)
|
|
|
EXTENSIONS
| More terms from John W. Layman (layman(AT)math.vt.edu), Oct 21 2000
Extended through 2630061 by Robert Israel (israel(AT)math.ubc.ca), Nov 16 2005; two further terms from Alec Mihailovs (alec(AT)mihailovs.com) (using Robert Israel's procedure), Nov 16 2005
7051789 from Eric Weisstein (eric(AT)weisstein.com), Nov 17, 2005
10747207, 14158720, 21295570, 28188520 from Eric Weisstein (eric(AT)weisstein.com), Nov 28, 200, using Paul Abbott's Mathematica code.
|
| |
|
|
