For each positive integer \(n\), let \(M(n)\) be the minimum number of matchsticks needed to display an expression with value \(n\), using decimal digits together with the operators \(+\) and \(\times\). The seven-segment digit costs are fixed, and each operator contributes two extra matchsticks. The target quantity is
$$S(N)=\sum_{n=1}^{N} M(n),\qquad N=10^6.$$
The key observation is that the search space can be turned into a dynamic program over the integers \(1,2,\dots,N\), instead of a brute-force search over all expression trees.
The implementation builds the answer from smaller integers upward. Every candidate representation comes from one of three sources: writing \(n\) directly, writing \(n\) as a product of smaller values, or writing \(n\) as a sum whose last term is multiplicative.
Let \(c(d)\) be the matchstick cost of digit \(d\). For the standard seven-segment display used here,
$$c(0)=6,\ c(1)=2,\ c(2)=5,\ c(3)=5,\ c(4)=4,\ c(5)=5,\ c(6)=6,\ c(7)=3,\ c(8)=7,\ c(9)=6.$$
If \(n\) is written directly in decimal, its literal cost is
$$L(n)=\sum_{i=1}^{k} c(d_i).$$
The code computes this efficiently by the recurrence
$$L(n)=L\!\left(\left\lfloor\frac{n}{10}\right\rfloor\right)+c(n\bmod 10),\qquad L(0)=0.$$
This gives a valid upper bound for every \(M(n)\), because the literal representation is always available.
Define \(P(n)\) as the minimum matchstick cost of a term that evaluates to \(n\) and uses only decimal literals and multiplication. Then
$$P(n)=\min\!\left(L(n),\ \min_{\substack{d\mid n \\ 2\le d\le \sqrt{n}}}\bigl(P(d)+P(n/d)+2\bigr)\right).$$
The extra \(2\) is the cost of the multiplication sign. Restricting the divisor search to \(d\le\sqrt{n}\) is enough because factor pairs are symmetric.
This recurrence is exact for multiplicative terms: every product can be split at its top multiplication into two smaller multiplicative subterms, and conversely every such split produces a valid candidate.
Now let \(M(n)\) denote the true optimum for the value \(n\). The implementations treat a full expression as a sum of multiplicative terms, so after choosing the last summand we get
$$M(n)=\min\!\left(P(n),\ \min_{1\le a<n}\bigl(M(a)+P(n-a)+2\bigr)\right).$$
Here the left part \(a\) may already be an optimized full expression, while the right part \(n-a\) is the final multiplicative term. Again the \(+2\) accounts for the plus sign.
This recurrence turns the original expression problem into a shortest-cost decomposition problem on the interval \([1,N]\).
For small limits, the recurrences above can be evaluated directly. For \(N=10^6\), the optimized method instead starts from the literal table and repeatedly applies cost-improving relaxations.
For multiplication, every pair \(x\le y\) with \(xy\le N\) yields the candidate
$$\text{cost}(xy)\le \text{cost}(x)+\text{cost}(y)+2.$$
Running this update until no entry decreases produces the multiplication-closed table.
For addition, integers are grouped by current cost:
$$B_t=\{n\le N:\text{cost}(n)=t\}.$$
If \(x\in B_a\) and \(y\in B_b\), then \(x+y\) has candidate cost \(a+b+2\). Let
$$C_{\max}=\max_{1\le n\le N}\text{cost}(n).$$
Whenever \(a+b+2\ge C_{\max}\), that bucket pair cannot improve anything, so it is skipped. This cost-bucket pruning is the main reason the large computation is practical.
All updates are of the form “replace by a smaller integer if possible”, so the process is monotone decreasing and must eventually stabilize.
The recurrences become clearer on concrete numbers.
For \(28\), the literal cost is
$$L(28)=c(2)+c(8)=5+7=12.$$
But \(28=4\times 7\), so
$$P(28)\le L(4)+L(7)+2=4+3+2=9.$$
Thus \(M(28)=9\), already much better than writing 28 directly.
For \(82\), the literal cost is \(7+5=12\), while the additive split \(82=11+71\) gives
$$M(82)\le M(11)+P(71)+2=4+5+2=11.$$
For \(88\), the literal cost is \(14\). A multiplicative form \(88=8\times 11\) gives cost \(7+4+2=13\), but the additive form \(88=11+77\) gives
$$M(88)\le M(11)+P(77)+2=4+6+2=12.$$
These examples show why both multiplication and addition relaxations are needed. As a global checkpoint, summing the optimal values up to \(100\) gives \(S(100)=916\).
The C++, Python, and Java implementations begin by filling an array of literal costs with the decimal recurrence for \(L(n)\). That pass is linear in \(N\) once the digit table is fixed.
Next, they run repeated multiplication relaxations over all pairs \(x\le y\) with \(xy\le N\). Because multiplication is commutative, iterating only over \(x\le y\) avoids duplicate work without missing any product. When this loop reaches a fixed point, the table matches the optimum multiplicative costs \(P(n)\).
After that, the implementation switches to addition. It groups integers by their current matchstick cost, then combines bucket pairs in increasing cost order. Bucket pairs whose candidate cost is already too large are discarded immediately, and within a bucket pair the scan stops as soon as the numeric sum exceeds \(N\). Those two pruning rules remove most of the naive \(O(N^2)\) work.
One implementation also cross-checks the optimized routine against an exact small-limit dynamic program and verifies the checkpoint \(S(100)=916\) before evaluating the full \(N=10^6\) case.
Computing all literal costs takes \(O(N\log_{10}N)\) time and \(O(N)\) memory. One full multiplication sweep costs
$$\sum_{x=1}^{N}\left\lfloor\frac{N}{x}\right\rfloor=O(N\log N).$$
The multiplication phase repeats this sweep until no further decrease occurs; in practice the number of rounds is small.
The addition phase first rebuilds the cost buckets in \(O(N)\) time, then inspects only bucket pairs whose candidate cost can still improve the table and only value pairs whose sum is at most \(N\). Its exact running time is data-dependent: the naive worst case is quadratic, but the implemented pruning makes the real workload much smaller for this problem size. Memory usage stays \(O(N)\) throughout.
Für jede positive ganze Zahl \(n\) sei \(M(n)\) die minimale Anzahl von Streichhölzern, die nötig ist, um einen Ausdruck mit Wert \(n\) darzustellen, wobei Dezimalziffern sowie die Operatoren \(+\) und \(\times\) erlaubt sind. Die Ziffern haben die üblichen Kosten der Sieben-Segment-Anzeige, und jeder Operator kostet zwei zusätzliche Streichhölzer. Gesucht ist
$$S(N)=\sum_{n=1}^{N} M(n),\qquad N=10^6.$$
Der entscheidende Punkt ist, dass man nicht alle Ausdrucksbäume durchsuchen muss. Stattdessen lässt sich das Problem als dynamisches Programm über den Werten \(1,2,\dots,N\) formulieren.
Die Implementierung baut die optimalen Kosten von kleinen Zahlen zu großen Zahlen auf. Jede zulässige Darstellung entsteht aus einer von drei Quellen: direkte Dezimalschreibweise, Produkt kleinerer Werte oder Summe, deren letzter Summand ein multiplikativer Term ist.
Sei \(c(d)\) die Streichholzkosten der Ziffer \(d\). Für die hier verwendete Sieben-Segment-Anzeige gilt
$$c(0)=6,\ c(1)=2,\ c(2)=5,\ c(3)=5,\ c(4)=4,\ c(5)=5,\ c(6)=6,\ c(7)=3,\ c(8)=7,\ c(9)=6.$$
Wird \(n\) direkt als Dezimalzahl geschrieben, so ist seine Literal-Kostenfunktion
$$L(n)=\sum_{i=1}^{k} c(d_i).$$
Der Code berechnet diese Werte effizient mit
$$L(n)=L\!\left(\left\lfloor\frac{n}{10}\right\rfloor\right)+c(n\bmod 10),\qquad L(0)=0.$$
Damit erhält man sofort eine gültige obere Schranke für \(M(n)\), denn die direkte Schreibweise ist immer erlaubt.
Sei \(P(n)\) die minimale Kostenanzahl eines Terms, der nur Dezimalliterale und Multiplikation verwendet und den Wert \(n\) hat. Dann gilt
$$P(n)=\min\!\left(L(n),\ \min_{\substack{d\mid n \\ 2\le d\le \sqrt{n}}}\bigl(P(d)+P(n/d)+2\bigr)\right).$$
Die zusätzlichen \(2\) stammen vom Multiplikationszeichen. Es reicht, nur Divisoren bis \(\sqrt{n}\) zu betrachten, weil Faktorpaare symmetrisch sind.
Diese Rekurrenz ist für rein multiplikative Terme exakt: Jedes Produkt lässt sich an seiner obersten Multiplikation in zwei kleinere multiplikative Unterterme zerlegen, und jede solche Zerlegung liefert wiederum einen gültigen Kandidaten.
Nun sei \(M(n)\) die echte optimale Kostenanzahl für den Wert \(n\). Die Implementierungen behandeln einen vollständigen Ausdruck als Summe multiplikativer Terme. Wählt man den letzten Summanden ab, erhält man
$$M(n)=\min\!\left(P(n),\ \min_{1\le a<n}\bigl(M(a)+P(n-a)+2\bigr)\right).$$
Der linke Teil \(a\) darf bereits ein vollständig optimierter Ausdruck sein, während \(n-a\) den letzten multiplikativen Term bildet. Auch hier stehen die \(+2\) für das Pluszeichen.
Damit wird das ursprüngliche Ausdrucksproblem zu einem Kürzestkostenproblem auf dem Intervall \([1,N]\).
Für kleine Grenzen kann man die Rekurrenzen direkt auswerten. Für \(N=10^6\) startet die optimierte Methode stattdessen mit der Literal-Tabelle und wendet anschließend kostensenkende Relaxationen an.
Für die Multiplikation liefert jedes Paar \(x\le y\) mit \(xy\le N\) den Kandidaten
$$\text{Kosten}(xy)\le \text{Kosten}(x)+\text{Kosten}(y)+2.$$
Wird dieses Update bis zum Stillstand wiederholt, erhält man die unter Multiplikation abgeschlossene Tabelle.
Für die Addition werden Zahlen nach ihren aktuellen Kosten gruppiert:
$$B_t=\{n\le N:\text{Kosten}(n)=t\}.$$
Für \(x\in B_a\) und \(y\in B_b\) hat \(x+y\) den Kandidatenwert \(a+b+2\). Mit
$$C_{\max}=\max_{1\le n\le N}\text{Kosten}(n)$$
kann man alle Bucket-Paare mit \(a+b+2\ge C_{\max}\) sofort verwerfen, weil sie nichts mehr verbessern können. Genau dieses Bucket-Pruning macht die große Rechnung praktikabel.
Alle Updates sind monoton fallend, also „ersetze durch eine kleinere ganze Zahl, falls möglich“. Daher muss das Verfahren irgendwann einen stabilen Fixpunkt erreichen.
An einzelnen Zahlen sieht man die Rekurrenzen besonders gut.
Für \(28\) ist die direkte Schreibweise
$$L(28)=c(2)+c(8)=5+7=12.$$
Da aber \(28=4\times 7\) gilt, erhält man
$$P(28)\le L(4)+L(7)+2=4+3+2=9.$$
Also ist \(M(28)=9\), deutlich besser als das direkte Schreiben von 28.
Für \(82\) beträgt die Literal-Kostenanzahl \(7+5=12\), während die Zerlegung \(82=11+71\) liefert
$$M(82)\le M(11)+P(71)+2=4+5+2=11.$$
Für \(88\) ist die direkte Schreibweise \(14\). Multiplikativ ergibt \(88=8\times 11\) die Kosten \(7+4+2=13\), aber additiv liefert \(88=11+77\)
$$M(88)\le M(11)+P(77)+2=4+6+2=12.$$
Diese Beispiele zeigen, warum sowohl Multiplikations- als auch Additionsrelaxationen nötig sind. Als globaler Kontrollwert gilt außerdem \(S(100)=916\).
Die C++-, Python- und Java-Implementierungen füllen zunächst ein Array der Literal-Kosten mit der Dezimalrekurrenz für \(L(n)\). Dieser Schritt ist bei fester Zifferntabelle linear in \(N\).
Danach folgen wiederholte Multiplikationsrelaxationen über alle Paare \(x\le y\) mit \(xy\le N\). Wegen der Kommutativität der Multiplikation genügt diese halbe Paarmenge, um jede mögliche Produktdarstellung abzudecken. Sobald in einer Runde keine Kosten mehr sinken, entspricht die Tabelle den optimalen multiplikativen Werten \(P(n)\).
Anschließend wechselt die Implementierung zur Addition. Zahlen mit gleichem aktuellem Kostenwert werden gemeinsam betrachtet, Bucket-Paare in aufsteigender Kostenreihenfolge kombiniert und hoffnungslose Paare sofort abgeschnitten. Innerhalb eines Bucket-Paares endet der Scan, sobald die numerische Summe größer als \(N\) wird. Diese beiden Regeln entfernen den größten Teil der naiven \(O(N^2)\)-Arbeit.
Eine Implementierung prüft die schnelle Methode zusätzlich gegen ein exaktes dynamisches Programm für kleine Grenzen und verifiziert den Kontrollwert \(S(100)=916\), bevor der volle Fall \(N=10^6\) gerechnet wird.
Die Berechnung aller Literal-Kosten benötigt \(O(N\log_{10}N)\) Zeit und \(O(N)\) Speicher. Ein kompletter Multiplikationsdurchlauf kostet
$$\sum_{x=1}^{N}\left\lfloor\frac{N}{x}\right\rfloor=O(N\log N).$$
Die Multiplikationsphase wiederholt diesen Durchlauf bis keine Verbesserung mehr auftritt; in der Praxis bleibt die Zahl der Runden klein.
Die Additionsphase baut zuerst die Buckets in \(O(N)\) Zeit auf und untersucht dann nur noch Bucket-Paare, deren Kandidatenkosten überhaupt noch eine Verbesserung zulassen, sowie nur noch Wertepaarungen mit Summe höchstens \(N\). Die exakte Laufzeit ist daher datenabhängig: Der naive Worst Case bleibt quadratisch, aber durch das Pruning ist die tatsächliche Arbeit für diese Problemgröße deutlich kleiner. Der Speicherverbrauch bleibt durchgehend \(O(N)\).
Her pozitif \(n\) tamsayısı için \(M(n)\), ondalık rakamlar ile \(+\) ve \(\times\) işleçleri kullanılarak değeri \(n\) olan bir ifadeyi göstermek için gereken en az kibrit sayısı olsun. Rakamların yedi-segment maliyetleri sabittir ve her işleç iki ek kibrit kullanır. Hesaplanmak istenen büyüklük
$$S(N)=\sum_{n=1}^{N} M(n),\qquad N=10^6.$$
Esas fikir, bütün ifade ağaçlarını tek tek denemek yerine problemi \(1,2,\dots,N\) değerleri üzerinde çalışan bir dinamik programa dönüştürmektir.
Uygulama cevabı küçük sayılardan büyük sayılara doğru kurar. Her aday gösterim üç kaynaktan gelir: \(n\)'yi doğrudan yazmak, \(n\)'yi daha küçük değerlerin çarpımı olarak yazmak veya son terimi çarpımsal olan bir toplam olarak yazmak.
\(c(d)\), rakam \(d\)'nin kibrit maliyeti olsun. Burada kullanılan standart yedi-segment gösterimde
$$c(0)=6,\ c(1)=2,\ c(2)=5,\ c(3)=5,\ c(4)=4,\ c(5)=5,\ c(6)=6,\ c(7)=3,\ c(8)=7,\ c(9)=6.$$
\(n\) sayısı doğrudan ondalık biçimde yazılırsa literal maliyeti
$$L(n)=\sum_{i=1}^{k} c(d_i).$$
olur. Kod bunu şu özyinelemeli bağıntıyla hızlı hesaplar:
$$L(n)=L\!\left(\left\lfloor\frac{n}{10}\right\rfloor\right)+c(n\bmod 10),\qquad L(0)=0.$$
Böylece her \(M(n)\) için hemen geçerli bir üst sınır elde edilir; çünkü doğrudan yazım her zaman mümkündür.
\(P(n)\), yalnızca ondalık sayılar ve çarpma kullanılarak değeri \(n\) olan bir terimin en düşük maliyeti olsun. O zaman
$$P(n)=\min\!\left(L(n),\ \min_{\substack{d\mid n \\ 2\le d\le \sqrt{n}}}\bigl(P(d)+P(n/d)+2\bigr)\right)$$
yazılır. Buradaki ek \(2\), çarpma işaretinin maliyetidir. Çarpan çiftleri simetrik olduğu için yalnızca \(d\le\sqrt{n}\) aralığını taramak yeterlidir.
Bu bağıntı çarpımsal terimler için tamdır: Her ürün en üstteki çarpma noktasından iki küçük çarpımsal alt terime ayrılır ve her böyle ayrım geçerli bir aday üretir.
Şimdi \(M(n)\), değeri \(n\) olan ifadenin gerçek optimum maliyeti olsun. Uygulamalar, tam ifadeyi çarpımsal terimlerin toplamı olarak ele alır. Son terimi ayırınca
$$M(n)=\min\!\left(P(n),\ \min_{1\le a<n}\bigl(M(a)+P(n-a)+2\bigr)\right)$$
elde edilir. Burada soldaki \(a\) parçası zaten tam optimize edilmiş bir ifade olabilir; sağdaki \(n-a\) ise son çarpımsal terimdir. Yine \(+2\), artı işaretinin maliyetidir.
Böylece asıl ifade problemi, \([1,N]\) aralığında bir en düşük maliyetli ayrıştırma problemine dönüşür.
Küçük sınırlar için yukarıdaki bağıntılar doğrudan hesaplanabilir. \(N=10^6\) için ise optimize edilmiş yöntem literal tablosundan başlar ve maliyeti düşüren gevşetmeleri tekrar tekrar uygular.
Çarpma için \(xy\le N\) ve \(x\le y\) olan her çift şu adayı verir:
$$\text{maliyet}(xy)\le \text{maliyet}(x)+\text{maliyet}(y)+2.$$
Bu güncelleme değişim kalmayana kadar sürdürülünce çarpma altında kapanmış tablo elde edilir.
Toplama için sayılar güncel maliyetlerine göre gruplanır:
$$B_t=\{n\le N:\text{maliyet}(n)=t\}.$$
Eğer \(x\in B_a\) ve \(y\in B_b\) ise, \(x+y\) için aday maliyet \(a+b+2\) olur. Ayrıca
$$C_{\max}=\max_{1\le n\le N}\text{maliyet}(n)$$
tanımıyla, \(a+b+2\ge C_{\max}\) olan bucket çiftleri hiçbir şeyi iyileştiremeyeceğinden tamamen atlanır. Büyük durumda işi yapılabilir kılan ana hızlandırma budur.
Bütün güncellemeler “mümkünse daha küçük bir tamsayı ile değiştir” biçimindedir. Dolayısıyla maliyetler monoton azalır ve süreç mutlaka sabit bir noktada durur.
Bağıntılar somut sayılar üzerinde daha açık görünür.
\(28\) için doğrudan yazım maliyeti
$$L(28)=c(2)+c(8)=5+7=12$$
olur. Ama \(28=4\times 7\) olduğundan
$$P(28)\le L(4)+L(7)+2=4+3+2=9.$$
Demek ki \(M(28)=9\) olur; bu da 28'i doğrudan yazmaktan belirgin biçimde daha iyidir.
\(82\) için literal maliyet \(7+5=12\)'dir; buna karşılık \(82=11+71\) ayrımı
$$M(82)\le M(11)+P(71)+2=4+5+2=11$$
verir. \(88\) için doğrudan yazım \(14\) maliyetlidir. Çarpımsal biçim \(88=8\times 11\) ile \(7+4+2=13\) bulunur; fakat toplamsal biçim \(88=11+77\)
$$M(88)\le M(11)+P(77)+2=4+6+2=12$$
sonucunu verir. Bu örnekler, hem çarpma hem toplama gevşetmelerinin neden gerekli olduğunu gösterir. Genel bir kontrol noktası olarak da \(S(100)=916\) elde edilir.
C++, Python ve Java uygulamaları önce \(L(n)\) için ondalık bağıntıyı kullanarak literal maliyet dizisini doldurur. Rakam tablosu sabit olduğundan bu adım \(N\) açısından doğrusaldır.
Sonra \(xy\le N\) ve \(x\le y\) olan tüm çiftler üzerinde çarpma gevşetmeleri tekrar edilir. Çarpmanın değişme özelliği sayesinde yalnızca \(x\le y\) yarısı gezilerek yine de bütün ürünler kapsanır. Artık hiçbir giriş düşmediğinde tablo, en iyi çarpımsal maliyetler \(P(n)\) ile çakışır.
Bundan sonra uygulama toplama aşamasına geçer. Aynı maliyete sahip sayılar birlikte gruplanır, bucket çiftleri artan maliyet sırasıyla birleştirilir ve umut vermeyen çiftler en başta elenir. Bir bucket çifti içindeki tarama da sayısal toplam \(N\)'yi geçtiği anda durur. Bu iki budama kuralı, saf \(O(N^2)\) işin büyük bölümünü ortadan kaldırır.
Bir uygulama ayrıca hızlı yöntemi küçük sınırlar için tam dinamik programla karşılaştırır ve tam \(N=10^6\) hesabına geçmeden önce \(S(100)=916\) kontrolünü yapar.
Tüm literal maliyetlerin hesaplanması \(O(N\log_{10}N)\) zaman ve \(O(N)\) bellek gerektirir. Bir tam çarpma turunun maliyeti
$$\sum_{x=1}^{N}\left\lfloor\frac{N}{x}\right\rfloor=O(N\log N)$$
mertebesindedir. Çarpma aşaması, artık iyileştirme kalmayana kadar bu turu tekrarlar; pratikte tur sayısı küçüktür.
Toplama aşaması önce bucket'ları \(O(N)\) zamanda kurar, sonra yalnızca hâlâ iyileştirme potansiyeli taşıyan bucket çiftlerini ve toplamı en fazla \(N\) olan sayı çiftlerini inceler. Bu yüzden tam çalışma süresi veriye bağlıdır: saf en kötü durum hâlâ kareseldir, fakat uygulanan budama sayesinde gerçek iş yükü bu problem boyutunda çok daha düşüktür. Bellek kullanımı baştan sona \(O(N)\) kalır.
Para cada entero positivo \(n\), sea \(M(n)\) el número mínimo de cerillas necesarias para mostrar una expresión con valor \(n\), usando dígitos decimales y los operadores \(+\) y \(\times\). Los dígitos tienen los costes habituales del display de siete segmentos, y cada operador añade dos cerillas. La cantidad buscada es
$$S(N)=\sum_{n=1}^{N} M(n),\qquad N=10^6.$$
La idea esencial es que no hace falta enumerar todos los árboles de expresiones. El problema puede reescribirse como una programación dinámica sobre los valores \(1,2,\dots,N\).
La implementación construye la respuesta de los valores pequeños a los grandes. Toda representación candidata nace de una de tres fuentes: escribir \(n\) directamente, escribir \(n\) como producto de valores menores, o escribir \(n\) como suma cuyo último sumando es multiplicativo.
Sea \(c(d)\) el coste en cerillas del dígito \(d\). En el display de siete segmentos usado aquí,
$$c(0)=6,\ c(1)=2,\ c(2)=5,\ c(3)=5,\ c(4)=4,\ c(5)=5,\ c(6)=6,\ c(7)=3,\ c(8)=7,\ c(9)=6.$$
Si \(n\) se escribe directamente en decimal, su coste literal es
$$L(n)=\sum_{i=1}^{k} c(d_i).$$
El código calcula esta tabla con la recurrencia
$$L(n)=L\!\left(\left\lfloor\frac{n}{10}\right\rfloor\right)+c(n\bmod 10),\qquad L(0)=0.$$
Esto da una cota superior válida para todo \(M(n)\), porque siempre podemos escribir el número tal cual.
Definimos \(P(n)\) como el coste mínimo de un término que vale \(n\) y usa solo literales decimales y multiplicación. Entonces
$$P(n)=\min\!\left(L(n),\ \min_{\substack{d\mid n \\ 2\le d\le \sqrt{n}}}\bigl(P(d)+P(n/d)+2\bigr)\right).$$
El \(+2\) adicional es el coste del signo de multiplicación. Basta buscar divisores hasta \(\sqrt{n}\) porque los pares de factores son simétricos.
Esta recurrencia es exacta para términos multiplicativos: cualquier producto puede partirse en su multiplicación superior en dos subproductos más pequeños, y cada una de esas particiones produce un candidato válido.
Sea ahora \(M(n)\) el verdadero óptimo para el valor \(n\). Las implementaciones consideran una expresión completa como suma de términos multiplicativos, así que al separar el último sumando obtenemos
$$M(n)=\min\!\left(P(n),\ \min_{1\le a<n}\bigl(M(a)+P(n-a)+2\bigr)\right).$$
La parte izquierda \(a\) puede ser ya una expresión completa optimizada, mientras que \(n-a\) es el último término multiplicativo. De nuevo, el \(+2\) representa el signo más.
Con esta formulación, el problema original se convierte en una descomposición de coste mínimo sobre el intervalo \([1,N]\).
Para límites pequeños, las recurrencias pueden evaluarse directamente. Para \(N=10^6\), el método rápido empieza con la tabla literal y aplica relajaciones que solo pueden reducir costes.
En multiplicación, cada par \(x\le y\) con \(xy\le N\) da el candidato
$$\text{coste}(xy)\le \text{coste}(x)+\text{coste}(y)+2.$$
Al repetir esta actualización hasta que no haya cambios, se obtiene la tabla cerrada bajo multiplicación.
En adición, los enteros se agrupan por coste actual:
$$B_t=\{n\le N:\text{coste}(n)=t\}.$$
Si \(x\in B_a\) y \(y\in B_b\), entonces \(x+y\) tiene coste candidato \(a+b+2\). Si definimos
$$C_{\max}=\max_{1\le n\le N}\text{coste}(n),$$
cualquier par de buckets con \(a+b+2\ge C_{\max}\) puede descartarse de inmediato, porque no mejorará ninguna entrada. Esa poda por buckets es la clave del rendimiento.
Todas las actualizaciones son monótonas decrecientes, así que el proceso necesariamente termina en un punto fijo estable.
Las fórmulas se entienden mejor con algunos valores concretos.
Para \(28\), el coste literal es
$$L(28)=c(2)+c(8)=5+7=12.$$
Pero como \(28=4\times 7\), tenemos
$$P(28)\le L(4)+L(7)+2=4+3+2=9.$$
Por tanto \(M(28)=9\), mucho mejor que escribir 28 directamente.
Para \(82\), el coste literal es \(7+5=12\), mientras que la descomposición \(82=11+71\) da
$$M(82)\le M(11)+P(71)+2=4+5+2=11.$$
Para \(88\), la escritura directa cuesta \(14\). Una forma multiplicativa \(88=8\times 11\) cuesta \(7+4+2=13\), pero la forma aditiva \(88=11+77\) da
$$M(88)\le M(11)+P(77)+2=4+6+2=12.$$
Estos ejemplos muestran por qué hacen falta tanto las relajaciones multiplicativas como las aditivas. Como comprobación global, además se obtiene \(S(100)=916\).
Las implementaciones en C++, Python y Java comienzan llenando un arreglo de costes literales mediante la recurrencia decimal de \(L(n)\). Una vez fijada la tabla de dígitos, ese paso es lineal en \(N\).
Después ejecutan relajaciones multiplicativas repetidas sobre todos los pares \(x\le y\) con \(xy\le N\). Como la multiplicación es conmutativa, recorrer solo la mitad de los pares evita trabajo duplicado sin perder ningún producto. Cuando una pasada completa ya no reduce ninguna entrada, la tabla coincide con los costes multiplicativos óptimos \(P(n)\).
A continuación llega la fase aditiva. Los números con el mismo coste actual se agrupan, los pares de buckets se recorren en orden creciente de coste y los pares imposibles de mejorar se descartan al instante. Dentro de un par de buckets, el barrido también se detiene cuando la suma numérica supera \(N\). Esas dos podas eliminan la mayor parte del trabajo naive de \(O(N^2)\).
Una implementación también contrasta la rutina rápida con una programación dinámica exacta para límites pequeños y verifica el punto de control \(S(100)=916\) antes de evaluar el caso completo \(N=10^6\).
Calcular todos los costes literales requiere \(O(N\log_{10}N)\) tiempo y \(O(N)\) memoria. Una pasada completa de multiplicación cuesta
$$\sum_{x=1}^{N}\left\lfloor\frac{N}{x}\right\rfloor=O(N\log N).$$
La fase multiplicativa repite esa pasada hasta llegar al punto fijo; en la práctica, el número de rondas es pequeño.
La fase aditiva reconstruye primero los buckets en \(O(N)\) y luego examina solo los pares de buckets cuyo coste candidato todavía puede mejorar la tabla y solo los pares de valores cuya suma es como máximo \(N\). Su tiempo exacto depende de los datos: el peor caso ingenuo sigue siendo cuadrático, pero la poda implementada reduce mucho el trabajo real para este tamaño de entrada. El uso de memoria permanece en \(O(N)\).
对每个正整数 \(n\)，记 \(M(n)\) 为用十进制数字以及运算符 \(+\) 和 \(\times\) 写出一个值为 \(n\) 的表达式所需的最少火柴数。数字的代价由标准七段数码管决定，而每个运算符额外消耗两根火柴。题目要求计算
$$S(N)=\sum_{n=1}^{N} M(n),\qquad N=10^6.$$
关键点在于，不必暴力枚举所有表达式树。这个问题可以转化为在整数 \(1,2,\dots,N\) 上做最小代价动态规划。
实现方式是从小整数一路推到大整数。每个候选表示都来自三种来源之一：直接把 \(n\) 写成十进制、把 \(n\) 写成更小数的乘积，或者把 \(n\) 写成一个和，而最后一项是乘法项。
设 \(c(d)\) 表示数字 \(d\) 的火柴代价。在这里使用的标准七段显示中，
$$c(0)=6,\ c(1)=2,\ c(2)=5,\ c(3)=5,\ c(4)=4,\ c(5)=5,\ c(6)=6,\ c(7)=3,\ c(8)=7,\ c(9)=6.$$
如果把 \(n\) 直接按十进制写出来，那么它的字面量代价是
$$L(n)=\sum_{i=1}^{k} c(d_i).$$
代码用下面的递推式高效计算整张表：
$$L(n)=L\!\left(\left\lfloor\frac{n}{10}\right\rfloor\right)+c(n\bmod 10),\qquad L(0)=0.$$
这样一来，每个 \(M(n)\) 一开始就有一个合法上界，因为“直接写出来”永远是可行方案。
定义 \(P(n)\) 为“只允许十进制字面量和乘法”的情况下，表示数值 \(n\) 的最小火柴数。那么有
$$P(n)=\min\!\left(L(n),\ \min_{\substack{d\mid n \\ 2\le d\le \sqrt{n}}}\bigl(P(d)+P(n/d)+2\bigr)\right).$$
这里额外的 \(2\) 是乘号的代价。因为因子对是对称的，所以只需要枚举到 \(\sqrt{n}\)。
这个递推对纯乘法项是精确的：任意乘积都可以在最外层乘号处分成两个更小的乘法子项，而每一种这样的拆分都会给出一个合法候选。
现在令 \(M(n)\) 表示数值 \(n\) 的真正最优代价。实现采用的结构是“完整表达式由若干乘法项相加而成”，因此把最后一项拆出来后可得
$$M(n)=\min\!\left(P(n),\ \min_{1\le a<n}\bigl(M(a)+P(n-a)+2\bigr)\right).$$
这里左边的 \(a\) 可以已经是一个完全优化过的表达式，而右边的 \(n-a\) 是最后一个乘法项。式中的 \(+2\) 对应加号的代价。
这样，原题就变成了区间 \([1,N]\) 上的最小代价分解问题。
对于小范围，可以直接按上面的递推式计算。对于 \(N=10^6\)，优化后的算法从字面量表出发，不断做只会降低代价的松弛更新。
在乘法阶段，任意满足 \(x\le y\) 且 \(xy\le N\) 的数对都会产生候选
$$\text{cost}(xy)\le \text{cost}(x)+\text{cost}(y)+2.$$
把这个更新反复执行到没有任何条目继续下降为止，就得到对乘法封闭的代价表。
在加法阶段，先按当前代价把整数分桶：
$$B_t=\{n\le N:\text{cost}(n)=t\}.$$
若 \(x\in B_a\) 且 \(y\in B_b\)，则 \(x+y\) 的候选代价是 \(a+b+2\)。再记
$$C_{\max}=\max_{1\le n\le N}\text{cost}(n).$$
只要 \(a+b+2\ge C_{\max}\)，这个桶对就不可能改进任何值，因此可以整组跳过。正是这种“按代价分桶并提前剪枝”的策略，使得大规模计算成为可能。
所有更新都只可能把某个整数代价改小，不会改大，所以整个过程是单调下降的，最终一定停在稳定的不动点上。
看几个具体数字，递推关系会更直观。
对 \(28\) 而言，直接写成十进制的代价为
$$L(28)=c(2)+c(8)=5+7=12.$$
但因为 \(28=4\times 7\)，所以
$$P(28)\le L(4)+L(7)+2=4+3+2=9.$$
因此 \(M(28)=9\)，明显优于直接写出 28。
对 \(82\)，字面量代价是 \(7+5=12\)，而拆成 \(82=11+71\) 后有
$$M(82)\le M(11)+P(71)+2=4+5+2=11.$$
对 \(88\)，直接写的代价是 \(14\)。乘法形式 \(88=8\times 11\) 的代价为 \(7+4+2=13\)，但加法形式 \(88=11+77\) 给出
$$M(88)\le M(11)+P(77)+2=4+6+2=12.$$
这些例子说明，乘法松弛和加法松弛都不可缺少。作为整体校验，还可得到 \(S(100)=916\)。
C++、Python 和 Java 实现都会先用 \(L(n)\) 的十进制递推式填满字面量代价数组。因为数字代价表是固定的，这一步对 \(N\) 来说是线性的。
随后程序对所有满足 \(x\le y\) 且 \(xy\le N\) 的数对反复做乘法松弛。由于乘法满足交换律，只遍历 \(x\le y\) 这一半就足以覆盖全部乘积形式，而且不会重复太多工作。当一整轮下来再也没有条目下降时，这张表就已经等于最优乘法代价 \(P(n)\)。
接着进入加法阶段。程序把当前代价相同的整数放进同一个桶里，按桶成本从小到大组合，并立即丢弃那些候选成本已经不可能更优的桶对。在一个桶对内部，只要数值和超过 \(N\)，扫描也会立刻停止。这两条剪枝规则去掉了朴素 \(O(N^2)\) 枚举中的绝大部分工作。
其中一个实现还会在小范围上用精确动态规划交叉验证快速算法，并在真正计算 \(N=10^6\) 之前检查基准值 \(S(100)=916\)。
计算全部字面量代价需要 \(O(N\log_{10}N)\) 时间和 \(O(N)\) 空间。一次完整的乘法扫描成本为
$$\sum_{x=1}^{N}\left\lfloor\frac{N}{x}\right\rfloor=O(N\log N).$$
乘法阶段会重复这类扫描，直到代价表稳定；在实际数据上，轮数很少。
加法阶段先用 \(O(N)\) 时间重建所有代价桶，然后只考察那些候选成本仍有希望改进答案的桶对，以及数值和不超过 \(N\) 的整数对。它的精确运行时间取决于数据分布：朴素最坏情况仍然是二次的，但这里的分桶和剪枝使实际工作量远小于全量平方枚举。整个过程中空间复杂度始终为 \(O(N)\)。
Для каждого положительного целого \(n\) обозначим через \(M(n)\) минимальное число спичек, необходимое для записи выражения со значением \(n\), если разрешены десятичные цифры и операции \(+\) и \(\times\). Стоимость цифр задается стандартным семисегментным индикатором, а каждый оператор добавляет две спички. Требуется вычислить
$$S(N)=\sum_{n=1}^{N} M(n),\qquad N=10^6.$$
Главное наблюдение состоит в том, что не нужно перебирать все деревья выражений. Задача сводится к динамическому программированию по значениям \(1,2,\dots,N\).
Реализация строит ответ снизу вверх. Любое кандидатное представление возникает из одного из трех источников: непосредственная десятичная запись числа, произведение меньших значений или сумма, у которой последний член является мультипликативным термом.
Пусть \(c(d)\) обозначает стоимость цифры \(d\) в спичках. Для используемого здесь семисегментного дисплея имеем
$$c(0)=6,\ c(1)=2,\ c(2)=5,\ c(3)=5,\ c(4)=4,\ c(5)=5,\ c(6)=6,\ c(7)=3,\ c(8)=7,\ c(9)=6.$$
Если число \(n\) записано напрямую в десятичном виде, его стоимость равна
$$L(n)=\sum_{i=1}^{k} c(d_i).$$
Код вычисляет эту таблицу по рекуррентной формуле
$$L(n)=L\!\left(\left\lfloor\frac{n}{10}\right\rfloor\right)+c(n\bmod 10),\qquad L(0)=0.$$
Тем самым для каждого \(M(n)\) сразу получается корректная верхняя граница, потому что прямая запись числа всегда допустима.
Обозначим через \(P(n)\) минимальную стоимость терма, который равен \(n\) и использует только десятичные литералы и умножение. Тогда
$$P(n)=\min\!\left(L(n),\ \min_{\substack{d\mid n \\ 2\le d\le \sqrt{n}}}\bigl(P(d)+P(n/d)+2\bigr)\right).$$
Дополнительное \(2\) — это стоимость знака умножения. Достаточно просматривать делители до \(\sqrt{n}\), потому что пары множителей симметричны.
Эта рекурсия точна для чисто мультипликативных термов: любое произведение можно разрезать по верхнему умножению на два меньших подтерма, и каждый такой разрез дает допустимого кандидата.
Теперь пусть \(M(n)\) — настоящий оптимум для значения \(n\). Реализация рассматривает полное выражение как сумму мультипликативных термов. Если отделить последний член, получаем
$$M(n)=\min\!\left(P(n),\ \min_{1\le a<n}\bigl(M(a)+P(n-a)+2\bigr)\right).$$
Левая часть \(a\) уже может быть полностью оптимизированным выражением, а \(n-a\) является последним мультипликативным термом. Как и раньше, \(+2\) соответствует знаку сложения.
Так исходная задача об выражениях превращается в задачу о разложении с минимальной стоимостью на отрезке \([1,N]\).
Для малых границ рекурсии можно вычислять напрямую. Для \(N=10^6\) быстрый метод стартует с таблицы литералов и затем многократно применяет релаксации, которые могут только уменьшать стоимость.
На шаге умножения каждая пара \(x\le y\) при \(xy\le N\) дает кандидат
$$\text{cost}(xy)\le \text{cost}(x)+\text{cost}(y)+2.$$
Если повторять это обновление до тех пор, пока ни одна запись больше не уменьшается, получится таблица, замкнутая относительно умножения.
На шаге сложения целые числа группируются по текущей стоимости:
$$B_t=\{n\le N:\text{cost}(n)=t\}.$$
Если \(x\in B_a\) и \(y\in B_b\), то для \(x+y\) кандидатная стоимость равна \(a+b+2\). Обозначив
$$C_{\max}=\max_{1\le n\le N}\text{cost}(n),$$
можно сразу отбросить все пары корзин с \(a+b+2\ge C_{\max}\), потому что они уже не улучшат ни одной записи. Именно такое отсечение по корзинам делает большой расчет выполнимым.
Все обновления имеют вид «замени на меньшее целое, если получилось лучше», поэтому процесс монотонно убывает и обязательно заканчивается в устойчивой фиксированной точке.
На конкретных числах рекурсии видны особенно ясно.
Для \(28\) прямая десятичная запись стоит
$$L(28)=c(2)+c(8)=5+7=12.$$
Но так как \(28=4\times 7\), получаем
$$P(28)\le L(4)+L(7)+2=4+3+2=9.$$
Следовательно, \(M(28)=9\), что существенно лучше прямой записи 28.
Для \(82\) буквальная стоимость равна \(7+5=12\), а разложение \(82=11+71\) дает
$$M(82)\le M(11)+P(71)+2=4+5+2=11.$$
Для \(88\) непосредственная запись стоит \(14\). Мультипликативная форма \(88=8\times 11\) имеет стоимость \(7+4+2=13\), но аддитивная форма \(88=11+77\) дает
$$M(88)\le M(11)+P(77)+2=4+6+2=12.$$
Эти примеры показывают, почему нужны и мультипликативные, и аддитивные релаксации. В качестве общей контрольной точки получается также \(S(100)=916\).
Реализации на C++, Python и Java сначала заполняют массив буквальных стоимостей по десятичной рекурсии для \(L(n)\). При фиксированной таблице цифр этот этап линеен по \(N\).
Затем многократно выполняются мультипликативные релаксации по всем парам \(x\le y\) с условием \(xy\le N\). Из-за коммутативности умножения достаточно рассматривать только половину пар, не теряя ни одного произведения. Когда полный проход перестает уменьшать значения, таблица совпадает с оптимальными мультипликативными стоимостями \(P(n)\).
После этого начинается аддитивная фаза. Числа с одинаковой текущей стоимостью собираются вместе, пары корзин перебираются в порядке возрастания стоимости, а безнадежные пары отсекаются сразу. Внутри пары корзин перебор прекращается, как только числовая сумма превышает \(N\). Эти два правила снимают основную часть наивной работы порядка \(O(N^2)\).
Одна из реализаций дополнительно сверяет быстрый метод с точной динамикой на малых границах и проверяет контрольное значение \(S(100)=916\) перед вычислением полного случая \(N=10^6\).
Вычисление всех буквальных стоимостей требует \(O(N\log_{10}N)\) времени и \(O(N)\) памяти. Один полный мультипликативный проход стоит
$$\sum_{x=1}^{N}\left\lfloor\frac{N}{x}\right\rfloor=O(N\log N).$$
Мультипликативная фаза повторяет такой проход до стабилизации таблицы; на практике число раундов невелико.
Аддитивная фаза сначала перестраивает корзины за \(O(N)\), а затем рассматривает только те пары корзин, чья кандидатная стоимость еще может улучшить ответ, и только те пары значений, чья сумма не превосходит \(N\). Поэтому точное время работы зависит от распределения данных: наивный худший случай остается квадратичным, но используемое отсечение сильно уменьшает реальный объем вычислений для данной размерности. Память во всем алгоритме остается \(O(N)\).
لكل عدد صحيح موجب \(n\)، نرمز بـ \(M(n)\) إلى أقل عدد من أعواد الثقاب اللازمة لعرض تعبير قيمته \(n\)، باستعمال الأرقام العشرية والعمليتين \(+\) و\(\times\). كلفة كل رقم مأخوذة من شاشة سباعية المقاطع القياسية، وكل عامل حسابي يضيف عودين إضافيين. المطلوب هو حساب
$$S(N)=\sum_{n=1}^{N} M(n),\qquad N=10^6.$$
الفكرة الأساسية هي أنه لا حاجة إلى تعداد جميع أشجار التعابير. يمكن تحويل المسألة إلى برمجة ديناميكية على القيم \(1,2,\dots,N\).
يبني التنفيذ الجواب من الأعداد الصغيرة إلى الكبيرة. كل تمثيل مرشح يأتي من واحد من ثلاثة مصادر: كتابة \(n\) مباشرة، أو كتابة \(n\) كحاصل ضرب لقيم أصغر، أو كتابة \(n\) كمجموع يكون حده الأخير حدًا ضربيًا.
لتكن \(c(d)\) هي كلفة الرقم \(d\) بعدد الأعواد. في الشاشة السباعية المستخدمة هنا لدينا
$$c(0)=6,\ c(1)=2,\ c(2)=5,\ c(3)=5,\ c(4)=4,\ c(5)=5,\ c(6)=6,\ c(7)=3,\ c(8)=7,\ c(9)=6.$$
إذا كُتب العدد \(n\) مباشرة بصيغته العشرية فتكلفته هي
$$L(n)=\sum_{i=1}^{k} c(d_i).$$
ويحسب الكود هذه القيم بسرعة بواسطة العلاقة
$$L(n)=L\!\left(\left\lfloor\frac{n}{10}\right\rfloor\right)+c(n\bmod 10),\qquad L(0)=0.$$
وهذا يعطي حدًا أعلى صحيحًا لكل \(M(n)\)، لأن الكتابة المباشرة متاحة دائمًا.
لنعرّف \(P(n)\) بأنه أقل كلفة لحد يساوي \(n\) ويستخدم فقط الأعداد العشرية والضرب. عندئذٍ
$$P(n)=\min\!\left(L(n),\ \min_{\substack{d\mid n \\ 2\le d\le \sqrt{n}}}\bigl(P(d)+P(n/d)+2\bigr)\right).$$
الزيادة \(2\) هي كلفة علامة الضرب. ويكفي فحص القواسم حتى \(\sqrt{n}\) لأن أزواج العوامل متناظرة.
هذه العلاقة دقيقة تمامًا للحدود الضربية: فكل حاصل ضرب يمكن قطعه عند أعلى عملية ضرب إلى حدين ضربيين أصغر، وكل هذا التقسيم يولد مرشحًا صالحًا.
الآن ليكن \(M(n)\) هو الحل الأمثل الحقيقي للقيمة \(n\). تتعامل التطبيقات مع التعبير الكامل على أنه مجموع حدود ضربية، ولذلك إذا فصلنا الحد الأخير نحصل على
$$M(n)=\min\!\left(P(n),\ \min_{1\le a<n}\bigl(M(a)+P(n-a)+2\bigr)\right).$$
الجزء الأيسر \(a\) قد يكون تعبيرًا كاملًا محسّنًا بالفعل، بينما \(n-a\) هو الحد الضربي الأخير. أما \(+2\) فهي كلفة علامة الجمع.
بهذا تتحول المسألة الأصلية إلى مسألة تفكيك بأقل كلفة على المجال \([1,N]\).
للحدود الصغيرة يمكن تقييم العلاقات السابقة مباشرة. أما عندما \(N=10^6\)، فالطريقة السريعة تبدأ من جدول الكتابة المباشرة ثم تطبق إرخاءات لا يمكن إلا أن تُنقص الكلفة.
في مرحلة الضرب، كل زوج \(x\le y\) مع \(xy\le N\) يعطي المرشح
$$\text{cost}(xy)\le \text{cost}(x)+\text{cost}(y)+2.$$
وعند تكرار هذا التحديث حتى يتوقف أي انخفاض جديد نحصل على جدول مغلق تحت الضرب.
في مرحلة الجمع، تُجمع الأعداد حسب كلفتها الحالية:
$$B_t=\{n\le N:\text{cost}(n)=t\}.$$
إذا كان \(x\in B_a\) و\(y\in B_b\)، فالكلفة المرشحة للعدد \(x+y\) هي \(a+b+2\). وإذا عرّفنا
$$C_{\max}=\max_{1\le n\le N}\text{cost}(n),$$
فإن أي زوج من المجموعات يحقق \(a+b+2\ge C_{\max}\) لا يمكنه تحسين أي قيمة، ولذلك يُهمل مباشرة. هذا التقليم بحسب الكلفة هو سبب قابلية الحساب الكبير للتنفيذ.
جميع التحديثات من نوع "استبدل القيمة بقيمة صحيحة أصغر إن أمكن"، لذلك تسير العملية في اتجاه تنازلي أحادي وتنتهي حتمًا عند نقطة ثابتة مستقرة.
تظهر العلاقات أوضح عندما ننظر إلى أعداد محددة.
بالنسبة إلى \(28\)، فإن كلفة الكتابة المباشرة هي
$$L(28)=c(2)+c(8)=5+7=12.$$
لكن بما أن \(28=4\times 7\)، فإننا نحصل على
$$P(28)\le L(4)+L(7)+2=4+3+2=9.$$
إذًا \(M(28)=9\)، وهو أفضل بكثير من كتابة 28 مباشرة.
أما \(82\)، فكلفته المباشرة \(7+5=12\)، في حين أن التفكيك \(82=11+71\) يعطي
$$M(82)\le M(11)+P(71)+2=4+5+2=11.$$
وبالنسبة إلى \(88\)، فالكلفة المباشرة هي \(14\). الصيغة الضربية \(88=8\times 11\) تعطي \(7+4+2=13\)، لكن الصيغة الجمعية \(88=11+77\) تعطي
$$M(88)\le M(11)+P(77)+2=4+6+2=12.$$
توضح هذه الأمثلة لماذا نحتاج إلى إرخاءات الضرب والجمع معًا. وكاختبار عام، نحصل أيضًا على \(S(100)=916\).
تبدأ تطبيقات C++ وPython وJava بملء مصفوفة كلف الكتابة المباشرة باستخدام العلاقة العشرية الخاصة بـ \(L(n)\). ومع ثبات جدول الأرقام تكون هذه الخطوة خطية في \(N\).
بعد ذلك تُنفَّذ إرخاءات الضرب مرارًا على جميع الأزواج \(x\le y\) التي تحقق \(xy\le N\). وبما أن الضرب تبديلي، فإن الاكتفاء بالنصف \(x\le y\) يغطي جميع صور الضرب من دون تكرار غير لازم. وعندما تمر دورة كاملة بلا أي انخفاض جديد، تصبح المصفوفة مساوية للكلف الضربية المثلى \(P(n)\).
ثم تأتي مرحلة الجمع. تُجمع الأعداد ذات الكلفة الحالية نفسها في المجموعات نفسها، وتُفحَص أزواج المجموعات بترتيب تصاعدي للكلفة، وتُقصى الأزواج التي لم تعد قادرة على التحسين فورًا. وداخل كل زوج من المجموعات يتوقف الفحص حالما يتجاوز المجموع العددي \(N\). هاتان القاعدتان تزيلان معظم العمل الساذج ذي الكلفة \(O(N^2)\).
كما أن أحد التطبيقات يقارن الطريقة السريعة ببرمجة ديناميكية دقيقة على حدود صغيرة، ويتحقق من القيمة المرجعية \(S(100)=916\) قبل حساب الحالة الكاملة \(N=10^6\).
حساب جميع كلف الكتابة المباشرة يحتاج إلى زمن \(O(N\log_{10}N)\) وذاكرة \(O(N)\). أما كلفة دورة ضرب كاملة فهي
$$\sum_{x=1}^{N}\left\lfloor\frac{N}{x}\right\rfloor=O(N\log N).$$
وتكرر مرحلة الضرب هذه الدورة حتى تثبت المصفوفة؛ وعمليًا يبقى عدد الدورات صغيرًا.
مرحلة الجمع تعيد أولًا بناء مجموعات الكلفة في \(O(N)\)، ثم تفحص فقط أزواج المجموعات التي ما زالت قادرة على تحسين الجواب، وفقط أزواج القيم التي لا يتجاوز مجموعها \(N\). لذلك فإن زمنها الدقيق يعتمد على توزع البيانات: أسوأ حالة ساذجة ما تزال تربيعية، لكن التقليم المطبق يخفض العمل الفعلي كثيرًا لهذا الحجم من المسألة. ويظل استهلاك الذاكرة \(O(N)\) طوال التنفيذ.