Calculate a maximal length 3 progression free subset of [N].

roth.py

from sys import argv
import math

N = int(argv[1])
S = set();

k = N

for j in range(1,N+1):
    S.add(j)

while k > 1:
    removed = 0

    for i in range(1,int(math.floor(k/2)+1)):
        if k - 2*i > 0:
            S.remove(k - i)
            removed += 1

    k -= removed + 1

print S

# Experimental results indicate that |S| decreases exponentially
# in N, S ~ 2^kN * N
#
# In relation to http://goo.gl/gnxgQU on the P=NP blog