# Is it a sum-free set?

A set is sum-free if no two (not necessarily distinct) elements when added together are part of the set itself.

For example, {1, 5, 7} is sum-free, because all members are odd, and two odd numbers when added together are always even. On the other hand, {2, 4, 9, 13} is not sum-free, as either 2 + 2 = 4 or 4 + 9 = 13 add together to a member of the set.

Write a program or function that takes a set as input, and outputs a Truthy value if the set is sum-free, and Falsy otherwise.

Examples:

Sum-free:
{}
{4}
{1, 5, 7}
{16, 1, 4, 9}

Not sum-free:
{0}
{1, 4, 5, 7}
{3, 0}
{16, 1, 4, 8}

• Can the set be an array/list? Jul 7, 2016 at 1:05
• @CᴏɴᴏʀO'Bʀɪᴇɴ Sure.
– orlp
Jul 7, 2016 at 1:17
• Some more test cases might be nice!
– Lynn
Jul 7, 2016 at 1:52
• Badly needs test cases. Are sets purely unique?
– cat
Jul 7, 2016 at 2:33
• I think you should clarify that you mean the sum of two not necessarily distinct elements from the set. Jul 9, 2016 at 0:32

# Python 2, 41 bytes

lambda s:s==s-{a+b for a in s for b in s}


s should be a Python set.

Fun fact: sum-free is an anagram of my name.

• lambda s:not{a+b for a in s for b in s}&s is the same length. I can't find a way to shorten the negation, sadly. Jul 7, 2016 at 1:41
• Upvoted for anagram.
– Neil
Jul 7, 2016 at 7:56
• @feersum this is your question. Jul 7, 2016 at 17:21
• @FilipHaglund No, it's orlp's. Jul 14, 2016 at 21:48
• @mbomb007 If serious, yes. But, that can have a non-serious meaning: This is your question/You OWND the question/You beat everyone else here (Python). They didn't say "You are the OP." Jul 15, 2016 at 8:57

# Jelly, 5 bytes

ṗ3ḅ-P


Try it online!

### How it works

ṗ3ḅ-P  Main link. Argument: A (array)

ṗ3     Take the third Cartesian power of A, i.e., generate all triplets that
consist of elements of A.
ḅ-   Convert each triplet from base -1 to integer.
This maps [a, b, c] to a - b + c = (a + c) - b.
If (a + c) belong to A, this will yield 0 for some b.
P  Take the product of all resulting integers.


# Pyth - 8 5 bytes

Thanks to @FryAmTheEggman for saving me 3 bytes.

!@sM*

!             Logical not. This makes the empty intersection true and vice versa.
@    Q       Setwise intersection with input (implictly).
sM          Map sum to all the pairs.
*QQ        Get all pairs by doing cartesian product with input*input (implicit).

• @FryAmTheEggman smart.... Jul 7, 2016 at 1:55
• I just got the same answer, but then realized *QQ actually produces [1,1], which are two same elements, and should not appear in the map. Jul 7, 2016 at 2:41
• @busukxuan the question actually asks you to consider duplicates: 2 + 2 = 4 from OP. My answer before FryAmTheEggman's golf actually used .Combinations with replacement because of this. Jul 7, 2016 at 2:49
• @Maltysen Oh nice! Jul 7, 2016 at 3:09

# JavaScript, 8642 41 bytes

n=>!n.some(m=>n.some(o=>n.includes(m+o)))


Thanks Cᴏɴᴏʀ O'Bʀɪᴇɴ for saving me a ton of bytes off parentheses/curly brackets. Also thanks Neil for pointing out that the function was returning the opposite boolean value than it should have.

I tried to cut down on bytes by redefining n.some but that doesn't work because it's a prototype function unfortunately. There might be a better solution with Array.prototype.map in JS but the some function is really fun.

I'm now wondering if there's a shorter way than .includes using something such as .indexOf and adding 1 (which would give it a truthy value if it contains the number).

Testing:

