A product-sum number is a natural number N which can be expressed as both the product and the sum of the same set of numbers.

N = a1 × a2 × ... × ak = a1 + a2 + ... + ak

For example, 6 = 1 × 2 × 3 = 1 + 2 + 3.

For a given set of size, k, we shall call the smallest N with this property a minimal product-sum number. The minimal product-sum numbers for sets of size, k = 2, 3, 4, 5, and 6 are as follows.
```
k=2: 4 = 2 × 2 = 2 + 2
k=3: 6 = 1 × 2 × 3 = 1 + 2 + 3
k=4: 8 = 1 × 1 × 2 × 4 = 1 + 1 + 2 + 4
k=5: 8 = 1 × 1 × 2 × 2 × 2 = 1 + 1 + 2 + 2 + 2
k=6: 12 = 1 × 1 × 1 × 1 × 2 × 6 = 1 + 1 + 1 + 1 + 2 + 6
```

Hence for 2 ≤ k ≤ 6, the sum of all the minimal product-sum numbers is 4+6+8+12 = 30; note that 8 is only counted once in the sum.

Your task is to write an algorithm to compute the sum of all minimal product-sum numbers where 2 ≤ k ≤ n.

Courtesy of ProjectEuler.net

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

def _disabled_input(*args, **kwargs):
    raise RuntimeError("input() is disabled in callable mode")
builtins.input = _disabled_input

