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.
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.
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.
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.
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.
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\).
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.
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.
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.
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.
Für \(k \ge 2\) ist eine Produktsummenzahl eine positive ganze Zahl \(N\), die sich zugleich als Summe und als Produkt derselben Multimenge aus \(k\) positiven Zahlen schreiben lässt:
$$N=a_1+a_2+\cdots+a_k=a_1a_2\cdots a_k,\qquad a_i\ge 1.$$
Sei \(M(k)\) die kleinste solche Zahl. Gesucht ist die Summe aller verschiedenen Werte unter \(M(2),M(3),\dots,M(12000)\). Eine naive Suche über alle \(k\)-Tupel wäre extrem verschwenderisch, weil die meisten Einträge nur Einsen sind und das Produkt nicht verändern. Deshalb durchsuchen die Implementierungen nur die Faktoren größer als 1 und rekonstruieren daraus die passende Größe \(k\).
Schreibe \(K=12000\). Der entscheidende Gedanke ist: Sobald die nichttrivialen Faktoren feststehen, ist auch die Anzahl der nötigen Einsen fest vorgegeben. Damit wird aus einem Problem über Summenzerlegungen ein Problem über multiplikative Faktorisierungen.
Wähle nicht abnehmende Faktoren \(f_1\le f_2\le \cdots \le f_m\) mit \(f_i\ge 2\). Setze
$$P=\prod_{i=1}^{m} f_i,\qquad S=\sum_{i=1}^{m} f_i.$$
Ergänzt man genau \(P-S\) Einsen, dann bleibt das Produkt gleich \(P\), während die Summe zu
$$S+(P-S)=P$$
wird. Die entstehende Produktsummendarstellung hat also die Größe
$$k=(P-S)+m=P-S+m.$$
Umgekehrt lässt sich jede Produktsummendarstellung durch Entfernen aller Einsen genau in diese Form überführen. Das ist die Grundinvariante des Codes: Jede Multimenge von Faktoren \(\ge 2\) bestimmt genau ein Kandidatenpaar \((k,P)\). Der Ein-Faktor-Fall liefert immer \(k=1\); interessant wird es also erst ab mindestens zwei nichttrivialen Faktoren.
Dieselbe Zahl kann aus verschiedenen multiplikativen Partitionen entstehen, und diese Partitionen können zu verschiedenen Mengenlängen führen. Zum Beispiel gilt
$$12=2\cdot 6 \qquad\Longrightarrow\qquad k=12-(2+6)+2=6,$$
also ist
$$12=1+1+1+1+2+6=1\cdot 1\cdot 1\cdot 1\cdot 2\cdot 6$$
eine gültige Darstellung. Aber auch
$$12=2\cdot 2\cdot 3 \qquad\Longrightarrow\qquad k=12-(2+2+3)+3=8$$
liefert eine gültige Identität:
$$12=1+1+1+1+1+2+2+3=1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 2\cdot 2\cdot 3.$$
Darum löst der Algorithmus die Werte \(k\) nicht einzeln. Er durchläuft alle zulässigen Faktorisierungen und aktualisiert für jedes auftretende \(k\) das bislang kleinste gefundene Produkt.
Eine einfache Konstruktion liefert eine globale Suchgrenze. Für jedes \(k\ge 2\) betrachte die Multimenge aus \(k-2\) Einsen sowie 2 und \(k\). Summe und Produkt sind beide gleich \(2k\):
$$2k=\underbrace{1+\cdots+1}_{k-2\text{ Terme}}+2+k=\underbrace{1\cdots 1}_{k-2\text{ Terme}}\cdot 2\cdot k.$$
Daraus folgt
$$M(k)\le 2k.$$
Für das Problem gilt \(k\le K=12000\), also liegt jede minimale Produktsummenzahl höchstens bei \(2K=24000\). Jeder Rekursionszweig, dessen aktuelles Produkt bereits größer als \(24000\) ist, kann niemals noch zur Lösung beitragen und darf sofort verworfen werden.
Die Implementierungen bauen die Faktorisierungen direkt per Tiefensuche auf. Ein Zustand besteht aus
$$\bigl(P,S,m,a\bigr),$$
wobei \(P\) das aktuelle Produkt, \(S\) die aktuelle Summe, \(m\) die Zahl der gewählten Faktoren und \(a\) die kleinste erlaubte nächste Faktorgröße ist. Von diesem Zustand aus wird jeder legale Nachfolger durch Wahl eines \(x\ge a\) mit \(Px\le 2K\) erzeugt:
$$\bigl(Px,\ S+x,\ m+1,\ x\bigr).$$
Dass \(x\) als neue Untergrenze weitergereicht wird, erzwingt eine nicht abnehmende Faktorfolge. Dadurch wird jede ungeordnete Faktormultimenge genau einmal erzeugt. In jedem besuchten Knoten lautet die zugehörige Mengenlänge
$$k=P-S+m.$$
Liegt \(2\le k\le K\), dann ist das aktuelle Produkt \(P\) ein gültiger Kandidat für \(M(k)\), und das gespeicherte Minimum wird gegebenenfalls verbessert.
Dieselbe Formel erklärt auch das Abschneiden der Rekursion. Fügt man einen Faktor \(x\ge 2\) an, so erhält man
$$k'=Px-(S+x)+(m+1)=k+(x-1)(P-1)\ge k.$$
Der Wert \(k\) kann in tieferen Ebenen also nie kleiner werden. Sobald in einem Zustand \(k>K\) gilt, erfüllen alle Nachfahren ebenfalls \(k>K\), und der gesamte Teilbaum kann sicher übersprungen werden. Auch die Rekursionstiefe bleibt klein: Weil jeder gewählte Faktor mindestens 2 ist und das Produkt nie über \(2K\) steigt, gilt stets \(m\le \lfloor\log_2(2K)\rfloor\).
Starte im leeren Zustand \((1,0,0,2)\) und verfolge den Zweig mit den Faktoren \(2,2,3\). Die aufeinanderfolgenden Zustände sind
$$ (2,2,1,2),\qquad (4,4,2,2),\qquad (12,7,3,3). $$
Die zugehörigen Werte von \(k=P-S+m\) sind \(1\), \(2\) und \(8\). Der mittlere Zustand liefert
$$4=2+2=2\cdot 2,$$
also insbesondere \(M(2)\le 4\). Der letzte Zustand ergibt \(k=12-7+3=8\), also müssen fünf Einsen ergänzt werden:
$$12=1+1+1+1+1+2+2+3=1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 2\cdot 2\cdot 3.$$
Ein anderer Zweig, nämlich \(2,6\), erreicht dasselbe Produkt 12, aber mit \(k=6\). Dieses eine Beispiel zeigt beide zentralen Effekte: Gültige Kandidaten entstehen bereits an inneren Knoten des Suchbaums, und dasselbe Produkt kann zu mehreren verschiedenen Mengenlängen gehören.
Die C++-, Python- und Java-Implementierungen reservieren ein Array über den \(k\)-Werten, das anfangs mit einem großen Platzhalterwert gefüllt ist und für jedes \(2\le k\le K\) das kleinste bisher gefundene Produkt speichert. Die Suche beginnt mit der leeren Faktorisierung: Produkt 1, Summe 0, keine gewählten Faktoren und 2 als kleinster erlaubter nächster Faktor.
Jeder Rekursionsaufruf berechnet zunächst den aktuellen Wert \(k=P-S+m\). Liegt dieser im Zielbereich, wird das momentane Produkt \(P\) mit dem gespeicherten Minimum verglichen. Anschließend probiert die Implementierung jeden nächsten Faktor \(x\) ab der aktuellen Untergrenze aus, solange die Bedingung \(Px\le 2K\) erfüllt bleibt. Weil der nächste Aufruf wieder \(x\) als neue Untergrenze erhält, werden Permutationen wie \(2,3,2\) und \(3,2,2\) gar nicht erst mehrfach untersucht.
Nach Abschluss der Tiefensuche laufen die Implementierungen einmal über \(k=2,3,\dots,K\), tragen die minimalen Produkte in eine Menge ein und summieren anschließend die verschiedenen Elemente dieser Menge. Dieses Entfernen von Duplikaten ist unverzichtbar, weil dieselbe minimale Produktsummenzahl für mehrere Werte von \(k\) gleichzeitig minimal sein kann. Schon kleine Beispiele zeigen, dass ein einziger Zahlenwert zu mehreren benachbarten Mengenlängen gehört.
Sei \(T(K)\) die Anzahl aller nicht abnehmenden Faktortupel \((f_1,\dots,f_m)\) mit \(f_i\ge 2\) und Produkt höchstens \(2K\). Die Tiefensuche besucht jedes solche Tupel genau einmal, daher benötigt die Enumerationsphase \(O(T(K))\) Zeit. Das ist die natürliche Komplexitätsbeschreibung für dieses Verfahren, denn der Code läuft tatsächlich den Baum aller multiplikativen Faktorisierungen unter der Schranke \(2K\) ab.
Der zusätzliche Durchlauf über \(k=2,\dots,K\) kostet \(O(K)\). Die Rekursionstiefe ist höchstens \(\lfloor\log_2(2K)\rfloor\), und der zusätzliche Speicherbedarf beträgt \(O(K)\) für das Array der besten Werte und die Menge der verschiedenen Minima sowie \(O(\log K)\) für den Rekursionsstapel. Für \(K=12000\) sorgt die Grenze \(2K=24000\) dafür, dass dieser direkte DFS-Ansatz problemlos praktikabel bleibt.
\(k \ge 2\) için bir çarpım-toplam sayısı, aynı \(k\) tane pozitif sayının hem toplamı hem de çarpımı olarak yazılabilen pozitif bir \(N\) tamsayısıdır:
$$N=a_1+a_2+\cdots+a_k=a_1a_2\cdots a_k,\qquad a_i\ge 1.$$
\(M(k)\) bu özelliği sağlayan en küçük sayı olsun. Soruda istenen şey, \(M(2),M(3),\dots,M(12000)\) değerleri arasındaki farklı sayıların toplamıdır. Tüm \(k\)-li dizileri doğrudan taramak çok verimsizdir; çünkü çoğu terim 1 olur ve çarpımı değiştirmez. Bu yüzden uygulamalar yalnızca 1'den büyük çarpanları üretir ve doğru küme büyüklüğünü oradan çıkarır.
\(K=12000\) yazalım. Temel gözlem şudur: Trivial olmayan çarpanlar sabitlendiğinde kaç tane 1 eklenmesi gerektiği de otomatik olarak belirlenir. Böylece problem, toplamsal ayrışımları denemek yerine çarpımsal ayrışımları gezmeye dönüşür.
\(f_1\le f_2\le \cdots \le f_m\) olacak şekilde ve her biri \(f_i\ge 2\) olan çarpanlar seçelim. Tanımlar:
$$P=\prod_{i=1}^{m} f_i,\qquad S=\sum_{i=1}^{m} f_i.$$
Bunlara tam olarak \(P-S\) tane 1 eklersek çarpım yine \(P\) kalır, toplam ise
$$S+(P-S)=P$$
olur. Dolayısıyla oluşan çarpım-toplam gösteriminin boyutu
$$k=(P-S)+m=P-S+m$$
şeklindedir. Ters yönde de her çarpım-toplam gösterimi, içindeki tüm 1'ler çıkarıldığında tam olarak bu biçime iner. Kodun kullandığı temel değişmez budur: \(\ge 2\) olan her çarpan çokluğu, tek bir \((k,P)\) adayını belirler. Tek çarpanlı durumda her zaman \(k=1\) elde edilir; dolayısıyla asıl ilginç aralık, en az iki trivial olmayan çarpan seçildiğinde başlar.
Aynı sayı farklı çarpımsal ayrışımlardan gelebilir ve bu ayrışımlar farklı küme boyutları üretebilir. Örneğin
$$12=2\cdot 6 \qquad\Longrightarrow\qquad k=12-(2+6)+2=6,$$
dolayısıyla şu gösterim geçerlidir:
$$12=1+1+1+1+2+6=1\cdot 1\cdot 1\cdot 1\cdot 2\cdot 6.$$
Fakat
$$12=2\cdot 2\cdot 3 \qquad\Longrightarrow\qquad k=12-(2+2+3)+3=8$$
olduğunda başka bir gösterim elde ederiz:
$$12=1+1+1+1+1+2+2+3=1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 2\cdot 2\cdot 3.$$
Bu nedenle algoritma her \(k\) için ayrı bir arama yapmaz. Tüm uygun çarpan ayrışımlarını gezer ve ortaya çıkan her \(k\) için görülen en küçük çarpımı günceller.
Basit bir yapı, küresel arama sınırını verir. Her \(k\ge 2\) için \(k-2\) tane 1 ile birlikte 2 ve \(k\) sayılarını alalım. Toplam da çarpım da \(2k\) olur:
$$2k=\underbrace{1+\cdots+1}_{k-2\text{ terim}}+2+k=\underbrace{1\cdots 1}_{k-2\text{ terim}}\cdot 2\cdot k.$$
Buradan
$$M(k)\le 2k$$
çıkar. Soruda \(k\le K=12000\) olduğundan her minimum çarpım-toplam sayısı en fazla \(2K=24000\) olabilir. Bu yüzden mevcut çarpımı \(24000\)'i aşmış her özyinelemeli dal artık cevaba katkı yapamaz ve hemen kesilebilir.
Uygulamalar çarpan ayrışımlarını doğrudan derinlik öncelikli aramayla kurar. Bir arama durumu
$$\bigl(P,S,m,a\bigr)$$
ile temsil edilir; burada \(P\) mevcut çarpım, \(S\) mevcut toplam, \(m\) seçilmiş çarpan sayısı ve \(a\) bir sonraki çarpan için izin verilen en küçük değerdir. Bu durumdan her geçerli uzatma, \(x\ge a\) ve \(Px\le 2K\) koşullarıyla bir \(x\) seçip
$$\bigl(Px,\ S+x,\ m+1,\ x\bigr)$$
durumuna gider. \(x\) değerinin yeni alt sınır olarak taşınması çarpan dizisini azalmayan sırada tutar; böylece aynı çarpan çokluğu yalnızca bir kez üretilir. Her ziyaret edilen düğümde ilgili küme boyutu
$$k=P-S+m$$
olarak hesaplanır. Eğer \(2\le k\le K\) ise mevcut \(P\) değeri, o \(k\) için geçerli bir adaydır ve gerekliyse saklanan minimum güncellenir.
Aynı formül budamayı da açıklar. \(x\ge 2\) olan yeni bir çarpan eklenince
$$k'=Px-(S+x)+(m+1)=k+(x-1)(P-1)\ge k$$
olur. Yani arama derinleştikçe \(k\) hiçbir zaman küçülmez. Bir durumda \(k>K\) olduktan sonra alt ağaçtaki hiçbir torun faydalı aralığa geri dönemez; dolayısıyla tüm alt ağaç güvenle atılır. Derinlik de küçüktür: Her çarpan en az 2 olduğundan ve çarpım \(2K\)'yı geçmediğinden her zaman \(m\le \lfloor\log_2(2K)\rfloor\) vardır.
Boş durum \((1,0,0,2)\) ile başlayıp \(2,2,3\) çarpanlarını seçen dala bakalım. Ardışık durumlar
$$ (2,2,1,2),\qquad (4,4,2,2),\qquad (12,7,3,3) $$
şeklindedir. Bunların \(k=P-S+m\) değerleri sırasıyla \(1\), \(2\) ve \(8\) olur. Ortadaki durum
$$4=2+2=2\cdot 2$$
eşitliğini verir; yani \(M(2)\le 4\). Son durum ise \(k=12-7+3=8\) üretir; bu da beş tane 1 eklenmesi gerektiği anlamına gelir:
$$12=1+1+1+1+1+2+2+3=1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 2\cdot 2\cdot 3.$$
Buna karşılık \(2,6\) dalı aynı 12 çarpımına ulaşır ama \(k=6\) üretir. Bu tek örnek yöntemin iki ana özelliğini gösterir: geçerli adaylar arama ağacının ara düğümlerinde oluşur ve aynı çarpım birden fazla küme boyutuna ait olabilir.
C++, Python ve Java uygulamaları, \(2\le k\le K\) için şimdiye kadar bulunan en küçük çarpımı tutan bir dizi ayırır ve bunu başlangıçta büyük bir bekçi değerle doldurur. Arama; çarpım 1, toplam 0, seçilmiş çarpan sayısı 0 ve bir sonraki en küçük çarpan 2 olacak şekilde boş ayrışımla başlar.
Her özyinelemeli çağrı önce \(k=P-S+m\) değerini hesaplar. Bu değer hedef aralıkta ise mevcut çarpım \(P\) saklanan minimumla karşılaştırılır. Ardından, çarpım sınırı \(Px\le 2K\) bozulana kadar geçerli alt sınırdan başlayarak tüm \(x\) değerleri denenir. Bir sonraki çağrıda yeni alt sınır yine \(x\) olduğu için \(2,3,2\) ve \(3,2,2\) gibi aynı çokluğun farklı sıraları ayrı ayrı gezilmez.
DFS tamamlandıktan sonra uygulamalar \(k=2,3,\dots,K\) aralığını tarar, elde edilen minimum çarpımları bir kümeye yerleştirir ve farklı küme elemanlarının toplamını alır. Bu son tekilleştirme adımı zorunludur; çünkü aynı minimum çarpım-toplam sayısı birkaç farklı \(k\) değeri için aynı anda minimum olabilir. Küçük örnekler bile tek bir sayının komşu birkaç küme boyutunda görünebildiğini gösterir.
\(T(K)\), tüm bileşenleri \(\ge 2\) olan ve çarpımı en fazla \(2K\) olan azalmayan çarpan dizilerinin sayısı olsun. DFS bu dizilerin her birini tam bir kez ziyaret eder; dolayısıyla üretim aşamasının çalışma süresi \(O(T(K))\) olur. Bu yöntem için doğal karmaşıklık ölçüsü budur, çünkü algoritma gerçekten de \(2K\) kesimine kadar olan çarpımsal ayrışım ağacını dolaşır.
Buna ek olarak \(k=2,\dots,K\) aralığında yapılan son tarama \(O(K)\) maliyetlidir. Özyineleme derinliği en fazla \(\lfloor\log_2(2K)\rfloor\) kadardır. Yardımcı bellek kullanımı, en iyi değer dizisi ve farklı minimumlar kümesi için \(O(K)\), çağrı yığını için ise \(O(\log K)\) olur. \(K=12000\) için \(2K=24000\) sınırı arama ağacını yeterince küçük tuttuğundan bu doğrudan DFS yaklaşımı pratikte rahatlıkla çalışır.
Para \(k \ge 2\), un número producto-suma es un entero positivo \(N\) que puede escribirse a la vez como suma y como producto del mismo multiconjunto de \(k\) enteros positivos:
$$N=a_1+a_2+\cdots+a_k=a_1a_2\cdots a_k,\qquad a_i\ge 1.$$
Sea \(M(k)\) el menor valor con esa propiedad. La tarea consiste en sumar todos los valores distintos entre \(M(2),M(3),\dots,M(12000)\). Buscar directamente entre todos los \(k\)-tuplos sería muy ineficiente, porque la mayoría de las entradas son 1 y no alteran el producto. Por eso las implementaciones solo enumeran los factores mayores que 1 y a partir de ellos reconstruyen el tamaño correcto del conjunto.
Escribamos \(K=12000\). La observación central es que, una vez fijados los factores no triviales, la cantidad de unos ya queda determinada. Así, el problema deja de ser una búsqueda sobre descomposiciones aditivas arbitrarias y pasa a ser una búsqueda sobre factorizaciones multiplicativas.
Tomemos factores no decrecientes \(f_1\le f_2\le \cdots \le f_m\) con \(f_i\ge 2\). Definimos
$$P=\prod_{i=1}^{m} f_i,\qquad S=\sum_{i=1}^{m} f_i.$$
Si añadimos exactamente \(P-S\) unos, el producto sigue siendo \(P\), mientras que la suma pasa a ser
$$S+(P-S)=P.$$
Por tanto, la identidad producto-suma resultante tiene tamaño
$$k=(P-S)+m=P-S+m.$$
En sentido inverso, cualquier representación producto-suma puede reducirse a esta forma quitando todos los unos. Esa es la invariante básica del código: cada multiconjunto de factores \(\ge 2\) determina exactamente un par candidato \((k,P)\). El caso de un solo factor siempre produce \(k=1\), de modo que el rango interesante empieza cuando ya se han elegido al menos dos factores no triviales.
Un mismo entero puede aparecer a partir de distintas particiones multiplicativas, y esas particiones pueden llevar a tamaños de conjunto diferentes. Por ejemplo,
$$12=2\cdot 6 \qquad\Longrightarrow\qquad k=12-(2+6)+2=6,$$
así que una representación válida es
$$12=1+1+1+1+2+6=1\cdot 1\cdot 1\cdot 1\cdot 2\cdot 6.$$
Pero también
$$12=2\cdot 2\cdot 3 \qquad\Longrightarrow\qquad k=12-(2+2+3)+3=8$$
da otra identidad válida:
$$12=1+1+1+1+1+2+2+3=1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 2\cdot 2\cdot 3.$$
Por eso el algoritmo no resuelve cada \(k\) por separado. Recorre todas las factorizaciones admisibles y actualiza el mejor producto conocido para cada \(k\) que aparezca.
Una construcción muy simple proporciona un límite global para la búsqueda. Para cualquier \(k\ge 2\), tomemos el multiconjunto formado por \(k-2\) unos, además de 2 y \(k\). Su suma y su producto son ambos \(2k\):
$$2k=\underbrace{1+\cdots+1}_{k-2\text{ términos}}+2+k=\underbrace{1\cdots 1}_{k-2\text{ términos}}\cdot 2\cdot k.$$
De aquí se deduce
$$M(k)\le 2k.$$
En el problema completo se tiene \(k\le K=12000\), luego todo número producto-suma mínimo está acotado por \(2K=24000\). Cualquier rama recursiva cuyo producto actual ya supere \(24000\) nunca podrá mejorar la respuesta y puede descartarse en el acto.
Las implementaciones construyen las factorizaciones directamente mediante búsqueda en profundidad. Un estado de búsqueda es
$$\bigl(P,S,m,a\bigr),$$
donde \(P\) es el producto actual, \(S\) la suma actual, \(m\) el número de factores elegidos y \(a\) el menor valor permitido para el siguiente factor. Desde ese estado, cada extensión legal elige un \(x\ge a\) con \(Px\le 2K\) y pasa a
$$\bigl(Px,\ S+x,\ m+1,\ x\bigr).$$
Reutilizar \(x\) como nueva cota inferior obliga a que la secuencia de factores sea no decreciente, de modo que cada multiconjunto de factores se genera exactamente una vez. En cada nodo visitado, el tamaño inducido del conjunto es
$$k=P-S+m.$$
Si \(2\le k\le K\), el producto actual \(P\) es un candidato válido para \(M(k)\), y se actualiza el mínimo almacenado si corresponde.
La misma fórmula justifica la poda. Después de añadir un factor \(x\ge 2\), el nuevo valor es
$$k'=Px-(S+x)+(m+1)=k+(x-1)(P-1)\ge k.$$
Es decir, \(k\) nunca disminuye al profundizar en la recursión. Una vez que un estado alcanza \(k>K\), todos sus descendientes también quedarán fuera del rango útil, así que todo ese subárbol puede omitirse con seguridad. La profundidad de la recursión también es pequeña: como cada factor elegido es al menos 2 y el producto nunca supera \(2K\), siempre se cumple \(m\le \lfloor\log_2(2K)\rfloor\).
Partimos del estado vacío \((1,0,0,2)\) y seguimos la rama que elige los factores \(2,2,3\). Los estados sucesivos son
$$ (2,2,1,2),\qquad (4,4,2,2),\qquad (12,7,3,3). $$
Los valores correspondientes de \(k=P-S+m\) son \(1\), \(2\) y \(8\). El estado intermedio produce
$$4=2+2=2\cdot 2,$$
luego \(M(2)\le 4\). El último estado da \(k=12-7+3=8\), lo que significa que hay que añadir cinco unos:
$$12=1+1+1+1+1+2+2+3=1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 2\cdot 2\cdot 3.$$
Otra rama, la de \(2,6\), alcanza el mismo producto 12 pero genera \(k=6\). Ese ejemplo concreto muestra los dos fenómenos esenciales del método: aparecen candidatos válidos en nodos intermedios del árbol de búsqueda y un mismo producto puede corresponder a varios tamaños de conjunto diferentes.
Las implementaciones en C++, Python y Java reservan un arreglo indexado por \(k\), inicialmente lleno con un valor centinela grande, para guardar el menor producto encontrado hasta ese momento para cada \(2\le k\le K\). La exploración comienza con la factorización vacía: producto 1, suma 0, ningún factor elegido y 2 como siguiente factor mínimo permitido.
Cada llamada recursiva calcula primero \(k=P-S+m\). Si ese valor cae dentro del intervalo objetivo, compara el producto actual \(P\) con el mínimo almacenado y conserva el menor. Después prueba todos los factores siguientes \(x\) desde la cota inferior actual hasta que la condición \(Px\le 2K\) deje de cumplirse. Como la siguiente llamada vuelve a usar \(x\) como nueva cota inferior, permutaciones como \(2,3,2\) y \(3,2,2\) no se recorren por separado.
Cuando termina el DFS, las implementaciones recorren \(k=2,3,\dots,K\), insertan los productos mínimos en un conjunto y suman los elementos distintos de ese conjunto. Ese paso final es imprescindible porque un mismo número producto-suma mínimo puede ser óptimo para más de un valor de \(k\). Incluso en los casos pequeños ya se ve que un único entero puede ser mínimo para varios tamaños vecinos.
Sea \(T(K)\) el número de tuplas no decrecientes de factores \((f_1,\dots,f_m)\) con \(f_i\ge 2\) y producto a lo sumo \(2K\). El DFS visita cada una exactamente una vez, así que la fase de enumeración tarda \(O(T(K))\). Esa es la medida natural de complejidad para este enfoque, porque el algoritmo recorre literalmente el árbol de factorizaciones multiplicativas bajo el corte \(2K\).
El barrido adicional sobre \(k=2,\dots,K\) cuesta \(O(K)\). La profundidad de la recursión es como mucho \(\lfloor\log_2(2K)\rfloor\), y la memoria auxiliar es \(O(K)\) para el arreglo de mejores valores y el conjunto final de mínimos distintos, más \(O(\log K)\) para la pila de recursión. Para \(K=12000\), la barrera \(2K=24000\) mantiene el árbol de búsqueda lo bastante pequeño como para que este DFS directo resulte totalmente práctico.
当 \(k \ge 2\) 时，乘积和数是指这样一个正整数 \(N\)：它既能写成同一组 \(k\) 个正整数的和，也能写成这 \(k\) 个正整数的积：
$$N=a_1+a_2+\cdots+a_k=a_1a_2\cdots a_k,\qquad a_i\ge 1.$$
记 \(M(k)\) 为满足这一条件的最小 \(N\)。题目要求求出 \(M(2),M(3),\dots,M(12000)\) 中所有不同取值的总和。若直接枚举长度为 \(k\) 的所有数组合，会产生大量无意义的重复，因为其中大部分位置只是 1，而 1 对乘积没有影响。三个实现真正做的事情，是只枚举大于 1 的因子，然后再由这些因子反推出对应的集合大小。
设 \(K=12000\)。这道题最关键的观察是：一旦所有非平凡因子都确定了，需要补多少个 1 也就随之确定了。因此问题真正的搜索空间并不是“所有长度为 \(k\) 的和式”，而是“所有由不小于 2 的因子组成的乘法分解”。
取一个非降序因子序列 \(f_1\le f_2\le \cdots \le f_m\)，并且每个因子都满足 \(f_i\ge 2\)。定义
$$P=\prod_{i=1}^{m} f_i,\qquad S=\sum_{i=1}^{m} f_i.$$
如果在这些因子之外再补上恰好 \(P-S\) 个 1，那么乘积仍然保持为 \(P\)，而总和会变成
$$S+(P-S)=P.$$
于是这组数形成了一个大小为
$$k=(P-S)+m=P-S+m$$
的乘积和表示。反过来，任何一个乘积和表示，只要把其中所有的 1 去掉，就一定能还原成这种形式。这就是代码使用的核心不变量：每一个只含 \(\ge 2\) 因子的多重集合，都会唯一地对应一个候选对 \((k,P)\)。单因子的情况永远只会得到 \(k=1\)，所以真正有用的候选从至少选出两个非平凡因子才开始出现。
同一个整数可以由不同的乘法拆分得到，而不同的拆分会对应不同的集合大小。例如
$$12=2\cdot 6 \qquad\Longrightarrow\qquad k=12-(2+6)+2=6,$$
于是可以写成
$$12=1+1+1+1+2+6=1\cdot 1\cdot 1\cdot 1\cdot 2\cdot 6.$$
但如果使用另一种分解
$$12=2\cdot 2\cdot 3 \qquad\Longrightarrow\qquad k=12-(2+2+3)+3=8,$$
就会得到另一种合法表示：
$$12=1+1+1+1+1+2+2+3=1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 2\cdot 2\cdot 3.$$
这说明算法不能把每个 \(k\) 当成彼此独立的问题去求。更自然的做法是遍历所有允许的因子分解，并把它们产生的每一个 \(k\) 对应的最优乘积都更新一遍。
要把搜索范围压下来，需要一个通用上界。对任意 \(k\ge 2\)，考虑由 \(k-2\) 个 1，再加上 2 和 \(k\) 组成的多重集合。它的和与积都等于 \(2k\)：
$$2k=\underbrace{1+\cdots+1}_{k-2\text{ 项}}+2+k=\underbrace{1\cdots 1}_{k-2\text{ 项}}\cdot 2\cdot k.$$
因此一定有
$$M(k)\le 2k.$$
在本题里 \(k\le K=12000\)，所以所有最小乘积和数都不会超过 \(2K=24000\)。这就是实现里最重要的全局剪枝条件：只要当前递归分支的乘积已经大于 \(24000\)，它就不可能再贡献任何答案。
三个实现都直接用深度优先搜索来构造因子分解。一个搜索状态写成
$$\bigl(P,S,m,a\bigr),$$
其中 \(P\) 是当前乘积，\(S\) 是当前因子和，\(m\) 是已经选出的因子个数，\(a\) 是下一个因子允许的最小值。从这个状态出发，所有合法扩展都是选择某个满足 \(x\ge a\) 且 \(Px\le 2K\) 的 \(x\)，然后转移到
$$\bigl(Px,\ S+x,\ m+1,\ x\bigr).$$
把 \(x\) 继续作为下一层的下界，等价于强制因子序列保持非降序，所以每个无序因子多重集合只会被生成一次，不会因为排列顺序不同而重复访问。在每个访问到的节点上，对应的集合大小都由
$$k=P-S+m$$
给出。只要 \(2\le k\le K\)，当前的乘积 \(P\) 就是 \(M(k)\) 的一个有效候选值，可以拿来更新该 \(k\) 的最小记录。
同一个公式还给出了递归剪枝的严格依据。若再附加一个因子 \(x\ge 2\)，新的 \(k\) 变为
$$k'=Px-(S+x)+(m+1)=k+(x-1)(P-1)\ge k.$$
也就是说，随着递归深入，\(k\) 只会保持不变或增大，绝不可能下降。因此一旦某个状态已经满足 \(k>K\)，它的所有后代也都不可能重新回到有用区间，整个子树都可以立刻丢弃。另外，递归深度本身也很小：因为每次加入的因子至少是 2，而总乘积始终不超过 \(2K\)，所以总有 \(m\le \lfloor\log_2(2K)\rfloor\)。
从空状态 \((1,0,0,2)\) 出发，沿着选择因子 \(2,2,3\) 的分支往下走，会依次得到状态
$$ (2,2,1,2),\qquad (4,4,2,2),\qquad (12,7,3,3). $$
对应的 \(k=P-S+m\) 依次是 \(1\)、\(2\)、\(8\)。中间那个状态直接给出
$$4=2+2=2\cdot 2,$$
因此可以立即知道 \(M(2)\le 4\)。最后那个状态给出 \(k=12-7+3=8\)，也就是说必须补上五个 1：
$$12=1+1+1+1+1+2+2+3=1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 2\cdot 2\cdot 3.$$
如果换另一条分支 \(2,6\)，会到达同样的乘积 12，但对应的是 \(k=6\)。这个例子恰好把方法的两个核心现象都展示出来了：第一，合法候选会在搜索树的中间节点出现；第二，同一个乘积可以同时服务多个不同的 \(k\)。
C++、Python 和 Java 三个实现都会先分配一个按 \(k\) 索引的数组，用很大的哨兵值初始化，用来记录每个 \(2\le k\le K\) 目前看到的最小乘积。搜索从空因子分解开始，也就是乘积 1、总和 0、已选因子数 0，以及下一因子下界为 2。
每次递归调用都会先计算 \(k=P-S+m\)。如果这个 \(k\) 落在目标范围内，就用当前乘积 \(P\) 去更新对应的最优值。然后程序从当前下界开始枚举所有可能的下一个因子 \(x\)，直到乘积限制 \(Px\le 2K\) 不再满足为止。由于下一层递归仍然把 \(x\) 作为新的下界，像 \(2,3,2\) 和 \(3,2,2\) 这种仅仅顺序不同的情况不会被重复搜索。
DFS 结束后，实现会遍历 \(k=2,3,\dots,K\)，把每个 \(k\) 的最小乘积放进一个集合，再对集合中的不同元素求和。这个去重步骤必不可少，因为同一个最小乘积和数可能同时是多个 \(k\) 的最优解。题目的答案要的是不同最小值的总和，而不是把每个 \(k\) 的最优值直接机械相加。
记 \(T(K)\) 为所有满足“因子均不小于 2、且总乘积不超过 \(2K\)”的非降序因子序列 \((f_1,\dots,f_m)\) 的数量。DFS 会把这些序列逐一访问一遍，因此枚举阶段的时间复杂度就是 \(O(T(K))\)。对于这个算法来说，这是最自然的复杂度描述，因为它确实在遍历一个以 \(2K\) 为截断的乘法分解树。
额外的 \(k=2,\dots,K\) 线性扫描需要 \(O(K)\) 时间。递归深度最多为 \(\lfloor\log_2(2K)\rfloor\)。辅助空间方面，记录最优值的数组和最后的去重集合需要 \(O(K)\)，递归调用栈需要 \(O(\log K)\)。在本题的 \(K=12000\) 下，\(2K=24000\) 这个上界足够小，因此这种直接的 DFS 搜索完全可行。
При \(k \ge 2\) числом произведение-сумма называется такое положительное целое \(N\), которое можно записать и как сумму, и как произведение одного и того же мультимножества из \(k\) положительных чисел:
$$N=a_1+a_2+\cdots+a_k=a_1a_2\cdots a_k,\qquad a_i\ge 1.$$
Обозначим через \(M(k)\) наименьшее такое \(N\). Нужно найти сумму всех различных значений среди \(M(2),M(3),\dots,M(12000)\). Прямой перебор всех \(k\)-кортежей здесь почти полностью заполнен единицами и потому дает колоссальное количество повторов. Поэтому реализации перечисляют только множители больше 1, а нужную длину набора восстанавливают уже из них.
Положим \(K=12000\). Ключевое наблюдение состоит в том, что после фиксации всех нетривиальных множителей число необходимых единиц определяется однозначно. Значит, реальное пространство поиска задается не произвольными суммами длины \(k\), а мультисетами множителей, не меньших 2.
Выберем неубывающие множители \(f_1\le f_2\le \cdots \le f_m\), где каждый \(f_i\ge 2\). Обозначим
$$P=\prod_{i=1}^{m} f_i,\qquad S=\sum_{i=1}^{m} f_i.$$
Если добавить к ним ровно \(P-S\) единиц, то произведение останется равным \(P\), а сумма станет
$$S+(P-S)=P.$$
Следовательно, размер получившегося набора равен
$$k=(P-S)+m=P-S+m.$$
В обратную сторону это тоже верно: любую запись произведение-сумма можно свести к такой форме, если удалить все единицы. Это и есть основной инвариант решения: каждый мультимножитель из чисел \(\ge 2\) задает ровно одну кандидатную пару \((k,P)\). Случай с одним множителем всегда дает \(k=1\), поэтому полезные состояния начинаются только после выбора хотя бы двух нетривиальных множителей.
Один и тот же целый результат может получаться из разных мультипликативных разбиений, а эти разбиения могут вести к разным размерам набора. Например,
$$12=2\cdot 6 \qquad\Longrightarrow\qquad k=12-(2+6)+2=6,$$
поэтому верна запись
$$12=1+1+1+1+2+6=1\cdot 1\cdot 1\cdot 1\cdot 2\cdot 6.$$
Но разложение
$$12=2\cdot 2\cdot 3 \qquad\Longrightarrow\qquad k=12-(2+2+3)+3=8$$
дает уже другую корректную идентичность:
$$12=1+1+1+1+1+2+2+3=1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 2\cdot 2\cdot 3.$$
Именно поэтому алгоритм не решает задачу отдельно для каждого \(k\). Он проходит по всем допустимым факторизациям и обновляет наилучшее известное произведение для каждого встретившегося значения \(k\).
Простая конструкция дает глобальную верхнюю границу для поиска. Для любого \(k\ge 2\) возьмем мультимножество из \(k-2\) единиц, а также чисел 2 и \(k\). Его сумма и произведение одновременно равны \(2k\):
$$2k=\underbrace{1+\cdots+1}_{k-2\text{ слагаемых}}+2+k=\underbrace{1\cdots 1}_{k-2\text{ множителей}}\cdot 2\cdot k.$$
Следовательно,
$$M(k)\le 2k.$$
В полной задаче \(k\le K=12000\), значит любой минимальный результат не превосходит \(2K=24000\). Поэтому всякий рекурсивный путь, у которого текущее произведение уже больше \(24000\), можно немедленно отбросить: он не сумеет улучшить ответ.
Во всех реализациях факторизации строятся напрямую с помощью поиска в глубину. Состояние поиска имеет вид
$$\bigl(P,S,m,a\bigr),$$
где \(P\) — текущее произведение, \(S\) — текущая сумма, \(m\) — число уже выбранных множителей, а \(a\) — минимально допустимое значение следующего множителя. Из такого состояния каждый допустимый переход выбирает \(x\ge a\) при условии \(Px\le 2K\) и переходит в
$$\bigl(Px,\ S+x,\ m+1,\ x\bigr).$$
Передача \(x\) как новой нижней границы заставляет последовательность множителей оставаться неубывающей, поэтому каждое неупорядоченное мультимножество факторов генерируется ровно один раз. В каждом посещенном узле соответствующий размер набора вычисляется по формуле
$$k=P-S+m.$$
Если \(2\le k\le K\), текущее произведение \(P\) является корректным кандидатом для \(M(k)\), и сохраненный минимум при необходимости обновляется.
Та же формула объясняет и отсечение. После добавления нового множителя \(x\ge 2\) получаем
$$k'=Px-(S+x)+(m+1)=k+(x-1)(P-1)\ge k.$$
Значит, при углублении рекурсии значение \(k\) никогда не уменьшается. Если в некотором состоянии уже выполнено \(k>K\), то ни один потомок не сможет вернуться в полезный диапазон, и весь поддеревом можно безопасно пренебречь. Глубина рекурсии тоже невелика: каждый множитель не меньше 2, а произведение никогда не превышает \(2K\), поэтому всегда \(m\le \lfloor\log_2(2K)\rfloor\).
Начнем с пустого состояния \((1,0,0,2)\) и пойдем по ветви, выбирающей множители \(2,2,3\). Последовательность состояний такова:
$$ (2,2,1,2),\qquad (4,4,2,2),\qquad (12,7,3,3). $$
Соответствующие значения \(k=P-S+m\) равны \(1\), \(2\) и \(8\). Среднее состояние дает
$$4=2+2=2\cdot 2,$$
так что сразу видно: \(M(2)\le 4\). Последнее состояние дает \(k=12-7+3=8\), то есть нужно добавить пять единиц:
$$12=1+1+1+1+1+2+2+3=1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 2\cdot 2\cdot 3.$$
Другая ветвь, а именно \(2,6\), приводит к тому же произведению 12, но уже с \(k=6\). Этот пример одновременно показывает два ключевых свойства метода: корректные кандидаты появляются в промежуточных узлах дерева поиска, и одно произведение может соответствовать сразу нескольким разным длинам набора.
Реализации на C++, Python и Java выделяют массив, индексируемый по \(k\), и заполняют его большим сторожевым значением. В нем хранится наименьшее произведение, найденное к данному моменту для каждого \(2\le k\le K\). Поиск стартует из пустой факторизации: произведение 1, сумма 0, выбранных множителей пока нет, а минимально допустимый следующий множитель равен 2.
Каждый рекурсивный вызов сначала вычисляет \(k=P-S+m\). Если это значение попадает в нужный диапазон, текущее произведение \(P\) сравнивается с уже сохраненным минимумом. Затем перебираются все возможные следующие множители \(x\), начиная с текущей нижней границы, пока не нарушится ограничение \(Px\le 2K\). Поскольку следующий вызов снова использует \(x\) как новую нижнюю границу, перестановки вроде \(2,3,2\) и \(3,2,2\) не исследуются по отдельности.
После завершения DFS реализации проходят по всем \(k=2,3,\dots,K\), помещают найденные минимальные произведения в множество, а затем суммируют различные элементы этого множества. Этот шаг необходим, потому что одно и то же минимальное число произведение-сумма может быть оптимальным сразу для нескольких значений \(k\). В ответ входит сумма различных минимальных значений, а не простая сумма по всем индексам.
Пусть \(T(K)\) обозначает число всех неубывающих наборов множителей \((f_1,\dots,f_m)\), для которых \(f_i\ge 2\) и произведение не превосходит \(2K\). DFS посещает каждый такой набор ровно один раз, так что фаза перечисления работает за \(O(T(K))\). Это естественная оценка именно для данного алгоритма, потому что он буквально проходит по дереву мультипликативных разбиений под отсечением \(2K\).
Дополнительный линейный проход по \(k=2,\dots,K\) требует \(O(K)\) времени. Глубина рекурсии не превышает \(\lfloor\log_2(2K)\rfloor\). Дополнительная память составляет \(O(K)\) для массива лучших значений и множества различных минимумов, плюс \(O(\log K)\) для стека рекурсии. При \(K=12000\) граница \(2K=24000\) делает дерево поиска достаточно небольшим, поэтому такой прямой DFS-подход оказывается вполне практичным.
عندما يكون \(k \ge 2\)، فإن عدد الناتج-المجموع هو عدد صحيح موجب \(N\) يمكن كتابته في الوقت نفسه على أنه مجموع وعلى أنه حاصل ضرب للمجموعة نفسها المكوّنة من \(k\) أعداد صحيحة موجبة:
$$N=a_1+a_2+\cdots+a_k=a_1a_2\cdots a_k,\qquad a_i\ge 1.$$
ولنرمز إلى أصغر عدد يحقق ذلك من أجل قيمة معيّنة لـ \(k\) بالرمز \(M(k)\). المطلوب هو جمع جميع القيم المختلفة بين \(M(2),M(3),\dots,M(12000)\). البحث المباشر في كل الترتيبات ذات الطول \(k\) غير عملي، لأن معظم الحدود تكون مساوية لـ 1 ولا تغيّر حاصل الضرب. لذلك تعتمد التطبيقات على تعداد العوامل الأكبر من 1 فقط، ثم تستنتج من هذه العوامل الحجم الصحيح للمجموعة.
لنكتب \(K=12000\). الفكرة الأساسية هي أن عدد الواحدات المطلوبة يصبح محددًا تلقائيًا بمجرد تثبيت العوامل غير التافهة. وبذلك تتحول المسألة من بحث في جميع التحليلات الجمعيّة الممكنة إلى بحث في جميع التحليلات الضربيّة الممكنة.
لنختر عوامل غير متناقصة
$$f_1\le f_2\le \cdots \le f_m,\qquad f_i\ge 2.$$
ونعرّف
$$P=\prod_{i=1}^{m} f_i,\qquad S=\sum_{i=1}^{m} f_i.$$
إذا أضفنا بالضبط \(P-S\) واحدات، فإن حاصل الضرب يبقى مساويًا لـ \(P\)، بينما يصبح المجموع
$$S+(P-S)=P.$$
إذًا يصبح حجم تمثيل الناتج-المجموع مساويًا لـ
$$k=(P-S)+m=P-S+m.$$
وبالعكس، أي تمثيل من هذا النوع يمكن اختزاله إلى هذه الصورة بمجرد حذف كل الواحدات. هذه هي الثابتة الأساسية التي تبني عليها الشيفرة: كل مجموعة متعددة من العوامل التي لا تقل عن 2 تحدد زوجًا مرشحًا وحيدًا \((k,P)\). أما حالة العامل الوحيد فتعطي دائمًا \(k=1\)، ولهذا لا تبدأ الحالات المفيدة إلا بعد اختيار عاملين غير تافهين على الأقل.
قد ينتج العدد نفسه من أكثر من تحليل ضربي، وقد تؤدي هذه التحليلات المختلفة إلى أحجام مختلفة للمجموعة. على سبيل المثال،
$$12=2\cdot 6 \qquad\Longrightarrow\qquad k=12-(2+6)+2=6,$$
ومن ثم نحصل على التمثيل
$$12=1+1+1+1+2+6=1\cdot 1\cdot 1\cdot 1\cdot 2\cdot 6.$$
لكن التحليل
$$12=2\cdot 2\cdot 3 \qquad\Longrightarrow\qquad k=12-(2+2+3)+3=8$$
يعطي هوية صحيحة أخرى:
$$12=1+1+1+1+1+2+2+3=1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 2\cdot 2\cdot 3.$$
ولهذا لا تعالج الخوارزمية كل قيمة \(k\) على حدة. بل تمر على جميع التحليلات المسموح بها وتحدّث أصغر حاصل ضرب معروف لكل قيمة \(k\) تظهر أثناء البحث.
هناك بناء بسيط يعطي حدًا أعلى شاملًا لمساحة البحث. لأي \(k\ge 2\)، خذ \(k-2\) واحدات مع العددين 2 و\(k\). عندئذٍ يكون المجموع والناتج كلاهما مساويين لـ \(2k\):
$$2k=\underbrace{1+\cdots+1}_{k-2}+2+k=\underbrace{1\cdots 1}_{k-2}\cdot 2\cdot k.$$
إذًا
$$M(k)\le 2k.$$
وفي هذه المسألة لدينا \(k\le K=12000\)، ولذلك لا يمكن لأي عدد ناتج-مجموع أصغري أن يتجاوز \(2K=24000\). وأي فرع تكراري يصبح حاصل ضربه الحالي أكبر من \(24000\) لا يمكنه بعد ذلك أن يساهم في الجواب، ولذلك يمكن قطعه فورًا.
تقوم التطبيقات ببناء التحليلات الضربيّة مباشرة باستعمال البحث في العمق. وتمثل حالة البحث بالرباعي
$$\bigl(P,S,m,a\bigr),$$
حيث إن \(P\) هو حاصل الضرب الحالي، و\(S\) هو المجموع الحالي، و\(m\) هو عدد العوامل المختارة حتى الآن، و\(a\) هو أصغر عامل مسموح به في الخطوة التالية. ومن هذه الحالة، كل امتداد قانوني يختار قيمة \(x\ge a\) تحقق \(Px\le 2K\)، ثم ينتقل إلى
$$\bigl(Px,\ S+x,\ m+1,\ x\bigr).$$
تمرير \(x\) بوصفه الحد الأدنى الجديد يفرض أن تبقى سلسلة العوامل غير متناقصة، ولذلك لا يُولد كل متعدد مجموعة من العوامل إلا مرة واحدة. وفي كل عقدة مزارة يكون حجم المجموعة الموافق هو
$$k=P-S+m.$$
فإذا تحقق \(2\le k\le K\)، صار حاصل الضرب الحالي \(P\) مرشحًا صحيحًا للقيمة \(M(k)\)، ويمكن تحديث الحد الأدنى المخزّن لتلك القيمة.
والصيغة نفسها تبرر القطع أيضًا. فإذا أضفنا عاملًا جديدًا \(x\ge 2\)، فإن القيمة الجديدة لـ \(k\) تصبح
$$k'=Px-(S+x)+(m+1)=k+(x-1)(P-1)\ge k.$$
أي إن \(k\) لا تنخفض أبدًا مع التعمق في الاستدعاء التكراري. لذلك إذا وصلت حالة ما إلى \(k>K\)، فلن يتمكن أي ابن من أبناء هذه الحالة من العودة إلى المجال المفيد، ويمكن حذف الشجرة الفرعية كلها بأمان. كما أن عمق التكرار نفسه صغير: فكل عامل لا يقل عن 2، وحاصل الضرب لا يتجاوز \(2K\)، وبالتالي يبقى دائمًا
$$m\le \lfloor\log_2(2K)\rfloor.$$
لنبدأ من الحالة الفارغة \((1,0,0,2)\)، ونتبع الفرع الذي يختار العوامل \(2,2,3\). الحالات المتتالية هي
$$ (2,2,1,2),\qquad (4,4,2,2),\qquad (12,7,3,3). $$
وتكون القيم الموافقة لـ \(k=P-S+m\) هي \(1\) ثم \(2\) ثم \(8\). الحالة الوسطى تعطي
$$4=2+2=2\cdot 2,$$
ومن ثم نعرف أن \(M(2)\le 4\). أما الحالة الأخيرة فتعطي \(k=12-7+3=8\)، وهذا يعني أنه يجب إضافة خمس واحدات:
$$12=1+1+1+1+1+2+2+3=1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 2\cdot 2\cdot 3.$$
أما الفرع الآخر \(2,6\) فيصل إلى حاصل الضرب نفسه 12، لكنه ينتج \(k=6\) بدلًا من ذلك. هذا المثال الواحد يوضح الظاهرتين الأساسيتين في الطريقة: تظهر المرشحات الصالحة في العقد الداخلية لشجرة البحث، كما أن حاصل الضرب الواحد قد ينتمي إلى أكثر من حجم مجموعة.
تخصص تطبيقات C++ وPython وJava مصفوفة مفهرسة بالقيم \(k\)، وتملؤها أولًا بقيمة حارسة كبيرة، لكي تحفظ أصغر حاصل ضرب تم العثور عليه لكل \(2\le k\le K\). تبدأ عملية البحث من التحليل الفارغ: حاصل الضرب 1، والمجموع 0، وعدد العوامل المختارة 0، وأصغر عامل تالٍ مسموح به هو 2.
في كل استدعاء تكراري تُحسب أولًا القيمة \(k=P-S+m\). فإذا كانت داخل المجال المطلوب، قورِن حاصل الضرب الحالي \(P\) مع الحد الأدنى المخزّن واحتُفظ بالأصغر. بعد ذلك تُجرَّب كل العوامل التالية \(x\) ابتداءً من الحد الأدنى الحالي ما دام الشرط \(Px\le 2K\) محققًا. وبما أن الاستدعاء التالي يستخدم \(x\) مرة أخرى بوصفه الحد الأدنى الجديد، فإن ترتيبات مثل \(2,3,2\) و\(3,2,2\) لا تُفحَص على أنها حالات مختلفة.
بعد انتهاء DFS، تمر التطبيقات على جميع القيم \(k=2,3,\dots,K\)، وتضع القيم الدنيا الناتجة في مجموعة، ثم تجمع العناصر المختلفة في هذه المجموعة. وهذه الخطوة ضرورية لأن العدد الأصغري الناتج-المجموع نفسه قد يكون مثاليًا لأكثر من قيمة واحدة لـ \(k\). والمطلوب في النهاية هو مجموع القيم الدنيا المختلفة فقط، لا مجموع القيم مع تكرارها.
لنرمز بـ \(T(K)\) إلى عدد جميع سلاسل العوامل غير المتناقصة \((f_1,\dots,f_m)\) التي تحقق \(f_i\ge 2\) وحاصل ضربها لا يتجاوز \(2K\). يزور DFS كل سلسلة من هذه السلاسل مرة واحدة، ولذلك فإن زمن مرحلة التعداد يساوي \(O(T(K))\). وهذه هي الصياغة الطبيعية لتعقيد الخوارزمية، لأنها بالفعل تسير داخل شجرة التحليلات الضربيّة المقطوعة عند الحد \(2K\).
المسح الإضافي على القيم \(k=2,\dots,K\) يكلف \(O(K)\). وعمق المكدس التكراري لا يتجاوز \(\lfloor\log_2(2K)\rfloor\). أما الذاكرة الإضافية فمقدارها \(O(K)\) لمصفوفة أفضل القيم ولمجموعة القيم الدنيا المختلفة، بالإضافة إلى \(O(\log K)\) لمكدس الاستدعاءات. وعند \(K=12000\) يكون الحد \(2K=24000\) صغيرًا بما يكفي ليجعل هذا البحث المباشر في العمق عمليًا تمامًا.