from fractions import Fraction
from functools import lru_cache

C = 60

def parallel(a, b):
    return Fraction(a * b, a + b)


def series(a, b):
    return a + b
    

@lru_cache()
def caps(n):
    if n == 1:
        return set([C])

    cs = set()
    for size_a in range(1, (n // 2) + 1):
        size_b = n - size_a
        for a in caps(size_a):
            for b in caps(size_b):
                cs.add(a)
                cs.add(parallel(a, b))
                cs.add(series(a, b))
    return cs


def euler_155():
    assert len(caps(1)) == 1
    assert len(caps(2)) == 3
    assert len(caps(3)) == 7
    return len(caps(18))


if __name__ == "__main__":
    solution = euler_155()
    print("e155.py: " + str(solution))
    assert solution == 3857447