Euler – Coder.si

Product-sum numbers

Problem 88

A natural number, N, that can be written as the sum and product of a given set of at least two natural numbers, {a₁, a₂, ... , a_k} is called a product-sum number: N = a₁ + a₂ + ... + a_k = a₁ × a₂ × ... × a_k.

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.

In fact, as the complete set of minimal product-sum numbers for 2≤k≤12 is {4, 6, 8, 12, 15, 16}, the sum is 61.

What is the sum of all the minimal product-sum numbers for 2≤k≤12000?

cache = []


def recurse(limit, p, s, n, start):
    k = n + p - s
    if k > limit:
        return
    if p < cache[k]:
        cache[k] = p
    for x in range(start, 2 * limit // p + 1):
        recurse(limit, p * x, s + x, n + 1, x)


def run(limit=12000):
    global cache
    cache = cache + ([3 * limit] * (limit + 1))
    recurse(limit, 1, 0, 0, 2)
    return sum(set(cache[2:]))


#### Slow
from math import log, ceil


def run_long(limit=12000):
    max_len = ceil(log(limit, 2))

    best = {}
    queue = [([k], k, k, 1) for k in range(2, limit)]
    while queue:
        l, p, s, length = queue.pop(0)
        if p > 2 * limit:
            continue
        q = p - s + length
        if q > limit:
            continue
        if q not in best:
            best[q] = p
        if p < best[q]:
            best[q] = p
        if len(l) == max_len:
            continue
        for i in range(l[-1], 2 * limit // p):
            queue.append((l + [i], p * i, s + i, length + 1))

    return sum(set(best.values())) - 2