/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.

>>40
DOGS R 4 BOYZ, CATS R 4 GIRLZ

>>40
Why are you ``generating'' the subset when you should be selecting elements from the superset?

>>42
That's what I meant, that's what the code does. After the prime is found (say, in form 3k + 2), a loop is run, 1<=i<=p. Calculate {i*x_j mod p}. These sets are sum-free, and one is guaranteed to be at least n/3 + 1 in size.

I promise code, one of these days.

>>34
The point was to show the solution in >>11-12 was correct for the purposes of the challenge.

>>41
Get a load of this fuckin 1950s retard. Go back there you stupid dog fucking virgin nigger.

NIGGER

>>45
Get a load of this fucking 1950's piece of shit. Go back there you theist shitlord.

So are you going to post your solution?

>>48
Here's pseudocode:
Input:
Let X = {x_i} be the given set.

Output:
Find a prime p such that:
p = 3k + 2
p > 2max{|x_i|}

For 1 <= j < p:
let S = { j*x_i mod p }
if |S| > |X|/3 break

return S

Sorry I'm not writing any code in a real language but I'm messing with some emacs modes right now. Btw, the book I read this from mentions that the requirements for p can be dropped: It is sufficient that p simply does not divide any of the |x_i|. I did not check if the algorithm works as-is with such a p, and that is what I intented to do when I said I'll post code in a few days, or else I would simply post an implementation of the pseudo-code I just posted.

Sorry for the delay.

>>41
AAAWWW LQQK DAAAAAAAA, AN0THER 01D FUK FACE 01D HERPEZ DAMN WH0RE 2 LQQK AT ANN HEAR WAT DA DAMN B1MB0 B0Z0 B1TCH BASTARD HAZZ 2 SAY FR0M HRR 01D MUDD M0UTH H01E, HRR DAMN MAMA ANN DADA MUST B REA1 FUK1N PR0UD 0F DER DUMB ASS CUP1D S0 STUP1D DAMN 2 HE11 DAMN DAUGTHER 4 ACT1N TH1Z WAY 1NN FR0NT 0F M1LL1ONZ 0F PPL DA D0NT EVEN CARE N0R WANT 2 HEAR HRR 01D FAT S0 SAD ASS TALK , N0TT EVEN 4 A FUK1N DAMN M1NUTE, U R A FUK1N F0U1 DAMN F001, S0 U D0NT CARE AS WE REA11Y D0NT CARE 1F U CR0AK 2MORROW U DUMB ASS BEEEEEEEECCHHAAAAAAA :-)