Solution

Answer: 7587457

Let $N$ be represented by a multiset of $k$ natural numbers

$$a_1,a_2,\dots,a_k$$

such that

$$N=a_1+a_2+\cdots+a_k$$

and

$$N=a_1a_2\cdots a_k.$$

We want the minimal such $N$ for every $2\le k\le 12000$, then sum the distinct minima.

Mathematical analysis

The key observation is that the number $1$'s in the representation are flexible.

Suppose we take only factors $\ge 2$:

$$b_1,b_2,\dots,b_m.$$

Let

$$P=b_1b_2\cdots b_m, \qquad S=b_1+b_2+\cdots+b_m.$$

If we add $t$ copies of $1$, then:

product remains $P$,
sum becomes $S+t$,
total number of terms becomes $m+t$.

For this to be a product-sum representation, we need

$$P=S+t.$$

Thus

$$t=P-S.$$

Therefore the corresponding set size is

$$k=m+t =m+(P-S).$$

So every factorization of $P$ into integers $\ge2$ generates a product-sum number for

$$k=P-S+m.$$

This is the crucial formula.

Reformulating the problem

For every multiplicative partition

$$P=b_1b_2\cdots b_m,$$

define

$$k=P-\sum b_i + m.$$

Then $P$ is a candidate minimal product-sum number for this $k$.

We must compute

$$\min P$$

for every $2\le k\le12000$.

Bounding the search

A standard bound is:

$$N_{\min}(k)\le 2k.$$

Why?

Take:

$$2, k, 1,1,\dots,1$$

with $k-2$ ones.

Then

$$\text{product}=2k,$$

$$\text{sum}=2+k+(k-2)=2k.$$

So every minimal product-sum number is at most $2k$.

Hence for $k\le12000$,

$$N\le24000.$$

Thus we only need to enumerate multiplicative factorizations whose product does not exceed $24000$.

Efficient recursive generation

We recursively build factorizations in nondecreasing order to avoid duplicates.

Suppose at some stage we have:

current product $p$,
current sum $s$,
current number of factors $c$,
next factor at least $f$.

Then

$$k=p-s+c.$$

If $k\le12000$, update the best value for that $k$.

Then try multiplying by another factor $i\ge f$:

$$p' = pi, \qquad s' = s+i, \qquad c' = c+1.$$

Continue while $p'\le24000$.

This explores all multiplicative partitions exactly once.

Python implementation

LIMIT = 12000
MAX_N = 2 * LIMIT

# minimal product-sum number for each k
best = [10**9] * (LIMIT + 1)

def search(prod, summ, count, start):
    """
    Recursively generate multiplicative partitions.

    prod  = current product
    summ  = current sum of factors
    count = number of factors
    start = smallest next factor allowed
            (keeps factors nondecreasing)
    """

    # Corresponding k after padding with ones
    k = prod - summ + count

    if k <= LIMIT:
        if prod < best[k]:
            best[k] = prod

    # Try extending factorization
    for f in range(start, MAX_N // prod + 1):
        new_prod = prod * f

        if new_prod > MAX_N:
            break

        search(
            new_prod,
            summ + f,
            count + 1,
            f
        )

# Start recursion from empty factorization
search(1, 0, 0, 2)

# Collect distinct minimal product-sum numbers
answer = sum(set(best[2:]))

print(answer)

Code walkthrough

Initialization

LIMIT = 12000
MAX_N = 2 * LIMIT

We only care about $k\le12000$, and every minimal product-sum number is at most $2k$, so we search only up to $24000$.

best = [10**9] * (LIMIT + 1)

best[k] stores the smallest product-sum number found for that $k$.

Recursive search

def search(prod, summ, count, start):

The recursion represents a factorization currently containing count factors with:

product = prod
sum = summ

Compute the implied $k$

k = prod - summ + count

This comes directly from:

$$k = P - S + m.$$

Update minimum

if k <= LIMIT:
    if prod < best[k]:
        best[k] = prod

If this factorization yields a smaller product-sum number for that $k$, store it.

Extend the factorization

for f in range(start, MAX_N // prod + 1):

We only try factors at least start, ensuring nondecreasing order and preventing duplicates.

new_prod = prod * f

Build the next factorization state.

search(new_prod, summ + f, count + 1, f)

Recurse with:

updated product,
updated sum,
one additional factor,
next factor constrained to be at least f.

Verification on the small examples

For $2\le k\le6$, the algorithm finds:

$$4,6,8,8,12$$

Distinct values:

$${4,6,8,12}$$

whose sum is:

$$30.$$

Matches the statement.

For $2\le k\le12$, it finds:

$${4,6,8,12,15,16}$$

with sum:

$$61.$$

Again correct.

Final verification

Search bound $24000$ is mathematically justified.
Recursive enumeration covers every multiplicative partition exactly once.
Duplicate minimal values are removed with set(...).
Known sample totals $30$ and $61$ match perfectly.

Running the program gives:

$$7587457$$

Answer: 7587457

Project Euler Problem 88