ns = {"__name__": "__judge__"}  # prevent if __name__ == "__main__" blocks
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "from functools import reduce\nfrom itertools import combinations_with_replacement \n\n''' Naive implementation of combinations built incrementaly doesn't work (for k = 3, there's no 1,2,3): \nn = 5\nfor k in range(1,n):\n    k_uplet_init = [1 for item in range(k)]\n    print(k_uplet_init)\n    for i in range(1,2*n):\n        k_uplet_init[k_uplet_init.index(min(k_uplet_init))] += 1\n        print(k_uplet_init)\n'''\n    \n    \n'''    \ndef productsum(n):\n    result = []\n    collections = [(2,2)]\n    \n    #setting up the various digits needed\n    nums = []\n    for i in range(3,n+3):\n        nums.append([item for item in range(1,i)])\n    \n    print('nums are {0}'.format(nums))\n    #initiate k\n    for k in range(2,n+1):\n        print('k = {0}'.format(k))\n        #loops through digits to use in nums\n        for digits in nums:\n            print('digits = {0}'.format(digits))\n            \n            combi = [uplets for uplets in list(combinations_with_replacement(digits, k))]\n            print('k combination of digits is {0}'.format(combi))\n            for item in combi:\n                print('n_uplet is {0}'.format(item))\n                sums = sum(item)\n                print('sum = {0}'.format(sums))\n                prods = reduce(lambda x,y: x*y,item)\n                print('prod = {0}\\n'.format(prods))\n                if sums == prods:\n                    if item not in collections:\n                        if len(item) == len(collections[-1]):\n                            if sum(item) < sum(collections[-1]):\n                                print('appending item {0}'.format(item))\n                                collections[-1] = item\n                                print('collection is now {0}\\n'.format(collections))\n                        else:\n                            print('appending item {0}'.format(item))\n                            collections.append(item)\n                            print('collection is now {0}\\n'.format(collections))\n                    break\n          \n    #collections = collections[1:]\n    \n    for item in collections:\n        if sum(item) not in collections:\n            result.append(sum(item))\n    \n    result = list(set(result))\n    \n    return sum(result)\n'''\n'''\ndef productsum(n):\n    result = []\n    collections = [(2,2)]\n    \n    #setting up the various digits needed\n    nums = []\n    for i in range(3,n+3):\n        nums.append([item for item in range(1,i)])\n    \n    #initiate k\n    for k in range(2,n+1):\n        #loops through digits to use in nums\n        for digits in nums:\n            combi = [uplets for uplets in list(combinations_with_replacement(digits, k))]\n            for item in combi:\n                sums = sum(item)\n                prods = reduce(lambda x,y: x*y,item)\n                if sums == prods:\n                    if item not in collections:\n                        if len(item) == len(collections[-1]):\n                            if sum(item) < sum(collections[-1]):\n                                collections[-1] = item\n                        else:\n                            collections.append(item)\n                    break\n          \n    for item in collections:\n        if sum(item) not in collections:\n            result.append(sum(item))\n    \n    print('collection is  {0}\\n'.format(collections))\n    print('result is  {0}\\n'.format(result))\n    result = list(set(result))\n    print('final result (sum) is  {0}\\n'.format(sum(result)))\n    return sum(result)\n    '''\n\n'''\ndef productsum(n):\n    result = []\n    collections = [(2,2)]\n    sums = []\n    \n    #setting up the various digits needed\n    nums = []\n    for i in range(3,n+3):\n        nums.append([item for item in range(1,i)])\n    \n    #initiate k\n    for k in range(2,n+1):\n        #loops through digits to use in nums\n        #print('k = {0}'.format(k))\n        for digits in range(k):\n            #print('digits = {0}'.format(nums[digits]))\n            combi = [uplets for uplets in list(combinations_with_replacement(nums[digits], k)) if sum(uplets) == reduce(lambda x,y: x*y,uplets)]\n            #print('combinations valid are: {0}'.format(combi))\n            if len(combi) > 0:\n                combi_sum = [sum(items) for items in combi]\n                collections.append(combi[combi_sum.index(min(combi_sum))])\n                break\n    for item in collections:\n        if sum(item) not in collections:\n            result.append(sum(item))\n    #print('collection is  {0}\\n'.format(collections))\n    #print('result is  {0}\\n'.format(result))\n    result = list(set(result))\n    #print('final result (sum) is  {0}\\n'.format(sum(result)))\n    return sum(result)\n'''\n\n'''\ndef productsum(n):\n\n    n_uplets = [()]\n    result = []\n    nums = []\n    for i in range(3,n+3):\n        nums.append([item for item in range(1,i)])\n    print(nums)\n    counter = 1\n    while len(n_uplets) < n+1:\n        for digits in nums:\n            combi = [uplets for uplets in list(combinations_with_replacement(digits, counter))]\n            #print('combi is {0}'.format(combi))\n            for combis in combi:\n                #sums = sum(combis)\n                prods = reduce(lambda x,y: x*y,combis)\n                if sum(combis) == prods:\n                    if len(n_uplets[-1]) == len(combis):\n                        if sum(combis) < sum(n_uplets[-1]):\n                            n_uplets[-1] = combis\n                    else:\n                        n_uplets.append(combis)\n\n            #print('n_uplets = {0}'.format(n_uplets))\n            counter +=1\n    n_uplets = n_uplets[2:]\n    print('final n_uplets are {0}'.format(n_uplets))\n\n    result = [sum(el) for el in n_uplets]\n    result = list(set(result))\n\n    return sum(result)\n'''\n\nfrom functools import reduce\nfrom itertools import combinations_with_replacement \n\n''' Naive implementation of combinations built incrementaly doesn't work (for k = 3, there's no 1,2,3): \nn = 5\nfor k in range(1,n):\n    k_uplet_init = [1 for item in range(k)]\n    print(k_uplet_init)\n    for i in range(1,2*n):\n        k_uplet_init[k_uplet_init.index(min(k_uplet_init))] += 1\n        print(k_uplet_init)\n'''\n    \n    \n'''    \ndef productsum(n):\n    result = []\n    collections = [(2,2)]\n    \n    #setting up the various digits needed\n    nums = []\n    for i in range(3,n+3):\n        nums.append([item for item in range(1,i)])\n    \n    print('nums are {0}'.format(nums))\n    #initiate k\n    for k in range(2,n+1):\n        print('k = {0}'.format(k))\n        #loops through digits to use in nums\n        for digits in nums:\n            print('digits = {0}'.format(digits))\n            \n            combi = [uplets for uplets in list(combinations_with_replacement(digits, k))]\n            print('k combination of digits is {0}'.format(combi))\n            for item in combi:\n                print('n_uplet is {0}'.format(item))\n                sums = sum(item)\n                print('sum = {0}'.format(sums))\n                prods = reduce(lambda x,y: x*y,item)\n                print('prod = {0}\\n'.format(prods))\n                if sums == prods:\n                    if item not in collections:\n                        if len(item) == len(collections[-1]):\n                            if sum(item) < sum(collections[-1]):\n                                print('appending item {0}'.format(item))\n                                collections[-1] = item\n                                print('collection is now {0}\\n'.format(collections))\n                        else:\n                            print('appending item {0}'.format(item))\n                            collections.append(item)\n                            print('collection is now {0}\\n'.format(collections))\n                    break\n          \n    #collections = collections[1:]\n    \n    for item in collections:\n        if sum(item) not in collections:\n            result.append(sum(item))\n    \n    result = list(set(result))\n    \n    return sum(result)\n'''\n'''\ndef productsum(n):\n    result = []\n    collections = [(2,2)]\n    \n    #setting up the various digits needed\n    nums = []\n    for i in range(3,n+3):\n        nums.append([item for item in range(1,i)])\n    \n    #initiate k\n    for k in range(2,n+1):\n        #loops through digits to use in nums\n        for digits in nums:\n            combi = [uplets for uplets in list(combinations_with_replacement(digits, k))]\n            for item in combi:\n                sums = sum(item)\n                prods = reduce(lambda x,y: x*y,item)\n                if sums == prods:\n                    if item not in collections:\n                        if len(item) == len(collections[-1]):\n                            if sum(item) < sum(collections[-1]):\n                                collections[-1] = item\n                        else:\n                            collections.append(item)\n                    break\n          \n    for item in collections:\n        if sum(item) not in collections:\n            result.append(sum(item))\n    \n    print('collection is  {0}\\n'.format(collections))\n    print('result is  {0}\\n'.format(result))\n    result = list(set(result))\n    print('final result (sum) is  {0}\\n'.format(sum(result)))\n    return sum(result)\n    '''\n\n'''\ndef productsum(n):\n    result = []\n    collections = [(2,2)]\n    sums = []\n    \n    #setting up the various digits needed\n    nums = []\n    for i in range(3,n+3):\n        nums.append([item for item in range(1,i)])\n    \n    #initiate k\n    for k in range(2,n+1):\n        #loops through digits to use in nums\n        #print('k = {0}'.format(k))\n        for digits in range(k):\n            #print('digits = {0}'.format(nums[digits]))\n            combi = [uplets for uplets in list(combinations_with_replacement(nums[digits], k)) if sum(uplets) == reduce(lambda x,y: x*y,uplets)]\n            #print('combinations valid are: {0}'.format(combi))\n            if len(combi) > 0:\n                combi_sum = [sum(items) for items in combi]\n                collections.append(combi[combi_sum.index(min(combi_sum))])\n                break\n    for item in collections:\n        if sum(item) not in collections:\n            result.append(sum(item))\n    #print('collection is  {0}\\n'.format(collections))\n    #print('result is  {0}\\n'.format(result))\n    result = list(set(result))\n    #print('final result (sum) is  {0}\\n'.format(sum(result)))\n    return sum(result)\n'''\n\n'''\ndef productsum(n):\n\n    n_uplets = [()]\n    result = []\n    nums = []\n    for i in range(3,n+3):\n        nums.append([item for item in range(1,i)])\n    print(nums)\n    counter = 1\n    while len(n_uplets) < n+1:\n        for digits in nums:\n            combi = [uplets for uplets in list(combinations_with_replacement(digits, counter))]\n            #print('combi is {0}'.format(combi))\n            for combis in combi:\n                #sums = sum(combis)\n                prods = reduce(lambda x,y: x*y,combis)\n                if sum(combis) == prods:\n                    if len(n_uplets[-1]) == len(combis):\n                        if sum(combis) < sum(n_uplets[-1]):\n                            n_uplets[-1] = combis\n                    else:\n                        n_uplets.append(combis)\n\n            #print('n_uplets = {0}'.format(n_uplets))\n            counter +=1\n    n_uplets = n_uplets[2:]\n    print('final n_uplets are {0}'.format(n_uplets))\n\n    result = [sum(el) for el in n_uplets]\n    result = list(set(result))\n\n    return sum(result)\n'''\n\n'''\ndef productsum(n):\n    print('n = {0}'.format(n))\n    n_uplets = []\n    result = []\n    nums = []\n    not_min = []\n    for i in range(3,n+3):\n        nums.append([item for item in range(1,i)])\n    nums = nums[-2:]\n    #print('nums = {0}'.format(nums))\n    counter = 2\n    for digits in nums:\n        if len(n_uplets) <= n:          \n            #print('\\ndigits = {0}'.format(digits))\n            combi = [uplets for uplets in list(combinations_with_replacement(digits, counter))]\n            #print('combi is {0}\\n'.format(combi))\n            for combis in combi:\n                prods = reduce(lambda x,y: x*y,combis)\n                x = prods - sum(combis)\n                solution = tuple(1 for item in range(1,x+1))\n\n                z = combis + solution\n                z = sorted(z)\n                z = tuple(z)\n                if sum(z) == prods and len(z) <= n:\n                    #print('z is {0}'.format(z))\n                    if tuple(z) not in n_uplets :\n                        y = [len(member) for member in n_uplets]\n                        if len(z) in y and sum(z) < sum(n_uplets[y.index(len(z))]):\n                            not_min.append(n_uplets[y.index(len(z))])\n                            if z not in not_min:\n                                n_uplets[y.index(len(z))] = z\n                                #print('replacing uplets with z = {0}'.format(z))\n                            #print('z IGNORED {0}'.format(z))\n                        else:\n                            if z not in not_min and len(z) not in y:\n                                n_uplets.append(z)\n                                #print('adding uplets z = {0}'.format(z))\n                            \n                        #print('n_uplets is now {0}'.format(n_uplets))\n            counter +=1\n            \n    print('final n_uplets are {0}'.format(n_uplets))\n    print('not_minimums are {0}'.format(not_min))\n    result = [sum(el) for el in n_uplets]\n    result = list(set(result))\n    print('result before sum is {0}'.format(result))\n    return sum(result)\n\n'''\ndef productsum(n):\n    if n < 12:\n        kmax = n+1\n    else:\n        kmax = n\n    \n    def prodsum(p, s, nf, start):\n        k = p - s + nf     # product - sum + number of factors\n        if k < kmax:\n            if p < n[k]:\n                n[k] = p\n            for i in range(start, kmax//p*2 + 1):\n                prodsum(p*i, s+i, nf+1, i)\n    if kmax > 12: kmax +=1\n    n = [2*kmax] * kmax\n    \n    prodsum(1, 1, 1, 2)\n    \n    return sum(set(n[2:]))\n\n"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

