Finding sum-free partitions Executive summary

Given input k, find a partition of integers 1 to n into k sum-free subsets for the largest n you can within 10 minutes.

Background: Schur numbers

A set A is sum-free if its self-sum A + A = { x + y | x, y in A} has no elements in common with it.

For every positive integer k there is a largest integer S(k) such that the set {1, 2, ..., S(k)} can be partitioned into k sum-free subsets. This number is called the kth Schur number (OEIS A045652).

For example, S(2) = 4. We can partition {1, 2, 3, 4} as {1, 4}, {2, 3}, and that is the unique partition into two sum-free subsets, but we can't now add a 5 to either part.

Challenge

Write a deterministic program which does the following:


Take a positive integer k as input
Write the current Unix timestamp to stdout
Outputs a sequence of partitions of 1 to n into k sum-free subsets for increasing n, following each sequence with the current Unix timestamp.


The winner will be the program which prints a partition for the largest n within 10 minutes on my computer when given input 5. Ties will be broken by the quickest time to find a partition for the largest n, averaged over three runs: that's why the output should include timestamps.

Important details:


I have Ubuntu Precise, so if your language is not supported I will be unable to score it.
I have an Intel Core2 Quad CPU, so if you want to use multithreading there's no point using more than 4 threads.
If you want me to use any particular compiler flags or implementation, document that clearly in your answer.
You shall not special-case your code to handle the input 5.
You are not required to output every improvement you find. E.g. for input 2 you could output only the partition for n = 4. However, if you don't output anything in the first 10 minutes then I will score that as n = 0.
Python 3, sort by greatest number, n = 92 121
Thanks to Martin Büttner for a suggestion that unexpectedly improved the maximum n reached.
Last output:
[2, 3, 11, 12, 29, 30, 38, 39, 83, 84, 92, 93, 110, 111, 119, 120]
[1, 4, 10, 13, 28, 31, 37, 40, 82, 85, 91, 94, 109, 112, 118, 121]
[5, 6, 7, 8, 9, 32, 33, 34, 35, 36, 86, 87, 88, 89, 90, 113, 114, 115, 116, 117]
[14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108]
[41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81]

The algorithm is the same as my previous answer, quoted below:

There are k bins that have both the numbers in it so far and the numbers that can't go in it anymore. At each depth in the iteration (it's basically a depth-first search), the bin ordering is shuffled and the next number (nextN) is (sequentially) put into the bins that can take it and then goes one step deeper. If there are none, it returns, backing up one step.

...with one exception: the bin ordering is not shuffled. Instead, it is sorted in such a way that the bins with the greatest number come first. This reached n = 121 in 8 seconds!
Code:
from copy import deepcopy
from random import shuffle, seed
from time import clock, time
global maxN
maxN = 0
clock()

def search(k,nextN=1,sets=None):
    global maxN
    if clock() &gt; 600: return
    
    if nextN == 1: #first iteration
        sets = []
        for i in range(k):
            sets.append([[],[]])

    sets.sort(key=lambda x:max(x[0]or[0]), reverse=True)
    for i in range(k):
        if clock() &gt; 600: return
        if nextN not in sets[i][1]:
            sets2 = deepcopy(sets)
            sets2[i][0].append(nextN)
            sets2[i][1].extend([nextN+j for j in sets2[i][0]])
            nextN2 = nextN + 1
            
            if nextN &gt; maxN:
                maxN = nextN
                print(&quot;New maximum!&quot;,maxN)
                for s in sets2: print(s[0])
                print(time())
                print()
                
            search(k, nextN2, sets2)

search(5)