Search: id:A007865
Results 1-1 of 1 results found.

%I A007865
%S A007865 1,2,3,6,9,16,24,42,61,108,151,253,369,607,847,1400,1954,3139,4398,
%T A007865 6976,9583,15456,20982,32816,45417,70109,94499,148234,200768,308213,
%U A007865 415543,634270,849877,1311244,1739022,2630061,3540355,5344961,7051789,
               10747207,14158720,21295570,28188520
%N A007865 Number of sum-free subsets of {1, ..., n}.
%C A007865 More precisely, subsets of {1,...,n} containing no solutions of x+y=z.
%C A007865 There are two proofs that a(n) is 2^{n/2}(1+o(1)), as Paul Erdos and 
               I conjectured.
%C A007865 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 (noe(AT)sspectra.com), Apr 20 2004
%C A007865 The Sapozhenko paper has many additional references.
%D A007865 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.
%D A007865 S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 180-183.
%D A007865 A. A. Sapozhenko, The Cameron-Erdos conjecture, Discrete Math., 308 (2008), 
               4361-4369.
%H A007865 Per Hakan Lundow, <a href="b007865.txt">Table of n, a(n) for n = 0..70</
               a>
%H A007865 S. R. Finch, <a href="http://algo.inria.fr/bsolve/constant/cameron/sf/
               sf.html">Several Problems Concerning Sum-Free Sets</a>
%H A007865 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               Sum-FreeSet.html">Sum-Free Set</a>
%F A007865 a(n) = A050291(n)-A088810(n) = A085489(n)-A088811(n) = A050291(n)+A085489(n)-A088813(n). 
               - Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Oct 19 2003
%e A007865 {} has one sum-free subset, the empty set, so a(0)=1; {1} has two sum-free 
               subsets, {} and {1}, so a(1)=2.
%e A007865 a(2) = 3: 0,1,2
%e A007865 a(3) = 6: 0,1,2,3,13,23
%e A007865 a(4) = 9: 0,1,2,3,4,13,14,23,34
%p A007865 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);
%t A007865 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 ]
%t A007865 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 
               ] ] ] ]
%Y A007865 See A085489 for another version.
%Y A007865 Cf. A093970, A093971 (number of sum-full subsets of 1..n).
%Y A007865 Sequence in context: A147364 A147227 A147063 this_sequence A052812 A062114 
               A094768
%Y A007865 Adjacent sequences: A007862 A007863 A007864 this_sequence A007866 A007867 
               A007868
%K A007865 nonn,nice
%O A007865 0,2
%A A007865 Peter Cameron (P.J.Cameron(AT)qmw.ac.uk)
%E A007865 More terms from John W. Layman (layman(AT)math.vt.edu), Oct 21 2000
%E A007865 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
%E A007865 7051789 from Eric Weisstein (eric(AT)weisstein.com), Nov 17, 2005
%E A007865 10747207, 14158720, 21295570, 28188520 from Eric Weisstein (eric(AT)weisstein.com), 
               Nov 28, 200, using Paul Abbott's Mathematica code.

Search completed in 0.002 seconds