_target = None
_fn_name = 'productsum'
if _fn_name:
    if "Solution" in ns:
        try:
            _obj = ns["Solution"]()
            if hasattr(_obj, _fn_name):
                _target = getattr(_obj, _fn_name)
        except Exception:
            _target = None
    if _target is None and _fn_name in ns and callable(ns[_fn_name]):
        _target = ns[_fn_name]
# Fallback: if there's exactly one user-defined function, use it
if _target is None:
    _cands = [v for k, v in ns.items() if callable(v) and getattr(v, "__module__", "") in ("__judge__", "__main__")]
    _user_funcs = [c for c in _cands if getattr(c, "__name__", "").startswith("_") is False]
    if len(_user_funcs) == 1:
        _target = _user_funcs[0]
if _target is None:
    raise RuntimeError(f"Could not resolve callable '{_fn_name}'")

_raw = sys.stdin.read().strip()
if _raw:
    _parsed = json.loads(_raw)
    if isinstance(_parsed, dict):
        _kwargs = _parsed.get("kwargs", {})
        _args = _parsed.get("args", [])
    else:
        _args, _kwargs = _parsed, {}
else:
    _args, _kwargs = [], {}
if not isinstance(_args, (list, tuple)):
    _args = [_args]
_res = _target(*_args, **_kwargs)
try:
    sys.stdout.write(repr(_res) + "\n")
except Exception:
    pass

```

Measured memory_bytes: 6690