/prog/ challenge

A set of integers is sum-free when addition always gets you out of the set (i.e. x + y = z has no solutions -- in other words S + S and S are disjoint). Formally, let S be a subset of N. S is sum-free if for all a,b in S, a+b is not in S.

Now, let S be any set of nonzero integers. Find a subset of size > |S|/3.

You may use your favorite lisp language.

I've got a really nice solution for this one.

>>7
You want a subset of S then? Because your description wasn't clear on that point. I realized what you probably meant after posting.

Anyway, more Perl 6 (whee, junctions)

sub sumfree($l) {
$l.combinations( Int($l/3) ).grep: { (@^a X+ @^a).any == @^a.none }
}

This gives |S|/3, or |S|/3 -1 'cause I'm stupid. The fix is easy, use Int($l/3)+1 combinations.