Detailed mathematical approach

Problem Summary

For \(k \ge 2\), a product-sum number is a positive integer \(N\) that can be written both as the sum and as the product of the same multiset of \(k\) positive integers:

$N=a_1+a_2+\cdots+a_k=a_1a_2\cdots a_k,\qquad a_i\ge 1.$

Let \(M(k)\) denote the smallest such \(N\). The task is to compute the sum of all distinct values among \(M(2),M(3),\dots,M(12000)\). A naive search over all \(k\)-tuples is hopelessly redundant, because most entries are 1 and do not change the product. The implementations therefore search only over the factors greater than 1 and recover the correct set size from them.

Mathematical Approach

Write \(K=12000\). The core idea is that once the nontrivial factors are fixed, the number of required 1s is forced, so the problem becomes a search over multiplicative factorizations rather than over arbitrary additive decompositions.

Removing the Ones

Choose nondecreasing factors \(f_1\le f_2\le \cdots \le f_m\) with each \(f_i\ge 2\). Define

$P=\prod_{i=1}^{m} f_i,\qquad S=\sum_{i=1}^{m} f_i.$

If we append exactly \(P-S\) ones, then the product stays \(P\), while the sum becomes

$S+(P-S)=P.$

So the resulting product-sum representation has size

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

Conversely, every product-sum representation can be reduced to this form by deleting all the 1s. This gives the fundamental invariant used by the code: every multiset of factors at least 2 determines exactly one candidate pair \((k,P)\). The one-factor case always gives \(k=1\), so the interesting range starts as soon as at least two nontrivial factors have been chosen.

One Product Can Serve Several Values of \(k\)

The same integer can arise from different multiplicative partitions, and those partitions can lead to different set sizes. For example,

$12=2\cdot 6 \qquad\Longrightarrow\qquad k=12-(2+6)+2=6,$

so one valid representation is

$12=1+1+1+1+2+6=1\cdot 1\cdot 1\cdot 1\cdot 2\cdot 6.$

But the factorization

$12=2\cdot 2\cdot 3 \qquad\Longrightarrow\qquad k=12-(2+2+3)+3=8,$

gives another valid identity:

$12=1+1+1+1+1+2+2+3=1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 2\cdot 2\cdot 3.$

This is why the algorithm does not solve each \(k\) independently. It traverses all admissible factorizations and updates the best known product for every \(k\) that appears.

The Universal Bound \(M(k)\le 2k\)

A simple construction gives a global search bound. For any \(k\ge 2\), take the multiset consisting of \(k-2\) ones together with 2 and \(k\). Its sum and product are both \(2k\):

$2k=\underbrace{1+\cdots+1}_{k-2\text{ terms}}+2+k=\underbrace{1\cdots 1}_{k-2\text{ terms}}\cdot 2\cdot k.$

Therefore

$M(k)\le 2k.$

For the full problem, \(k\le K=12000\), so every minimal product-sum number is at most \(2K=24000\). Any recursive branch whose current product already exceeds \(24000\) can never contribute to the answer and may be discarded immediately.

DFS State, Recurrence, and Pruning

The implementations build factorizations directly by depth-first search. A search state consists of

$\bigl(P,S,m,a\bigr),$

where \(P\) is the current product, \(S\) is the current sum, \(m\) is the number of chosen factors, and \(a\) is the smallest value allowed for the next factor. From this state, every legal extension chooses \(x\ge a\) with \(Px\le 2K\) and moves to

$\bigl(Px,\ S+x,\ m+1,\ x\bigr).$

Passing \(x\) forward as the new lower bound forces the factor sequence to stay nondecreasing, so each unordered factor multiset is generated exactly once. At every visited node, the induced set size is

$k=P-S+m.$

If \(2\le k\le K\), the current product \(P\) is a valid candidate for \(M(k)\), and the stored minimum for that \(k\) is updated if necessary.

The same formula also justifies pruning. After appending a factor \(x\ge 2\), the new value of \(k\) is

$k'=Px-(S+x)+(m+1)=k+(x-1)(P-1)\ge k.$

So \(k\) never decreases as the recursion goes deeper. Once a state has \(k>K\), every descendant also has \(k>K\), and the whole subtree can be skipped safely. The recursion depth is small as well: since every chosen factor is at least 2 and the product never exceeds \(2K\), one always has \(m\le \lfloor\log_2(2K)\rfloor\).

Worked Example

Start from the empty state \((1,0,0,2)\) and follow the branch that chooses factors \(2,2,3\). The successive states are

$ (2,2,1,2),\qquad (4,4,2,2),\qquad (12,7,3,3). $

The corresponding values of \(k=P-S+m\) are \(1\), \(2\), and \(8\). The middle state gives

$4=2+2=2\cdot 2,$

so \(M(2)\le 4\). The last state gives \(k=12-7+3=8\), which means that five ones must be appended:

$12=1+1+1+1+1+2+2+3=1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 2\cdot 2\cdot 3.$

A different branch, namely \(2,6\), reaches the same product 12 but produces \(k=6\) instead. That single example illustrates both important phenomena: valid candidates arise at intermediate nodes of the search tree, and one product may belong to several different set sizes.

How the Code Works

Search Phase

The C++, Python, and Java implementations allocate an array indexed by \(k\), initially filled with a large sentinel value, to store the smallest product found so far for each \(2\le k\le K\). The search starts from the empty factorization with product 1, sum 0, zero chosen factors, and a minimum next factor of 2.

Each recursive call computes the current value \(k=P-S+m\). If that \(k\) lies in the target range, the implementation compares the current product \(P\) with the stored minimum and keeps the smaller one. It then tries every next factor \(x\) from the current lower bound upward until the product limit \(Px\le 2K\) would be violated. Because the next call uses \(x\) as the new lower bound, permutations such as \(2,3,2\) and \(3,2,2\) are never explored separately.

Deduplicating the Final Answer

After the DFS finishes, the implementations scan \(k=2,3,\dots,K\), insert the minimal products into a set, and sum the distinct set elements. This final deduplication step is essential because the same minimal product-sum number can serve more than one value of \(k\). For instance, small cases already show that one number may be minimal for several neighboring set sizes.

Complexity Analysis

Let \(T(K)\) be the number of nondecreasing factor tuples \((f_1,\dots,f_m)\) with all \(f_i\ge 2\) and product at most \(2K\). The DFS visits each such tuple once, so the enumeration phase runs in \(O(T(K))\) time. This is the right complexity measure for the method, because the algorithm literally walks the multiplicative-factor tree under the cutoff \(2K\).

The additional scan over \(k=2,\dots,K\) costs \(O(K)\). The recursion depth is at most \(\lfloor\log_2(2K)\rfloor\), and the auxiliary memory is \(O(K)\) for the best-value array and the final set of distinct minima, plus \(O(\log K)\) stack space. For \(K=12000\), the bound \(2K=24000\) keeps the search tree small enough for this direct DFS to be entirely practical.

Footnotes and References

1. Problem page: Project Euler 88 - Product-sum Numbers
2. Integer factorization: Wikipedia - Integer factorization
3. Depth-first search: Wikipedia - Depth-first search
4. Backtracking: Wikipedia - Backtracking
5. Multiset: Wikipedia - Multiset