Find set S of 7 numbers such that the set of all sums s1, s1 + s2, s1 + s2 + s3 for s1, s2, and s3 in S contains the set of positive integers [1, 70]

numbersets.py

import multiprocessing
import sys

def rsetgen(count, floor, ceiling):
    """
    Recursively generate all possible sets of
    count unique numbers between floor and ceiling
    """
    if 1 == count:
        for i in xrange(floor, ceiling):
            yield [i]
    else:
        for i in xrange(floor, ceiling):
            for s in rsetgen(count - 1, i + 1, ceiling):
                yield [i] + s

def pick(count, numbers):
    """
    Recursively generate all possible combinations
    of count items selected from the set numbers
    """
    if 1 == count:
        for i in numbers:
            yield [i]
    else:
        for i in numbers:
            for s in pick(count - 1, numbers):
                yield [i] + s

def worker(top, in_queue, out_queue):
    """
    Get sets of numbers on in_queue, test them
    for coverage in the target range and put the
    set with the missing count onto out_queue
    """
    target = set(range(1, top + 1))
    while True:
        numberset = in_queue.get()
        if numberset is None:
            out_queue.put(None)
            break
        result = set()
        for taken in pick(3, numberset):
            result.add(sum(taken))
        missing = len(target - result)
        out_queue.put((missing, numberset))

def driver(top, in_queue, worker_count):
    """
    Put sets for testing (generated by rsetgen) onto in_queue
    A quit signal (None) is put on the queue for each worker
    """
    for i in range(2, 5):
        for s in rsetgen(5, i + 1, top - 1):
            in_queue.put([0, 1, i] + s)
    for i in range(worker_count):
        in_queue.put(None)

def main(top, worker_count):
    # set up the queues
    in_queue = multiprocessing.Queue(worker_count * 4)
    out_queue = multiprocessing.Queue()
    # start the worker processes to test sets
    print("running on %d workers" % worker_count)
    for i in range(worker_count):
        p = multiprocessing.Process(target=worker, args=(top, in_queue, out_queue))
        p.daemon = True
        p.start()
    # start the driver process to generate sets as input to workers
    p = multiprocessing.Process(target=driver, args=(top, in_queue, worker_count))
    p.daemon = True
    p.start()

    # now process items from worker processes on out_queue
    done = 0
    missing = top
    soln = None
    while done < worker_count:
        result = out_queue.get()
        if result is None:
            done += 1
        else:
            m, numberset = result
            if 0 == m:
                return result
            if m < missing:
                soln = numberset
    return missing, soln

if __name__ == '__main__':
    worker_count = multiprocessing.cpu_count() - 2
    result = main(int(sys.argv[1]), worker_count)
    print repr(result)