OMFG! Yes, I finally finished this one! I’ve been working on this problem off and on for about 8 years and I finally got it! I think what finally did it is a better understanding of how to create integer partitions. I’d developed a really stellar algorithm to do so for a previous problem and just went from that point for this one.
My solution uses recursion. Python’s recursion limit is 1000 and since 12000 is much larger than that, I had to set the recursion limit much higher to account. However, I wasn’t able to run the code in pypy3. I kept giving me segmentation faults and I suspect it has to do with the amount of recursion happening. Would have been much faster running it in pypy3, but alas, this runs in about 8 minutes on python3.
def solve(n):
def partition(start, end, summ, prod, count):
k = start
while k > end:
s, p = summ + k, prod * k
if s == p and count > 1:
if s < minimals[count]:
minimals[count] = s
elif count < n and s >= p:
st = start
if p > 1:
st = s // (p - 1)
partition(st, k - 1, s, p, count + 1)
k -= 1
minimals = {i: float('inf') for i in range(2, n+1)}
partition(n, 0, 0, 1, 1)
return sum(set(minimals.values()))
if __name__ == '__main__':
import sys
n = int(sys.argv[1])
sys.setrecursionlimit(n * 2)
print(solve(n))