Problem Analysis
A product-sum number for a set of size k is a natural number N that can be expressed
simultaneously as the product and the sum of a multiset of k natural numbers. I must find, for every
k from 2 to 12000, the smallest such N - its minimal product-sum number - and then sum
the distinct values found (the example reminds us that 8 serves several values of k but counts once).
The naive reading of the problem - search over all multisets of size k - is hopeless, since the count
of multisets grows exponentially in k. The whole problem turns on a single algebraic observation about
the behaviour of the number 1.
The number 1 is the multiplicative identity: multiplying by 1 leaves a product unchanged but adding 1 raises a sum
by 1. So given any multiset of "real" factors (each at least 2) with product P and sum S,
where P ≥ S, I can append exactly P - S ones. The product stays P, the
sum rises to S + (P - S) = P, and the two now agree. The padded set has size
k = m + (P - S), where m is the number of real factors. This means I never enumerate the
ones at all: every integer factorization
into factors ≥ 2 implicitly defines one candidate (k, N) pair. The search collapses from "all
multisets" to "all factorizations," which is dramatically smaller. A second observation bounds the search: for any
k, the set {2, k, 1, 1, ..., 1} (with k - 2 ones) has product 2k
and sum 2 + k + (k - 2) = 2k, so it is always valid. Hence the minimal N for any
k never exceeds 2k. That caps every value at 2 · max_k, gives the
answer table a safe default, and drives a
branch-and-bound
pruning rule that keeps the work close to linear in max_k.
Solution Approach
Recursive Factorization Search
Both files implement the same algorithm, so I describe it once and note the language differences afterward. I keep
a table min_prod[k] initialised to 2 * max_k - the universal upper bound - for every
k. The
recursive
routine find_product_sum(prod, total, count, start) represents the state of having chosen
count factors so far with running product prod and running sum total;
start is the smallest value the next factor may take.
At each call I compute k = prod - total + count. Here prod - total is the number of ones
needed to make the sum equal the product, and count is the number of factors already chosen, so
k is exactly the implied set size from the padding identity. If k is within range I relax
the table with min_prod[k] = min(min_prod[k], prod). I then extend the factorization by iterating the
next factor i from start upward, recursing with updated product, sum, and count, and
passing i as the new start so factors stay non-decreasing.
The loop upper limit is max_k // prod * 2 + 1. If prod * i exceeded
2 * max_k, the resulting N would beat our bound for every k, so there is no
reason to continue. Because this limit is recomputed at each level using the current prod, it tightens
as the product grows, cutting branches more aggressively the deeper the recursion descends.
The initial call is find_product_sum(1, 1, 1, min_k). Starting product and sum at 1 with count 1 is a
bookkeeping seed: when the first real factor (say 2) is chosen, the product becomes 2, the sum becomes 3, and
count becomes 2 - but the count-1 seed cancels correctly in the k formula so single
real-factor cases score properly. Setting start = min_k (which is 2) guarantees every chosen factor is
at least 2, so I explore only genuine factorizations and never spuriously include a 1 as a "real" factor.
After the search I sum the distinct table entries. The Python version uses the concise
sum(set(min_prod[2:])). The C version, lacking a built-in set, allocates a char array of
size 2 * max_k + 1 indexed by value, marks each value as seen on first encounter, and accumulates only
unseen values - an O(N) deduplication. The C code also uses two file-scope globals, g_max_k and
g_min_prod, to avoid threading shared state through every recursive call, whereas Python defines the
helper as a nested function that closes over the enclosing variables. On the main case (max_k = 12000)
the C build runs in about 0.0011 s versus 0.0556 s for Python, roughly a 50x gap.