Problem 88: Product-sum Numbers

Mathematical Analysis

Key Observation

Given a set of numbers with product $P$ and sum $S$ where $P \ge S$, we can always pad the set with $(P - S)$ ones to make the sum equal the product. The resulting set has size $k = (P - S) + (\text{number of non-one elements})$.

So for any factorization of $N$ into factors $f_1, f_2, \ldots, f_m$ (each $\ge 2$), the corresponding $k$ is:

because we add $N - \sum f_i$ ones, giving total count $m + (N - \sum f_i) = N - \sum f_i + m$.

Bounds

Upper bound on $N_k$: For any $k$, we can always use $\{2, k, 1, 1, \ldots, 1\}$ (with $k-2$ ones) giving product $= 2k$ and sum $= 2 + k + (k-2) = 2k$. So $N_k \le 2k$.

For $k \le 12000$, we have $N_k \le 24000$.

Lower bound: $N_k \ge k$ since the sum of $k$ numbers each $\ge 1$ is at least $k$.

Editorial

The important simplification is that the ones never need to be generated explicitly. Once a factorization into numbers at least 2 is fixed, the number of ones required is forced, so the corresponding set size is determined by

That means the search is really over multiplicative cores rather than over full product-sum sets. The implementation checks each candidate value $N$ up to the standard bound $2k_{\max}$, recursively enumerates its factorizations in nondecreasing order to avoid duplicates, and turns each factorization into the implied value of $k$. Whenever that $k$ is in range, we update the best known product-sum number for that set size. At the end we take the distinct minima and sum them.

Pseudocode

Create an array best where best[k] stores the smallest product-sum number found for that k.

For each candidate value N from 2 up to 2 x 12000:
    Recursively enumerate factorizations of N into nondecreasing factors at least 2

    For each complete factorization:
        compute the implied set size k using the product-sum formula
        if 2 <= k <= 12000 and N improves best[k], update best[k]

After all candidates have been processed:
    collect the distinct values among best[2] through best[12000]
    return their sum

Factorization Enumeration

We use a recursive approach: for each $N$, enumerate factorizations where factors are in non-decreasing order (to avoid duplicates). Start with the smallest factor $\ge 2$ and recurse on $N / f$.

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Complexity Analysis

• Time: $O(N_{\max} \cdot d(N))$ where $d(N)$ is the number of factorizations. In practice, very fast since most numbers have few factorizations.
• Space: $O(k_{\max})$ for storing the minimal value per $k$.

Answer

#include <bits/stdc++.h>
using namespace std;

const int KMAX = 12000;
int best[KMAX + 1];

// Enumerate factorizations of N.
// prod = current product so far, sum_f = sum of factors so far,
// count = number of factors so far, min_factor = minimum next factor.
// We are building factorizations of the target number N = prod * (remaining).
void factorize(int n, int prod, int sum_f, int count, int min_factor) {
    // n is the remaining part to factorize (prod * n = original N)
    // At any point, we can stop and use n as the last factor
    // Last factor is n itself (n >= min_factor is required)
    if (n >= min_factor) {
        int total_prod = prod * n;
        int total_sum = sum_f + n;
        int total_count = count + 1;
        if (total_count >= 2) {
            int k = total_prod - total_sum + total_count;
            if (k >= 2 && k <= KMAX) {
                if (total_prod < best[k]) {
                    best[k] = total_prod;
                }
            }
        }
    }

    // Try splitting n further: pick factor f from min_factor to sqrt(n)
    for (int f = min_factor; (long long)f * f <= n; f++) {
        if (n % f == 0) {
            factorize(n / f, prod * f, sum_f + f, count + 1, f);
        }
    }
}

int main() {
    fill(best, best + KMAX + 1, INT_MAX);

    // Upper bound: N_k <= 2k, so we check N up to 2 * KMAX
    for (int N = 2; N <= 2 * KMAX; N++) {
        factorize(N, 1, 0, 0, 2);
    }

    // Sum distinct minimal product-sum numbers
    set<int> distinct;
    for (int k = 2; k <= KMAX; k++) {
        distinct.insert(best[k]);
    }

    long long answer = 0;
    for (int v : distinct) answer += v;

    cout << answer << endl;
    return 0;
}

import sys

def solve():
    """
    Find sum of all minimal product-sum numbers for 2 <= k <= 12000.

    Key insight: For factorization N = f1 * f2 * ... * fm (fi >= 2),
    N is a product-sum number for k = N - sum(fi) + m
    (by padding with N - sum(fi) ones).

    Upper bound: N_k <= 2k (use {2, k, 1, 1, ..., 1}).
    """
    KMAX = 12000
    best = [float('inf')] * (KMAX + 1)

    def factorize(n, prod, sum_f, count, min_factor):
        """Enumerate factorizations of the original number (= prod * n)."""
        # Use n as the last factor
        if n >= min_factor:
            total_prod = prod * n
            total_sum = sum_f + n
            total_count = count + 1
            if total_count >= 2:
                k = total_prod - total_sum + total_count
                if 2 <= k <= KMAX:
                    if total_prod < best[k]:
                        best[k] = total_prod

        # Split n further
        f = min_factor
        while f * f <= n:
            if n % f == 0:
                factorize(n // f, prod * f, sum_f + f, count + 1, f)
            f += 1

    sys.setrecursionlimit(100000)

    for N in range(2, 2 * KMAX + 1):
        factorize(N, 1, 0, 0, 2)

    # Sum distinct minimal product-sum numbers
    distinct = set()
    for k in range(2, KMAX + 1):
        distinct.add(best[k])

    print(sum(distinct))

if __name__ == "__main__":
    solve()