A211317 -id:A211317 - cp's OEIS frontend

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

Peter J. Cameron

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

			{} 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.

S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 180-183.

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..88, (terms up to a(70) from Per Hakan Lundow)
József Balogh, Hong Liu, Maryam Sharifzadeh, and Andrew Treglown, Sharp bound on the number of maximal sum-free subsets of integers, J. Eur. Math. Soc. 20 (2018), no. 8, pp. 1885-1911, also arXiv:1502.07605, Feb. 2015.
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

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.

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

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 *)

\\ 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

a(n) = A050291(n)-A088810(n) = A085489(n)-A088811(n) = A050291(n)+A085489(n)-A088813(n). - Reinhard Zumkeller, Oct 19 2003

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

A211316 Maximal size of sum-free set in additive group of integers mod n.

Original entry on oeis.org

1, 1, 2, 2, 3, 2, 4, 3, 5, 4, 6, 4, 7, 6, 8, 6, 9, 6, 10, 7, 11, 8, 12, 10, 13, 9, 14, 10, 15, 10, 16, 12, 17, 14, 18, 12, 19, 13, 20, 14, 21, 14, 22, 18, 23, 16, 24, 16, 25, 18, 26, 18, 27, 22, 28, 19, 29, 20, 30, 20, 31, 21, 32, 26, 33, 22, 34, 24, 35, 24

Offset: 2

N. J. A. Sloane, Apr 24 2012

nonn

Bela Bajnok, Additive Combinatorics: A Menu of Research Problems, Manuscript, May 2017. See Table in Section 1.6.1.
A. P. Street, Counting non-isomorphic sum-free sets, in Proc. First Australian Conf. Combinatorial Math., Univ. Newcastle, 1972, pp. 141-143.

Reinhard Zumkeller, Table of n, a(n) for n = 2..10000
Bela Bajnok, Additive Combinatorics: A Menu of Research Problems, arXiv:1705.07444 [math.NT], May 2017. See Table in Section 1.6.1.
Ben Green and Imre Z. Ruzsa, Sum-free sets in abelian groups, arXiv:math/0307142 [math.CO], 2004.

Bisection: A211317. Cf. A007865, A027748, A003627.

a211316 n | not $ null ps = n * (head ps + 1) `div` (3 * head ps)
          | m == 0        = n'
          | otherwise     = (n - 1) `div` 3
          where ps = [p | p <- a027748_row n, mod p 3 == 2]
                (n',m) = divMod n 3
-- Reinhard Zumkeller, Apr 25 2012

a[n_] := Module[{f = FactorInteger[n][[All, 1]]}, For[i = 1, i <= Length[f], i++, If[Mod[f[[i]], 3]==2, Return[n*(f[[i]] + 1)/3/f[[i]]]]]; If[Mod[n, 3] == 1, n-1, n]/3]
Table[a[n], {n, 2, 100}] (* Jean-François Alcover, Aug 02 2018, from PARI *)

a(n)=my(f=factor(n)[,1]); for(i=1,#f, if(f[i]%3==2, return(n*(f[i]+1)/3/f[i]))); if(n%3, n-1, n)/3 \\ Charles R Greathouse IV, Sep 02 2015

If n is divisible by a prime == 2 mod 3 then a(n) = n(p+1)/(3p) where p is the smallest such prime divisor; otherwise if n is divisible by 3 then a(n) = n/3; otherwise all prime divisors of n are == 1 mod 3 and a(n) = (n-1)/3.

In particular, a(2n) = n (cf. A211317).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions