Pitchup test

gistfile1.py

"""
Join us at pitch x. x is a number between 1 and 553 such that the sum of
x's divisors (not including x) is greater than x but no subset of x's
divisors add up to exactly x

Run on Python 3.4.3
tl;dr; result was 70
"""

import itertools


def divisors(n):
    """
    Returns all possible divisors for an integer,
    with the exception of the integer itself
    """
    s = set()
    for i in range(1, n - 1):
        if n % i == 0:
            s.add(i)
    return s


def check_subsets(s, x):
    """
    Check sums of all possible combinations of set s.

    Returns true if none of the possible combinations
    add up to x.
    """

    for i in range(1, len(s)):
        for c in itertools.combinations(s, i):
            if sum(c) == x:
                return False
    return True


def is_legit(x):
    """
    Finds all possible divisors of integer x,
    if total of all divisors > x and all the
    possible combinations of subsets != x
    then it's legit
    """
    s = divisors(x)
    return sum(s) > x and check_subsets(s, x)


if __name__ == "__main__":

    results = []

    for x in range(1, 554):
        if is_legit(x):
            results.append(x)

    # we should just have one spot
    assert len(results) == 1
    print("FOUND IT!", results[0])