Another variant of the previous two problems, but the trick is knowing that partition theory is related to generalised pentagonal number generation. So I just found a generator and modified it for my needs.

#Euler78 class Algorithms: def pentGen(self, num): pentagonal = lambda n : n*(3*n-1)/2 def generalised_pentagonal(n): if n < 0: return 0 if n % 2 == 0: return pentagonal(n/2+1) else: return pentagonal(-(n/2+1)) pt = [1] for n in range (1, num+1): r = 0 f = -1 i = 0 while 1: k = generalised_pentagonal(i) if k > n: break if i % 2 == 0: f = -f r += f*pt[n - k] i += 1 pt.append(r) if r % 1000000 == 0: return n if n % 10000 == 0: print n class Problem78: def __init__(self, stop): self.stop = stop self.Euler = Algorithms() def Solution(self): n = self.Euler.pentGen(self.stop) return "Answer = " + str(n) if __name__ == '__main__': P = Problem78(60000) print P.Solution()