> (n=>!n.some(m=>n.some(o=>n.includes(m+o))))([1,5,7]);
true
> (n=>!n.some(m=>n.some(o=>n.includes(m+o))))([1,5,7,12]);
false

• Try n=>n.some(m=>n.some(o=>n.some(p=>m+o==p))) Jul 7, 2016 at 3:02
• No problem! it works because of the behaviour of the anonymous functions. Look at other ES6 answers around here, you'll learn quite a lot :) Jul 7, 2016 at 3:05
• Hello, and welcome to PPCG! Jul 7, 2016 at 3:09
• The sense of this is wrong, it tells you if the set is not sum-free. Also, use n.contains(o+p) which saves you 2 bytes over the innermost some.
– Neil
Jul 7, 2016 at 7:59
• Sorry, yes, I meant includes (it was originally going to be called contains but some library has a conflicting definition).
– Neil
Jul 7, 2016 at 8:27

# MATL, 5 bytes

t&+m~


This outputs an array which is truthy if all entries are 1 and falsey otherwise. Here is a demo to show various truthy/falsey values in MATL.

Try it Online

Explanation

        % Implicitly grab input
t       % Duplicate
&+      % Compute sum of each element with every other element (2D Matrix)
m       % Check which members of the input are present in this matrix of sums
~       % Negate the result to yield a truthy value for sum-free sets
% Implicitly display truthy/falsey value


# Mathematica, 23 Bytes

{}==#⋂Tr/@#~Tuples~2&

• I mistakenly edited your submission, but then rolled it back to the way it was. Sorry! Jul 7, 2016 at 12:27
• By the way, nice insight that no element had to be removed from the list before making tuples. Jul 7, 2016 at 12:32
• Please replace ∩ with ⋂ (U-22C2). The code right now isn't copypastable into Mathematica. Jul 7, 2016 at 13:47
• @LLlAMnYP Thanks, I had to manually find the unicode character since Mathematica automatically formats expressions when you copy them; I must have found the wrong one. Jul 7, 2016 at 14:35
• @ASimmons If you highlight the character in Mathematica and hit F1 it will show you the help page for that specific character which always contains the character's Unicode code point (in hexadecimal). It's really annoying though that you can't just copy it as Unicode. I think there's a solution for "copy as Unicode" somewhere on Mathematica.SE but IIRC it was far from trivial. Jul 7, 2016 at 14:59

Simple solution:

f x=and[a+b/=c|a<-x,b<-x,c<-x]


Two bytes saved by @Lynn

• f x=and[a+b/=c|a<-x,b<-x,c<-x] for 30 bytes.
– Lynn
Jul 7, 2016 at 14:52

# Julia, 18 bytes

!x=x∩(x'.+x)==[]


Try it online!

# J, 1810 8 bytes

8 bytes saved thanks to miles, and 2 thanks to FrownyFrog!

-:]-.+/~


Matches the original list with the set difference of tabulated sums. This is equivalent to:

(-: (] -. +/~)) y


for input y. This translates to:

y -: (] -. +/~) y
y -: (y -. +/~ y)


+/~ returns a table of sums using y. For y =: 16 1 4 9, this gives:

   +/~ 16 1 4 9
32 17 20 25
17  2  5 10
20  5  8 13
25 10 13 18


Then, we use -., which produces a list consisting of all elements in y not in this table. If the list is sum-free, this will produce the same list. Then, -: checks for equality of lists, which produces the desired output.

## Old, 18 bytes

[:-.[:>./^:_+/~e.]


+/~ creates a table of the values of the set added to itself, and e. checks if those members are in the original set. The rest of that is negating the maximal element.

• -:]-.&,+/~ for 10 bytes using set difference -. and list matching -: Jul 7, 2016 at 2:18
• Ooo, very nice! Jul 7, 2016 at 2:18
• You don't need &, -. already works with cells of y. May 24, 2018 at 11:14
• @FrownyFrog Fascinating, TIL. Thanks! May 24, 2018 at 15:54

