notes.html

problem 88 · 70 lines

<article>
<h3>Problem Analysis</h3>
<p>
    A product-sum number for a set of size <code>k</code> is a natural number <code>N</code> that can be expressed
    simultaneously as the product and the sum of a multiset of <code>k</code> natural numbers. I must find, for every
    <code>k</code> from 2 to 12000, the smallest such <code>N</code> - its minimal product-sum number - and then sum
    the distinct values found (the example reminds us that 8 serves several values of <code>k</code> but counts once).
    The naive reading of the problem - search over all multisets of size <code>k</code> - is hopeless, since the count
    of multisets grows exponentially in <code>k</code>. The whole problem turns on a single algebraic observation about
    the behaviour of the number 1.
  </p>
<p>
    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 <code>P</code> and sum <code>S</code>,
    where <code>P ≥ S</code>, I can append exactly <code>P - S</code> ones. The product stays <code>P</code>, the
    sum rises to <code>S + (P - S) = P</code>, and the two now agree. The padded set has size
    <code>k = m + (P - S)</code>, where <code>m</code> is the number of real factors. This means I never enumerate the
    ones at all: every <a class="reference-source" href="https://en.wikipedia.org/wiki/Integer_factorization" rel="noopener noreferrer" target="_blank">integer factorization</a>
    into factors ≥ 2 implicitly defines one candidate <code>(k, N)</code> pair. The search collapses from "all
    multisets" to "all factorizations," which is dramatically smaller. A second observation bounds the search: for any
    <code>k</code>, the set <code>{2, k, 1, 1, ..., 1}</code> (with <code>k - 2</code> ones) has product <code>2k</code>
    and sum <code>2 + k + (k - 2) = 2k</code>, so it is always valid. Hence the minimal <code>N</code> for any
    <code>k</code> never exceeds <code>2k</code>. That caps every value at <code>2 · max_k</code>, gives the
    answer table a safe default, and drives a
    <a class="reference-source" href="https://en.wikipedia.org/wiki/Branch_and_bound" rel="noopener noreferrer" target="_blank">branch-and-bound</a>
    pruning rule that keeps the work close to linear in <code>max_k</code>.
  </p>
<h3>Solution Approach</h3>
<h4>Recursive Factorization Search</h4>
<p>
    Both files implement the same algorithm, so I describe it once and note the language differences afterward. I keep
    a table <code>min_prod[k]</code> initialised to <code>2 * max_k</code> - the universal upper bound - for every
    <code>k</code>. The
    <a class="reference-source" href="https://en.wikipedia.org/wiki/Recursion_(computer_science)" rel="noopener noreferrer" target="_blank">recursive</a>
    routine <code>find_product_sum(prod, total, count, start)</code> represents the state of having chosen
    <code>count</code> factors so far with running product <code>prod</code> and running sum <code>total</code>;
    <code>start</code> is the smallest value the next factor may take.
  </p>
<p>
    At each call I compute <code>k = prod - total + count</code>. Here <code>prod - total</code> is the number of ones
    needed to make the sum equal the product, and <code>count</code> is the number of factors already chosen, so
    <code>k</code> is exactly the implied set size from the padding identity. If <code>k</code> is within range I relax
    the table with <code>min_prod[k] = min(min_prod[k], prod)</code>. I then extend the factorization by iterating the
    next factor <code>i</code> from <code>start</code> upward, recursing with updated product, sum, and count, and
    passing <code>i</code> as the new <code>start</code> so factors stay non-decreasing.
  </p>
<p>
    The loop upper limit is <code>max_k // prod * 2 + 1</code>. If <code>prod * i</code> exceeded
    <code>2 * max_k</code>, the resulting <code>N</code> would beat our bound for every <code>k</code>, so there is no
    reason to continue. Because this limit is recomputed at each level using the current <code>prod</code>, it tightens
    as the product grows, cutting branches more aggressively the deeper the recursion descends.
  </p>
<p>
    The initial call is <code>find_product_sum(1, 1, 1, min_k)</code>. 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
    <code>count</code> becomes 2 - but the count-1 seed cancels correctly in the <code>k</code> formula so single
    real-factor cases score properly. Setting <code>start = min_k</code> (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.
  </p>
<p>
    After the search I sum the distinct table entries. The Python version uses the concise
    <code>sum(set(min_prod[2:]))</code>. The C version, lacking a built-in set, allocates a <code>char</code> array of
    size <code>2 * max_k + 1</code> 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, <code>g_max_k</code> and
    <code>g_min_prod</code>, 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 (<code>max_k = 12000</code>)
    the C build runs in about 0.0011 s versus 0.0556 s for Python, roughly a 50x gap.
  </p>
</article>