Sum-Free Set

Author

Eric W. Weisstein
November 27, 2005

This notebook downloaded from http://mathworld.wolfram.com/notebooks/SetTheory/Sum-FreeSet.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/Sum-FreeSet.html.

©2005 Wolfram Research, Inc. except for portions noted otherwise

Additional Authors

SumFreeSet and SumFreeSet2 by Paul Abbott
November 16 and 24, 2005

Code

SumFreeSet[0]={{}};SumFreeSet[n_]:=SumFreeSet[n]=Union[SumFreeSet[n-1],Union[#,{n}]&/@Select[SumFreeSet[n-1],Intersection[#,n-#]=={}&]]

NumbersOfSumFreeSets[nmax_]:=Module[{n=0},
Last[Reap[
Nest[(++n;Sow[Length[#]];
Union[#,Union[#,{n}]& /@Select[#,Intersection[#,n-#]=={}&]])&,{{}},nmax+1]
]
]
]

Tables

Standard

(Select[Subsets[Range[#]],SumFreeQ]&/@Range[0,5])//ColumnForm

Length /@ SumFreeSet /@ Range[0,38]//Timing

NumbersOfSumFreeSets[43]//Timing

NumbersOfSumFreeSets[44]//Timing

...out of memory...

Nonstandard Definition

SumFreeSet2Q[l_List?VectorQ]:=True /; Length[l]<3
SumFreeSet2Q[l_List?VectorQ]:=Intersection[l,Plus@@@Subsets[l,{2}]]=={}

Table[Select[Subsets[n],SumFreeSet2Q],{n,4}]//ColumnForm

Counts of Subsets of {1, …, n}

Length/@Table[Select[Subsets[Range[n]],SumFreeSet2Q],{n,10}]