## Retina, 45 44 bytes

\d+
<$&$*1>
$ M(<1*)>.*<(1*>).*\1\2 ^0  Input is a decimal list of comma-separated numbers. Output is 0 (falsy) or 1 (truthy). Try it online! (The first line enables a linefeed-separated test suite.) ### Explanation Stage 1: Substitution \d+ <$&$*1>  This converts all elements of the input to unary and wraps them in <...>. The purpose of the angle brackets is to distinguish a list containing only 0 from an empty list (since the unary representation of 0 is empty itself). Stage 2: Substitution $
$$


We repeat the string 3 times by append it twice at the end.

Stage 3: Match

M(<1*)>.*<(1*>).*\1\2


We now try to find three numbers in the result such that the first two add up to the third. Those matches are counted (this doesn't actually count all such tuples, because matches cannot overlap, but if such a tuple exists it will be found). Hence, we get 0 for sum-free sets and something positive otherwise.

Stage 4: Match

^0


Since the previous stage gave the opposite of what we want, we negate the result by counting the matches of ^0 which is 1 for input 0 and 0 for everything else.

# Octave, 2921 25 bytes

@(s)~[ismember(s,s+s') 0]


Thanks to Suever! It returns an array. I added 0 at the end to make [] become sum-free. To verify truthy and falsey in Octave, you can do this:

> f=@(s)~[ismember(s,s+s') 0]

> if f([]) "sum-free" else "not sum-free" end
ans = sum-free

> if f() "sum-free" else "not sum-free" end
ans = not sum-free

> if f() "sum-free" else "not sum-free" end
ans = sum-free

> if f([1 3]) "sum-free" else "not sum-free" end
ans = sum-free

> if f([2 4]) "sum-free" else "not sum-free" end
ans = not sum-free


An alternative that returns 0 or 1 is:

@(s)~numel(intersect(s+s',s))

• You could change it to be @(s)~ismember(s+s',s) since arrays can be truthy/falsey Jul 7, 2016 at 12:32

# Clojure, 47 37 bytes

#(=(for[a % b % :when(%(+ a b))]a)[])


quite plain solution. uses list comprehension to find all elements which sum is equal to another element.

38 bytes variant:

#(every? nil?(for[a % b %](%(+ a b))))

• Since in the challenge you are taking a set as your input, you can simply use the set to check for membership as in #(=(for[a % b % :when(%(+ a b))]a)[]) which can save 10 bytes Jul 7, 2016 at 13:24
• @miles oh wow, thanks, i did kinda ignore that fact and worked with lists. Jul 7, 2016 at 13:32

# Perl 6,  24 21 20  19 bytes

{not any (@_ X+@_)X==@_}
{so all (@_ X+@_)X!==@_}
{not @_ (&)(@_ X+@_)}
{not @_∩(@_ X+@_)}

{!(@_∩(@_ X+@_))}

Input is any Positional value like a List.
( a Set is an Associative so you would have to call .keys on it. )

### Test:

#! /usr/bin/env perl6
use v6.c;
use Test;

my @sum-free = (
(),
(4,),
(1, 5, 7),
(16, 1, 4, 9),
);

my @not-sum-free = (
(0,),
(1, 4, 5, 7),
(3, 0),
(16, 1, 4, 8),
);

my @tests = ( |(@sum-free X=> True), |(@not-sum-free X=> False) );

plan +@tests;

# store the lambda in lexical namespace for clarity
my &sum-free-set = {!(@_∩(@_ X+@_))}

for @tests -> $_ ( :key(@list), :value($expected) ) {
is sum-free-set(@list), $expected, .gist }  1..8 ok 1 - () => True ok 2 - (4) => True ok 3 - (1 5 7) => True ok 4 - (16 1 4 9) => True ok 5 - (0) => False ok 6 - (1 4 5 7) => False ok 7 - (3 0) => False ok 8 - (16 1 4 8) => False  # Mathematica 63 62 42 bytes This shorter version benefitted from A Simmons' submission. No element needs to be removed from the list before IntegerPartitions is applied. If an element cannot be partitioned into two integers (each from the list), then IntegerPartitions[#,{2},#]=={} holds. And checks whether this holds for every element in the list. If so, the list is sum-free. And@@(IntegerPartitions[#,{2},#]=={}&/@#)&  ## Examples  And@@(IntegerPartitions[#,{2},#]=={}&/@ #)&@{2, 4, 9, 13}  False  And@@(IntegerPartitions[#,{2},#]=={}&/@ #)&@{1, 5, 7}  True There is a 2, but no odd numbers that differ by 2.  And@@(IntegerPartitions[#,{2},#]=={}&/@#)&@{2, 3, 7, 11, 17, 23, 29, 37, 41, 47, 53, 59, 67, 71}  True • Do you have a defined somewhere else in your workbook? These expressions don't give the desired output when I evaluate them. Jul 7, 2016 at 14:38 • Thanks. That a should have been a #. I corrected it and removed a superfluous @. Jul 7, 2016 at 21:35 # R, 39 36 bytes w<-function(s)!any(outer(s,s,'+')%in%s)  Call as w(s), where s is the set (actually vector) of values. Here is the output for some test cases: > w(numeric(0)) # The empty set  TRUE > w(0)  FALSE > w(1)  TRUE > w(c(1, 5, 7))  TRUE > w(c(2, 4, 9, 13))  FALSE  Where c() is the concatenation function that takes a bunch of values and makes it a vector. EDIT: Making it an anonymous function to save 3 bytes, thanks to @MickyT. function(s)!any(outer(s,s,'+')%in%s)  • Very nice. You can post these as an unnamed function if you like. That would save you 3 bytes. eg function(s)!any(outer(s,s,'+')%in%s) Jul 7, 2016 at 10:29 # Ruby, 36 bytes Constructs a cartesian product of the set against itself and finds the sum of all elements, then checks for intersection with the original set. Input is arrays, but in Ruby they have enough set operations to make it work out nicely anyways. -1 byte over my original solution (used & instead of - and compared with []) because of inspiration from @feersum Try it here! ->s{s-s.product(s).map{|x,y|x+y}==s}  # Python, 40 bytes lambda s:s^{a+b for a in s for b in s}>s  ^ = symmetric difference, new set with elements in either sets but not both > True if the left set is a superset of the right set. • This doesn't work for the empty set, though I don't know if that's required. – xnor Jul 7, 2016 at 8:19 • Well, wikipedia says (among other things) that A is sum-free if the equation a + b = c has no solution with a, b, c ∈ A. With this definition, the empty set is not sum free, and my answer is correct. But I may be biased. Jul 7, 2016 at 8:34 • That definition implies that the empty set is sum-free, as there are no a, b and c in the empty set that satisfy the equation. The OP's newly added test cases support this. Jul 7, 2016 at 18:47 # Brachylog, 13 bytes '(p:?+L:?x'L)  ### Explanation '( ) True if what's in the parentheses is impossible, false otherwise p Get a permutation of Input :?+L L is the list of element-wise sums of the permutation with Input :?x'L There is at least one element of Input in L  • Is [2:2] a subset of 2 elements of [2:4:9]? Jul 7, 2016 at 9:52 • @LeakyNun No, because 2 only appears once in [2:4:9]. Jul 7, 2016 at 10:00 # Racket, 58 bytes (λ(l)(andmap(λ(m)(andmap(λ(n)(not(memq(+ n m)l)))l))l))  Explanation: (λ(l)(andmap(λ(m)(andmap(λ(n)(not(memq(+ n m)l)))l))l)) (λ(l) ) # Define a lambda function that takes in one parameter (andmap(λ(m) )l) # If for all m in l (andmap(λ(n) )l) # If for all n in l (not(memq(+ n m)l)) # n + m is not in l  # 05AB1E, 9 5 bytes Saved 4 bytes thanks to Magic Octopus Urn ãOå_P  Try it online! Explanation ã # cartesian product O # sum å # check each if it exists in input _ # logical negation P # product  • Is 0 really truthy in 05AB1E? Jul 7, 2016 at 15:53 • @Dennis I defined 0 as truthy for this challenge and anything else as falsy. Isn't that normally OK as long as it is unambiguous and OP hasn't specified a specific format? Jul 7, 2016 at 15:54 • This is our default interpretation of truthy/falsy. Jul 7, 2016 at 16:05 • @Dennis: Ah, too bad. sum-free = 0 and non-sum-free = "a sum" fitted nicely to the challenge imo. Seen a lot of other challenges which defined sums and similar non-standard values as true/false so I figured un-ambiguity was the default. I'll edit the answer then. Thanks for the heads up. Jul 7, 2016 at 16:09 • @MagicOctopusUrn: Thanks! Unsure if these commands worked this way back then, but they do now so thanks :) (I could just have missed it as well, I was pretty new to 05AB1E when I did this challenge) May 24, 2018 at 19:37 # APL, 8 bytes ⊢≡⊢~∘.+⍨  Explanation: ⊢ argument ≡ equals ⊢ argument ~ without ∘.+⍨ sums of its elements  Test:  ( ⊢≡⊢~∘.+⍨ ) ¨ (1 5 7)(2 4 9 13) 1 0  ## Haskell, 30 bytes f s=and[x+y/=z|x<-s,y<-s,z<-s]  I think there exists a shorter solution that's more interesting, but I haven't found it. These are 33 and 34 bytes: f s=and$((/=)<$>s<*>)$(+)<$>s<*>s f s|q<-((-)<$>s<*>)=all(/=0)$q$q$s  • does using elem on s and getting rid of the last part of the comprehsion work? Jul 7, 2016 at 5:43 • @Maltysen If you mean f s=and[notElem(x+y)s|x<-s,y<-s], that's 32. There's also f s=all(notElems)$(+)<$>s<*>s for 31. – xnor Jul 7, 2016 at 6:11 # Actually, 7 bytes ;;∙♂Σ∩Y  Try it online! ;;∙♂Σ∩Y Stack: [1,5,7] ; duplicate [1,5,7] [1,5,7] ; duplicate [1,5,7] [1,5,7] [1,5,7] ∙ cartesian product [1,5,7] [[1,1],[1,5],[1,7],[5,1],[5,5],[5,7],[7,1],[7,5],[7,7]] ♂Σ sum each [1,5,7] [2,6,8,6,10,12,8,12,14] ∩ intersect [] Y negate 1  • Maybe make your code more gender-equal? (♂) Jul 15, 2016 at 9:08 # TSQL, 47 bytes CREATE table T(a int) INSERT T values(1),(5),(7),(12) SELECT min(iif(a.a+b.a<>T.a,1,0))FROM T a,T b,T  Note: This will only run once, then the table needs to be deleted or dropped to run again. The fiddle editor doesn't allow creation of tables. Therefore the fiddle included in my answer uses 2 extra bytes to compensate for this - the fiddle version doesn't require cleanup. Fiddle # Perl, 46 bytes 45 bytes code + 1 byte command line (-p) $_="$_$_ $_"!~/(\b\d++.*)((?1))(??{$1+$2})/  Uses a single regex match with Perl's support for 'code expressions' inside the regex to allow for evaluation within a match. To get around the requirement that the input is unsorted, we repeat the input string three times. This guarantees that the result is after the two operands, and allows the same digit to be matched again (e.g. in the case of input 2 4). Usage example: echo "3 5 6 8" | perl -p entry.pl  # Factor, 47 bytes [ dup dup 2array [ Σ ] product-map ∩ { } = ]  • ∩ { } = is equivalent to but shorter than intersects?. • Σ is shorter than but equivalent to sum. Thanks, math.unicode! testing code: USING: arrays kernel math.unicode sequences sequences.product ; IN: sum-free : sum-free? ( seq -- ? ) dup dup 2array [ Σ ] product-map ∩ { } = ; USING: tools.test sum-free ; IN: sum-free.tests { t } [ { 5 7 9 } sum-free? ] unit-test { f } [ { 2 4 9 13 } sum-free? ] unit-test { t } [ { } sum-free? ] unit-test { f } [ { 0 } sum-free? ] unit-test { t } [ { 1 } sum-free? ] unit-test { f } [ { 0 1 } sum-free? ] unit-test  I'm only confident the first two are correct. It's unclear from the question what the rest should be, so I think it's fine for now. # PHP, 73 bytes +8 to turn the snippet into a program, -8 on obsolete variables thanks to insertusernamehere <?foreach($argv as$p)foreach($argv as$q)if(in_array($p+$q,$argv))die;echo 1;


prints 1 for true, empty output for false
usage: php <filename> <value1> <value2> ...

qualified function for testing (94 86): returns 1 or nothing

function f($a){foreach($a as$p)foreach($a as$q)if(in_array($p+$q,$a))return;return 1;}


tests

function out($a){if(!is_array($a))return$a;$r=[];foreach($a as$v)$r[]=out($v);return'['.join(',',$r).']';} function cmp($a,$b){if(is_numeric($a)&&is_numeric($b))return 1e-2<abs($a-$b);if(is_array($a)&&is_array($b)&&count($a)==count($b)){foreach($a as $v){$w = array_shift($b);if(cmp($v,$w))return true;}return false;}return strcmp($a,$b);} function test($x,$e,$y){static $h='<table border=1><tr><th>input</th><th>output</th><th>expected</th><th>ok?</th></tr>';echo"$h<tr><td>",out($x),'</td><td>',out($y),'</td><td>',out($e),'</td><td>',cmp($e,$y)?'N':'Y',"</td></tr>";$h='';}
$samples = [ [], 1, , false, , 1, [0,1], false, [2, 4, 9, 13], false, [1,5,7], 1 ]; while($samples)
{
$a=array_shift($samples);
$e=array_shift($samples);
test($a,$e,f($a)); }  • As you never use $i and $j you can discard $i=> as well as \$j=> and save 8 bytes. Unfortunately code snippets are not valid answers. Make it a function or a full program and include that in your byte count and you're ready to go. :) Jul 8, 2016 at 22:14

## Java, 67 bytes

s->!s.stream().anyMatch(p->s.stream().anyMatch(q->s.contains(p+q)))


Input is a Set<Integer>. Tests:

import java.util.Arrays;
import java.util.Set;
import java.util.function.Function;
import java.util.stream.Collectors;

public class SumFree {
public static void main(String[] args) {
sumFree(s->!s.stream()
.anyMatch(p->s.stream()
.anyMatch(q->s.contains(p+q)))); // formatted to avoid wrapping
}

public static void sumFree(Function<Set<Integer>, Boolean> func) {
test(func);
test(func, 4);
test(func, 1, 5, 7);
test(func, 16, 1, 4, 9);
test(func, 1, 4, 5, 7);
test(func, 0);
test(func, 3, 0);
test(func, 16, 1, 4, 8);
}

public static void test(Function<Set<Integer>, Boolean> func, Integer... vals) {
Set<Integer> set = Arrays.stream(vals).collect(Collectors.toSet());
System.out.format("%b %s%n", func.apply(set), set);
}
}


Output:

true []
true 
true [1, 5, 7]
true [16, 1, 4, 9]
false 
false [1, 4, 5, 7]
false [0, 3]
false [16, 1, 4, 8]


## Clojure, 34 bytes

#(not-any? %(for[i % j %](+ i j)))


I wrote this before noticing the earlier Clojure solution. Anyway, this one is more compact as it uses the input set as a pred function for not-any?.

# Prolog (SWI), 6656 49 bytes

A/B:-member(A,B).
-L:- \+ (E/L,F/L,G is E+F,G/L).


Try it online!