For each integer \(k\) with \(1 \le k \le 200\), let \(m(k)\) be the smallest number of multiplications needed to build \(a^k\) starting from \(a\), when every new power must be obtained by multiplying two powers that are already available. The problem asks for the total
$$\sum_{k=1}^{200} m(k).$$
If we track exponents instead of powers, each multiplication turns known exponents \(x\) and \(y\) into the new exponent \(x+y\). The question is therefore an addition-chain problem: how short can a chain ending at \(k\) be?
An addition chain for \(k\) is a sequence
$$1=a_0<a_1<\cdots<a_r=k,$$
where every later term is obtained from earlier ones by
$$a_t=a_i+a_j \qquad (0 \le i,j < t).$$
The length \(r\) is exactly the number of multiplications, so \(m(k)\) is the minimum possible length.
The implementations restrict the search to star chains, also called Brauer chains, where each new exponent must use the current largest exponent:
$$a_{t+1}=a_t+a_i \qquad (0 \le i \le t).$$
This models the move “take the newest available power and multiply it by one earlier power”. Because all chain elements are positive, every new term is larger than the previous one, so the chain stays strictly increasing automatically.
For the range required here, that restricted search space is enough: every exponent \(k \le 200\) attains its true minimum inside the star-chain search, so filling the table for all \(k\) gives the values demanded by the problem.
Fix a depth limit \(d\). A depth-limited DFS can enumerate every star chain of length at most \(d\). If some target \(k\) appears during that sweep, then \(k\) has a chain of length \(d\) or less.
The search is repeated for
$$d=1,2,3,\dots,$$
so the first depth at which \(k\) becomes reachable is its minimal length inside the searched family of chains. The code does not solve one target at a time; instead, one global pass keeps improving a table of best-known lengths for all intermediate exponents that appear anywhere in the search tree.
Suppose the current chain reaches an exponent \(n\) at depth \(d\). If the table already contains a shorter route to \(n\), then exploring from this occurrence cannot improve \(m(n)\). That is why the search prunes whenever
$$d > \text{best}(n).$$
This bound is monotone: once a value is stored in the best table, it can only stay the same or decrease. Every recursive call therefore uses the strongest information found so far.
Notice that branches with \(d=\text{best}(n)\) are still explored. Two different chains can reach the same exponent with the same length, but their later extensions can differ. Keeping equal-depth alternatives matters because one such branch may lead to a shorter chain for a larger target.
A concrete chain for \(15\) is
$$1,2,3,6,12,15.$$
Interpreted as powers, this means
$$a^2=a\cdot a,\quad a^3=a^2\cdot a,\quad a^6=a^3\cdot a^3,\quad a^{12}=a^6\cdot a^6,\quad a^{15}=a^{12}\cdot a^3.$$
So \(m(15)\le 5\). The depth-by-depth search proves optimality: the full depth-4 sweep finds no chain ending at \(15\), while the depth-5 sweep does. Therefore
$$m(15)=5.$$
This same argument is applied simultaneously to every \(k \le 200\), and the final result is the sum of all these minimal lengths.
The C++, Python, and Java implementations create an array of best-known multiplication counts for the exponents \(1\) through \(200\). The entry for \(1\) is initialized to \(0\), while all other entries start as “unknown”. The current chain starts as the one-term chain \([1]\).
Next comes iterative deepening. For each allowed depth, the implementation performs a DFS that takes the last exponent in the current chain and combines it with each earlier exponent, from larger addends to smaller ones. Every candidate
$$n=a_t+a_i$$
is ignored if \(n>200\). Otherwise, the table is updated when the new chain is shorter than the best one known so far for \(n\).
After recording a candidate, the DFS recurses on the extended chain and then removes that last term again on the way back up the recursion. In this way the search explores the whole tree of possibilities while storing only the current path. After each depth sweep, the code checks whether every exponent up to \(200\) now has a finite value. As soon as that is true, the search stops and the program adds the table entries.
All three language versions implement the same mathematical idea: iterative deepening over star chains, a global best-depth table for pruning, and a final summation over the completed table.
Exact addition-chain search is exponential in the maximum depth being explored. At depth \(t\), there are at most \(t+1\) choices for the addend paired with the current largest exponent, so the raw search tree grows very quickly as the allowed depth increases.
For this Project Euler instance the constants are small. The target range ends at \(200\), the search stops as soon as every value has been reached, and the best-known table removes many branches that cannot improve anything. Memory usage is modest: \(O(200)\) for the best table plus \(O(D)\) for the current chain and recursion stack, where \(D\) is the deepest chain length actually explored.
Für jede ganze Zahl \(k\) mit \(1 \le k \le 200\) sei \(m(k)\) die kleinste Anzahl von Multiplikationen, die nötig ist, um ausgehend von \(a\) die Potenz \(a^k\) zu erzeugen, wobei jede neue Potenz als Produkt zweier bereits bekannter Potenzen entstehen muss. Gesucht ist die Summe
$$\sum_{k=1}^{200} m(k).$$
Betrachtet man statt der Potenzen nur ihre Exponenten, dann verwandelt jede Multiplikation zwei bekannte Exponenten \(x\) und \(y\) in den neuen Exponenten \(x+y\). Damit wird die Aufgabe zu einem Problem über Additionsketten: Wie kurz kann eine Kette sein, die bei \(k\) endet?
Eine Additionskette für \(k\) ist eine Folge
$$1=a_0<a_1<\cdots<a_r=k,$$
bei der jeder spätere Term aus früheren Termen entsteht durch
$$a_t=a_i+a_j \qquad (0 \le i,j < t).$$
Die Länge \(r\) ist genau die Anzahl der Multiplikationen, also ist \(m(k)\) die minimale mögliche Länge.
Die Implementierungen durchsuchen nicht alle Additionsketten, sondern nur Sternketten, auch Brauer-Ketten genannt. Dort muss jeder neue Exponent den aktuell größten Exponenten verwenden:
$$a_{t+1}=a_t+a_i \qquad (0 \le i \le t).$$
Das modelliert genau den Schritt „nimm die zuletzt erzeugte Potenz und multipliziere sie mit einer früheren Potenz“. Da alle Kettenglieder positiv sind, ist jeder neue Term automatisch größer als der vorige; die Kette bleibt also streng wachsend.
Für den hier benötigten Bereich reicht dieser eingeschränkte Suchraum aus: Jeder Exponent \(k \le 200\) erreicht sein wahres Minimum bereits innerhalb der Sternkettensuche, sodass die vollständig gefüllte Tabelle genau die verlangten Werte liefert.
Fixiere eine Tiefengrenze \(d\). Eine tiefenbeschränkte Tiefensuche kann dann jede Sternkette der Länge höchstens \(d\) aufzählen. Wenn dabei ein Zielwert \(k\) auftaucht, besitzt \(k\) also eine Kette der Länge \(d\) oder kürzer.
Die Suche wird für
$$d=1,2,3,\dots$$
wiederholt. Daher ist genau die erste Tiefe, in der \(k\) erreichbar wird, seine minimale Länge innerhalb der durchsuchten Kettenfamilie. Der Code behandelt die Ziele nicht einzeln, sondern verbessert in einem einzigen globalen Durchlauf ständig die aktuell besten bekannten Längen aller Zwischenexponenten.
Angenommen, die aktuelle Kette erreicht einen Exponenten \(n\) in Tiefe \(d\). Wenn die Tabelle bereits einen kürzeren Weg zu \(n\) enthält, dann kann diese Verzweigung den Wert \(m(n)\) nicht mehr verbessern. Deshalb wird genau dann abgeschnitten, wenn
$$d > \text{best}(n).$$
Diese Schranke ist monoton: Ein einmal gespeicherter Tabellenwert kann nur gleich bleiben oder kleiner werden, niemals größer. Jede rekursive Fortsetzung arbeitet also mit den stärksten bisher bekannten Informationen.
Zweige mit \(d=\text{best}(n)\) bleiben jedoch erhalten. Zwei verschiedene Ketten können denselben Zwischenexponenten mit derselben Länge erreichen, aber ihre späteren Fortsetzungen können unterschiedlich sein. Genau deshalb dürfen gleich gute Alternativen nicht verworfen werden; eine davon kann für ein größeres Ziel noch entscheidend sein.
Eine konkrete Kette für \(15\) ist
$$1,2,3,6,12,15.$$
Als Potenzen gelesen bedeutet das
$$a^2=a\cdot a,\quad a^3=a^2\cdot a,\quad a^6=a^3\cdot a^3,\quad a^{12}=a^6\cdot a^6,\quad a^{15}=a^{12}\cdot a^3.$$
Also gilt \(m(15)\le 5\). Die iterative Tiefensuche zeigt, dass dies optimal ist: Die vollständige Suche bis Tiefe \(4\) findet keine Kette mit Endwert \(15\), die Suche bis Tiefe \(5\) dagegen schon. Folglich
$$m(15)=5.$$
Dasselbe Argument wird gleichzeitig auf alle \(k \le 200\) angewendet, und am Ende wird über alle Minimalwerte summiert.
Die Implementierungen in C++, Python und Java legen zunächst ein Feld mit den besten bekannten Multiplikationszahlen für die Exponenten \(1\) bis \(200\) an. Der Eintrag für \(1\) wird auf \(0\) gesetzt, alle anderen Einträge starten als „unbekannt“. Die aktuelle Kette beginnt mit \([1]\).
Danach folgt iterative Vertiefung. Für jede erlaubte Tiefe führt die Implementierung eine Tiefensuche aus, die den letzten Exponenten der aktuellen Kette mit jedem früheren Exponenten kombiniert, und zwar von großen zu kleinen Summanden. Jeder Kandidat
$$n=a_t+a_i$$
wird ignoriert, falls \(n>200\) ist. Andernfalls wird die Tabelle aktualisiert, wenn die neue Kette kürzer ist als der bisher beste bekannte Weg zu \(n\).
Nach dem Eintragen eines Kandidaten ruft sich die Suche rekursiv mit der erweiterten Kette auf und entfernt den letzten Term beim Zurückkehren wieder. So wird der gesamte Suchbaum durchlaufen, ohne mehr als den aktuellen Pfad speichern zu müssen. Nach jeder Tiefenrunde prüft der Code, ob inzwischen jeder Exponent bis \(200\) einen endlichen Wert besitzt. Sobald das der Fall ist, endet die Suche und die Tabellenwerte werden addiert.
Alle drei Sprachversionen setzen dieselbe mathematische Idee um: iterative Vertiefung über Sternketten, Beschneidung über eine globale Bestentabelle und am Ende die Summation über die vollständig gefüllte Tabelle.
Die exakte Suche nach Additionsketten ist exponentiell in der maximal untersuchten Tiefe. In Tiefe \(t\) gibt es höchstens \(t+1\) Möglichkeiten für den Summanden, der mit dem aktuell größten Exponenten kombiniert wird; deshalb wächst der rohe Suchbaum mit zunehmender Tiefe sehr schnell.
Für diese konkrete Aufgabe bleiben die Konstanten klein. Der Zielbereich endet bei \(200\), die Suche stoppt sofort, sobald alle Werte erreicht wurden, und die Bestentabelle schneidet viele Zweige ab, die nichts mehr verbessern können. Der Speicherbedarf ist gering: \(O(200)\) für die Tabelle plus \(O(D)\) für die aktuelle Kette und den Rekursionsstapel, wobei \(D\) die tatsächlich erreichte Suchtiefe bezeichnet.
\(1 \le k \le 200\) olmak üzere her \(k\) için, \(m(k)\) değeri \(a\) sayısından başlayarak \(a^k\) elde etmek için gereken en az çarpma sayısı olsun. Burada her yeni kuvvet, daha önce elde edilmiş iki kuvvetin çarpımı olmak zorundadır. Sorunun istediği toplam
$$\sum_{k=1}^{200} m(k)$$
ifadesidir.
Kuvvetlerin kendisi yerine üsleri izlersek, her çarpma iki bilinen üssü \(x\) ve \(y\) alıp yeni üs \(x+y\) üretir. Bu nedenle soru doğrudan bir toplama zinciri sorusuna dönüşür: \(k\) ile biten en kısa zincir nedir?
\(k\) için bir toplama zinciri
$$1=a_0<a_1<\cdots<a_r=k$$
şeklinde artan bir dizidir ve her sonraki terim
$$a_t=a_i+a_j \qquad (0 \le i,j < t)$$
biçiminde daha önceki iki terimin toplamı olarak elde edilir. Uzunluk \(r\), tam olarak çarpma sayısıdır; dolayısıyla \(m(k)\) mümkün olan en küçük uzunluktur.
Uygulamalar bütün toplama zincirlerini değil, yalnızca yıldız zincirleri ya da Brauer zincirleri denen alt aileyi tarar. Bu ailede her yeni üs, mevcut en büyük üssü kullanmak zorundadır:
$$a_{t+1}=a_t+a_i \qquad (0 \le i \le t).$$
Bu, “en son elde edilen kuvveti al ve onu daha eski kuvvetlerden biriyle çarp” hamlesini tam olarak modeller. Bütün zincir terimleri pozitif olduğundan, her yeni terim bir öncekinden otomatik olarak büyüktür; yani zincir zaten sıkı biçimde artandır.
Bu soruda gereken aralık için bu kısıtlı arama uzayı yeterlidir: \(k \le 200\) olan her üs gerçek minimumuna yıldız zinciri araması içinde ulaşır. Bu yüzden tabloyu tamamen doldurmak, problemde istenen \(m(k)\) değerlerini verir.
Bir derinlik sınırı \(d\) sabitleyelim. Derinlik sınırlı bir DFS, uzunluğu en çok \(d\) olan bütün yıldız zincirlerini dolaşabilir. Eğer bu tur sırasında bir hedef \(k\) görünüyorsa, demek ki \(k\) için uzunluğu \(d\) veya daha kısa bir zincir vardır.
Arama
$$d=1,2,3,\dots$$
için tekrarlandığından, \(k\)'nin ilk kez ulaşıldığı derinlik, taranan zincir ailesi içindeki en küçük uzunluktur. Kod her hedefi ayrı çözmez; bunun yerine arama ağacında görülen bütün ara üsler için en iyi bilinen uzunlukları tek bir küresel tabloda sürekli iyileştirir.
Varsayalım ki mevcut zincir, \(n\) üssüne \(d\) derinliğinde ulaşıyor. Eğer tabloda \(n\) için zaten daha kısa bir yol varsa, bu daldan devam etmek \(m(n)\) değerini iyileştiremez. Bu yüzden budama koşulu
$$d > \text{best}(n)$$
şeklindedir. Bu sınır tek yönlüdür: tabloya yazılan bir değer ancak aynı kalabilir ya da küçülebilir, büyümez. Böylece her özyineli çağrı, o ana kadar bulunmuş en güçlü üst sınırları kullanır.
Buna karşılık \(d=\text{best}(n)\) olan dallar korunur. Aynı ara üsse aynı sayıda adımda ulaşan iki farklı zincir, daha sonra farklı biçimlerde genişleyebilir. Bu eşit derinlikli alternatifleri tutmak önemlidir; çünkü bunlardan biri daha büyük bir hedef için daha kısa bir yol açabilir.
\(15\) için somut bir zincir
$$1,2,3,6,12,15$$
şeklindedir. Kuvvetler cinsinden bu zincir
$$a^2=a\cdot a,\quad a^3=a^2\cdot a,\quad a^6=a^3\cdot a^3,\quad a^{12}=a^6\cdot a^6,\quad a^{15}=a^{12}\cdot a^3$$
anlamına gelir. Dolayısıyla \(m(15)\le 5\).
Yinelemeli derinleştirme bunun gerçekten optimal olduğunu gösterir: derinlik \(4\) için yapılan tam aramada \(15\)'e ulaşan bir zincir çıkmaz, fakat derinlik \(5\) taramasında çıkar. O halde
$$m(15)=5.$$
Aynı mantık eşzamanlı olarak bütün \(k \le 200\) için uygulanır ve son cevap bu minimum uzunlukların toplamıdır.
C++, Python ve Java uygulamaları önce \(1\) ile \(200\) arasındaki üsler için en iyi bilinen çarpma sayılarını tutan bir dizi oluşturur. \(1\) için değer \(0\) yapılır; diğer bütün girişler başlangıçta “bilinmiyor” durumundadır. Mevcut zincir de \([1]\) olarak başlar.
Sonra yinelemeli derinleştirme gelir. Her izin verilen derinlikte uygulama, zincirin son üssünü daha önceki her üs ile birleştiren bir DFS yürütür; toplama yapılırken büyük eklerden küçüklere doğru gidilir. Her aday
$$n=a_t+a_i$$
için, eğer \(n>200\) ise dal atılır. Aksi halde yeni zincir daha kısaysa tabloda \(n\) için tutulan en iyi değer güncellenir.
Bir aday kaydedildikten sonra arama genişletilmiş zincirle özyineli olarak devam eder ve geri dönerken son terim silinir. Böylece bütün olasılık ağacı gezilirken yalnızca mevcut yol bellekte tutulur. Her derinlik turundan sonra kod, \(200\)'e kadar olan bütün üslerin artık sonlu bir değere sahip olup olmadığını kontrol eder. Bu koşul sağlanır sağlanmaz arama durur ve tablo toplanır.
Üç dildeki sürümler aynı matematiksel fikri uygular: yıldız zincirleri üzerinde yinelemeli derinleştirme, küresel en-iyi-derinlik tablosu ile budama ve sonunda tamamlanmış tablonun toplanması.
Kesin toplama zinciri araması, incelenen en büyük derinliğe göre üstel davranır. Derinlik \(t\) iken, mevcut en büyük üs ile eşlenecek ek için en fazla \(t+1\) seçenek vardır; bu nedenle ham arama ağacı derinlik arttıkça çok hızlı büyür.
Bu Project Euler örneğinde sabitler küçüktür. Hedef aralık \(200\)'de biter, bütün değerler bulunur bulunmaz arama sona erer ve en iyi değer tablosu işe yaramayacak çok sayıda dalı erken keser. Bellek kullanımı düşüktür: tablo için \(O(200)\), mevcut zincir ve özyineleme yığını için de \(O(D)\); burada \(D\) gerçekte taranan en derin zincir uzunluğudur.
Para cada entero \(k\) con \(1 \le k \le 200\), sea \(m(k)\) el menor número de multiplicaciones necesarias para construir \(a^k\) a partir de \(a\), suponiendo que cada nueva potencia debe obtenerse multiplicando dos potencias ya disponibles. El problema pide la suma
$$\sum_{k=1}^{200} m(k).$$
Si en vez de seguir las potencias seguimos solo sus exponentes, cada multiplicación convierte dos exponentes conocidos \(x\) y \(y\) en el nuevo exponente \(x+y\). Por eso la pregunta es exactamente una cuestión de cadenas de suma: ¿qué longitud mínima puede tener una cadena que termine en \(k\)?
Una cadena de suma para \(k\) es una sucesión
$$1=a_0<a_1<\cdots<a_r=k,$$
en la que cada término posterior se obtiene a partir de términos anteriores mediante
$$a_t=a_i+a_j \qquad (0 \le i,j < t).$$
La longitud \(r\) coincide exactamente con el número de multiplicaciones, así que \(m(k)\) es la menor longitud posible.
Las implementaciones no recorren todas las cadenas de suma, sino solo las cadenas estrella, también llamadas cadenas de Brauer. En ellas, cada nuevo exponente debe usar el mayor exponente actual:
$$a_{t+1}=a_t+a_i \qquad (0 \le i \le t).$$
Eso modela exactamente la operación “toma la potencia más reciente y multiplícala por una potencia anterior”. Como todos los términos de la cadena son positivos, cada nuevo término es automáticamente mayor que el anterior, de modo que la cadena permanece estrictamente creciente.
Para el rango que interesa aquí, ese espacio de búsqueda restringido basta: cada exponente \(k \le 200\) alcanza su mínimo real dentro de la búsqueda por cadenas estrella, así que completar la tabla produce exactamente los valores exigidos por el problema.
Fijemos un límite de profundidad \(d\). Un DFS limitado por profundidad puede enumerar todas las cadenas estrella de longitud a lo sumo \(d\). Si durante ese barrido aparece un objetivo \(k\), entonces \(k\) tiene una cadena de longitud \(d\) o menor.
La búsqueda se repite para
$$d=1,2,3,\dots,$$
así que la primera profundidad en la que \(k\) se vuelve alcanzable es su longitud mínima dentro de la familia de cadenas explorada. El código no resuelve un objetivo cada vez; una sola exploración global va mejorando una tabla con las mejores longitudes conocidas para todos los exponentes intermedios que van apareciendo.
Supongamos que la cadena actual alcanza un exponente \(n\) en profundidad \(d\). Si la tabla ya contiene una ruta más corta hacia \(n\), entonces continuar desde esta aparición no puede mejorar \(m(n)\). Por eso se poda siempre que
$$d > \text{best}(n).$$
Esta cota es monótona: una vez guardado un valor en la tabla, solo puede mantenerse o disminuir, nunca aumentar. Cada llamada recursiva usa por tanto la mejor información disponible en ese momento.
Sin embargo, las ramas con \(d=\text{best}(n)\) se conservan. Dos cadenas distintas pueden llegar al mismo exponente con la misma longitud, pero sus extensiones futuras pueden diferir. Mantener esas alternativas de igual profundidad es importante porque una de ellas puede abrir una ruta más corta hacia un objetivo mayor.
Una cadena concreta para \(15\) es
$$1,2,3,6,12,15.$$
Leída como potencias, significa
$$a^2=a\cdot a,\quad a^3=a^2\cdot a,\quad a^6=a^3\cdot a^3,\quad a^{12}=a^6\cdot a^6,\quad a^{15}=a^{12}\cdot a^3.$$
Así que \(m(15)\le 5\). La búsqueda por profundización iterativa demuestra que esto es óptimo: el barrido completo con profundidad \(4\) no encuentra ninguna cadena que termine en \(15\), mientras que el barrido con profundidad \(5\) sí la encuentra. En consecuencia,
$$m(15)=5.$$
El mismo razonamiento se aplica simultáneamente a todos los \(k \le 200\), y el resultado final es la suma de todas esas longitudes mínimas.
Las implementaciones en C++, Python y Java crean primero un arreglo con el mejor número conocido de multiplicaciones para los exponentes \(1\) a \(200\). La entrada correspondiente a \(1\) se fija en \(0\), y todas las demás empiezan como “desconocidas”. La cadena actual arranca como \([1]\).
Después viene la profundización iterativa. Para cada profundidad permitida, la implementación ejecuta un DFS que toma el último exponente de la cadena actual y lo combina con cada exponente anterior, desde los sumandos más grandes hasta los más pequeños. Cada candidato
$$n=a_t+a_i$$
se descarta si \(n>200\). En caso contrario, la tabla se actualiza cuando la nueva cadena es más corta que la mejor conocida hasta ese momento para \(n\).
Tras registrar un candidato, el DFS continúa recursivamente con la cadena extendida y luego elimina ese último término al regresar. De ese modo se recorre todo el árbol de posibilidades almacenando solo la ruta actual. Al terminar cada barrido de profundidad, el código comprueba si todos los exponentes hasta \(200\) ya tienen un valor finito. En cuanto eso ocurre, la búsqueda se detiene y el programa suma la tabla.
Las tres versiones implementan la misma idea matemática: profundización iterativa sobre cadenas estrella, poda mediante una tabla global de mejores profundidades y, al final, la suma sobre la tabla completada.
La búsqueda exacta de cadenas de suma es exponencial en la profundidad máxima explorada. En profundidad \(t\), hay como mucho \(t+1\) opciones para el sumando que se combina con el mayor exponente actual, así que el árbol bruto de búsqueda crece muy deprisa a medida que aumenta la profundidad permitida.
En esta instancia de Project Euler las constantes son pequeñas. El rango objetivo termina en \(200\), la búsqueda se detiene en cuanto todos los valores han sido alcanzados y la tabla global de mejores resultados elimina muchas ramas que ya no pueden mejorar nada. El uso de memoria es modesto: \(O(200)\) para la tabla y \(O(D)\) para la cadena actual y la pila recursiva, donde \(D\) es la profundidad máxima realmente explorada.
对每个满足 \(1 \le k \le 200\) 的整数 \(k\)，记 \(m(k)\) 为从 \(a\) 出发构造 \(a^k\) 所需的最少乘法次数，其中每一个新幂都必须通过两个已经得到的幂相乘而来。题目要求计算总和
$$\sum_{k=1}^{200} m(k).$$
如果不去跟踪幂本身，而只跟踪指数，那么每次乘法都会把两个已知指数 \(x\) 和 \(y\) 变成新指数 \(x+y\)。因此，这道题本质上就是一道加法链问题：以 \(k\) 结尾的最短链有多短？
\(k\) 的一条加法链是一个严格递增序列
$$1=a_0<a_1<\cdots<a_r=k,$$
并且每个后继项都满足
$$a_t=a_i+a_j \qquad (0 \le i,j < t).$$
长度 \(r\) 恰好就是乘法次数，所以 \(m(k)\) 就是所有可能长度中的最小值。
实现并没有枚举所有加法链，而是只搜索一种更窄的子类：星形链，也常被称为 Brauer 链。在这种链中，每一个新指数都必须使用当前最大的指数：
$$a_{t+1}=a_t+a_i \qquad (0 \le i \le t).$$
这正好对应“拿最新得到的幂，再乘上一个更早得到的幂”这一操作。由于链中的所有项都是正数，所以新项一定严格大于前一项，整条链天然保持递增。
对本题要求的范围来说，这个受限的搜索空间已经足够：每个 \(k \le 200\) 的真实最优值都能在星形链搜索中出现，因此只要把整张表填满，就得到了题目真正要求的 \(m(k)\)。
先固定一个深度上限 \(d\)。在这个上限下做深度优先搜索，就可以枚举所有长度不超过 \(d\) 的星形链。如果在这次搜索中某个目标 \(k\) 出现了，就说明 \(k\) 至少有一条长度不超过 \(d\) 的链。
然后把搜索按
$$d=1,2,3,\dots$$
逐层增加。于是，某个目标 \(k\) 第一次变得可达的深度，就是它在这类链中的最小长度。代码并不是把每个目标分开求解，而是在一次全局搜索中不断更新“目前已知的最短长度表”，凡是搜索树里出现过的中间指数，都会尝试用更短的深度去刷新这张表。
假设当前链在深度 \(d\) 到达了某个指数 \(n\)。如果表里已经记录了一个更短的到达方式，那么从这一次出现继续往下扩展，就不可能改进 \(m(n)\)。因此剪枝条件就是
$$d > \text{best}(n).$$
这个界是单调的：表中一旦写入某个值，它只可能保持不变或者继续减小，不会反过来变大。所以每一次递归调用，使用的都是截至当前所知道的最强上界。
但如果 \(d=\text{best}(n)\)，分支仍然要保留。原因是：两条不同的链可以用同样的长度到达同一个中间指数，可是它们后续还能延伸出的候选链并不一定相同。保留这些“同样好”的分支是必要的，因为其中一条也许会为更大的目标带来更短的最终链。
\(15\) 的一条具体链是
$$1,2,3,6,12,15.$$
把它翻译回幂运算，就是
$$a^2=a\cdot a,\quad a^3=a^2\cdot a,\quad a^6=a^3\cdot a^3,\quad a^{12}=a^6\cdot a^6,\quad a^{15}=a^{12}\cdot a^3.$$
因此 \(m(15)\le 5\)。而迭代加深搜索又证明了这已经是最优值：完整的深度 \(4\) 搜索找不到任何以 \(15\) 结尾的链，到了深度 \(5\) 才第一次找到，所以
$$m(15)=5.$$
同样的逻辑会同时作用于所有 \(k \le 200\)，最后再把这些最小长度全部相加。
C++、Python 和 Java 三个实现都会先建立一个长度为 \(201\) 的表，用来记录指数 \(1\) 到 \(200\) 的当前最优乘法次数。其中 \(1\) 对应的值初始化为 \(0\)，其他位置起初都视为“未知”。当前链从单元素链 \([1]\) 开始。
接下来进行迭代加深。对每一个允许的深度，程序都会执行一次 DFS：取出当前链的最后一个指数，再把它和链中更早出现的每一个指数相加，并且优先尝试较大的加数。每个候选值
$$n=a_t+a_i$$
如果超过 \(200\) 就直接忽略；否则，只要这条新链比当前记录更短，就更新表中的最优值。
记录完一个候选值之后，DFS 会带着扩展后的链继续递归；回溯时再把最后加入的那一项删除。这样就能在只保存当前路径的前提下，完整遍历整棵搜索树。每完成一轮固定深度的搜索后，代码都会检查 \(200\) 以内的所有指数是否都已经拥有有限值。一旦条件满足，搜索立刻停止，然后把整张表求和。
三种语言版本实现的核心数学完全一致：都使用星形链上的迭代加深，用全局最优深度表进行剪枝，最后对完整表格做一次求和。
精确求解加法链本质上是一个随最大搜索深度呈指数增长的问题。在深度 \(t\) 时，与当前最大指数配对的加数最多有 \(t+1\) 种选择，因此原始搜索树会随着允许深度的增加而迅速膨胀。
不过在这道 Project Euler 题里，常数规模很小。目标范围只到 \(200\)，所有值一旦全部被覆盖搜索就会停止，而全局最优表又会提前剪掉大量不可能再带来改进的分支。空间复杂度也很温和：最优值表需要 \(O(200)\)，当前链和递归栈需要 \(O(D)\)，其中 \(D\) 是实际探索到的最大链长。
Для каждого целого \(k\) при \(1 \le k \le 200\) обозначим через \(m(k)\) минимальное число умножений, необходимое для построения \(a^k\), начиная с \(a\), если каждая новая степень должна получаться как произведение двух уже имеющихся степеней. Требуется найти сумму
$$\sum_{k=1}^{200} m(k).$$
Если следить не за самими степенями, а только за показателями, то каждое умножение превращает два известных показателя \(x\) и \(y\) в новый показатель \(x+y\). Значит, задача в точности сводится к задаче о цепочках сложения: насколько короткой может быть цепочка, оканчивающаяся в \(k\)?
Цепочка сложения для числа \(k\) — это строго возрастающая последовательность
$$1=a_0<a_1<\cdots<a_r=k,$$
в которой каждый следующий член выражается через предыдущие по формуле
$$a_t=a_i+a_j \qquad (0 \le i,j < t).$$
Длина \(r\) в точности равна числу умножений, поэтому \(m(k)\) — это минимально возможная длина.
Реализации перебирают не все цепочки сложения, а только звёздные цепочки, также называемые цепочками Брауэра. В такой цепочке каждый новый показатель обязан использовать текущий наибольший показатель:
$$a_{t+1}=a_t+a_i \qquad (0 \le i \le t).$$
Это в точности соответствует ходу «взять самую свежую степень и умножить её на одну из более ранних степеней». Поскольку все элементы цепочки положительны, каждый новый член автоматически больше предыдущего, и цепочка остаётся строго возрастающей.
Для диапазона, который нужен в этой задаче, такого ограниченного пространства поиска достаточно: для каждого \(k \le 200\) истинный минимум достигается уже среди звёздных цепочек. Поэтому после заполнения всей таблицы мы получаем именно те значения \(m(k)\), которые и нужны в задаче.
Зафиксируем ограничение глубины \(d\). Поиск в глубину с этим пределом способен перечислить все звёздные цепочки длины не больше \(d\). Если при таком обходе появляется целевое значение \(k\), значит, для \(k\) существует цепочка длины \(d\) или меньше.
Далее поиск повторяется для
$$d=1,2,3,\dots,$$
поэтому первая глубина, на которой \(k\) становится достижимым, и есть его минимальная длина внутри рассматриваемого семейства цепочек. Код не решает цели по одной; вместо этого один глобальный проход постоянно улучшает таблицу лучших известных длин для всех промежуточных показателей, которые встречаются в дереве поиска.
Пусть текущая цепочка достигает показателя \(n\) на глубине \(d\). Если в таблице уже есть более короткий путь к \(n\), то продолжение из этого состояния не сможет улучшить \(m(n)\). Именно поэтому ветвь отсекается, когда
$$d > \text{best}(n).$$
Эта граница монотонна: записанное в таблицу значение может только сохраниться или уменьшиться, но не вырасти. Следовательно, каждый рекурсивный вызов использует самую сильную из уже найденных оценок.
При этом ветви с \(d=\text{best}(n)\) сохраняются. Две разные цепочки могут прийти к одному и тому же промежуточному показателю за одинаковое число шагов, но их последующие расширения могут различаться. Сохранять такие равноглубинные альтернативы важно, потому что одна из них может дать более короткий путь к большему целевому значению.
Одна конкретная цепочка для \(15\) имеет вид
$$1,2,3,6,12,15.$$
Если перевести её обратно в степени, получаем
$$a^2=a\cdot a,\quad a^3=a^2\cdot a,\quad a^6=a^3\cdot a^3,\quad a^{12}=a^6\cdot a^6,\quad a^{15}=a^{12}\cdot a^3.$$
Значит, \(m(15)\le 5\). Итеративное углубление доказывает, что это оптимум: полный перебор на глубине \(4\) не находит цепочку, оканчивающуюся в \(15\), а на глубине \(5\) такая цепочка появляется. Следовательно,
$$m(15)=5.$$
Точно такая же логика одновременно применяется ко всем \(k \le 200\), а итоговый ответ получается суммированием всех минимальных длин.
Реализации на C++, Python и Java сначала создают массив лучших известных чисел умножений для показателей от \(1\) до \(200\). Для \(1\) записывается значение \(0\), а все остальные позиции сначала считаются неизвестными. Текущая цепочка начинается с \([1]\).
Дальше запускается итеративное углубление. Для каждой разрешённой глубины выполняется поиск в глубину, который берёт последний показатель текущей цепочки и комбинирует его с каждым более ранним показателем, перебирая большие слагаемые раньше маленьких. Каждый кандидат
$$n=a_t+a_i$$
отбрасывается, если \(n>200\). Иначе таблица обновляется, когда новая цепочка оказывается короче лучшей из уже найденных для \(n\).
После фиксации кандидата поиск рекурсивно продолжается с расширенной цепочкой, а при возврате последний член удаляется. Благодаря этому перебирается всё дерево возможностей, но в памяти хранится только текущий путь. После каждого прохода с фиксированной глубиной код проверяет, получили ли уже все показатели до \(200\) конечное значение. Как только это становится верно, поиск останавливается и таблица суммируется.
Во всех трёх языковых версиях используется одна и та же математическая идея: итеративное углубление по звёздным цепочкам, отсечение по глобальной таблице лучших глубин и финальное суммирование по заполненной таблице.
Точный поиск цепочек сложения экспоненциален по максимальной исследуемой глубине. На глубине \(t\) существует не более \(t+1\) вариантов слагаемого, которое можно прибавить к текущему наибольшему показателю, поэтому необрезанное дерево поиска растёт очень быстро.
В этой задаче Project Euler константы невелики. Диапазон целей заканчивается на \(200\), поиск прекращается сразу после того, как все значения покрыты, а глобальная таблица лучших результатов заранее убирает многие бесполезные ветви. Память требуется умеренная: \(O(200)\) для таблицы и \(O(D)\) для текущей цепочки и рекурсивного стека, где \(D\) — максимальная реально исследованная глубина.
لكل عدد صحيح \(k\) بحيث \(1 \le k \le 200\)، نرمز بـ \(m(k)\) إلى أقل عدد من عمليات الضرب اللازمة لبناء \(a^k\) انطلاقًا من \(a\)، مع الشرط أن كل قوة جديدة يجب أن تنتج من ضرب قوتين تم الحصول عليهما سابقًا. المطلوب هو حساب المجموع
$$\sum_{k=1}^{200} m(k).$$
إذا تتبعنا الأسس بدلًا من القوى نفسها، فإن كل عملية ضرب تحوّل أسين معروفين \(x\) و\(y\) إلى الأس الجديد \(x+y\). لذلك تصبح المسألة في جوهرها مسألة سلسلة إضافة: ما أقصر سلسلة يمكن أن تنتهي عند \(k\)؟
سلسلة الإضافة للعدد \(k\) هي متتالية متزايدة تمامًا من الشكل
$$1=a_0<a_1<\cdots<a_r=k,$$
بحيث يتحقق لكل حد لاحق أن
$$a_t=a_i+a_j \qquad (0 \le i,j < t).$$
والطول \(r\) يساوي بالضبط عدد عمليات الضرب، لذلك فإن \(m(k)\) هو أصغر طول ممكن.
التنفيذات لا تستعرض جميع سلاسل الإضافة، بل تقتصر على فئة أضيق هي السلاسل النجمية أو ما يسمى أيضًا سلاسل براور. في هذه الفئة يجب أن يستخدم كل أس جديد أكبر أس موجود حاليًا:
$$a_{t+1}=a_t+a_i \qquad (0 \le i \le t).$$
وهذا يطابق تمامًا خطوة "خذ أحدث قوة متاحة واضربها في قوة أقدم". وبما أن جميع حدود السلسلة موجبة، فإن كل حد جديد يكون أكبر تلقائيًا من الحد السابق، ولذلك تبقى السلسلة متزايدة على نحو صارم.
ضمن المجال المطلوب في هذه المسألة، يكفي هذا الفضاء المقيد من البحث: فكل \(k \le 200\) يصل إلى قيمته المثلى الحقيقية داخل البحث على السلاسل النجمية، وبالتالي فإن ملء الجدول بالكامل يعطي القيم \(m(k)\) التي يطلبها السؤال فعلًا.
لنثبت حدًا للعمق مقداره \(d\). عندئذ يستطيع بحث عمق-أول محدود العمق أن يستعرض جميع السلاسل النجمية ذات الطول الذي لا يتجاوز \(d\). فإذا ظهر هدف معيّن \(k\) أثناء هذا المرور، فهذا يعني أن \(k\) يملك سلسلة بطول \(d\) أو أقل.
ثم يعاد البحث للقيم
$$d=1,2,3,\dots,$$
ولذلك فإن أول عمق يصبح عنده \(k\) قابلًا للوصول هو طوله الأدنى داخل فئة السلاسل التي يجري فحصها. الشيفرة لا تحل كل هدف على حدة، بل تقوم عملية بحث عالمية واحدة بتحديث جدول يحفظ أفضل الأطوال المعروفة لكل الأسس الوسيطة التي تظهر في شجرة البحث.
افترض أن السلسلة الحالية تصل إلى الأس \(n\) عند العمق \(d\). إذا كان الجدول يحتوي مسبقًا على طريق أقصر إلى \(n\)، فإن مواصلة التوسع من هذا الفرع لا يمكن أن تحسن \(m(n)\). ولهذا يكون شرط التقليم هو
$$d > \text{best}(n).$$
وهذا القيد أحادي الاتجاه: فالقيمة المخزنة في الجدول لا يمكن إلا أن تبقى كما هي أو تنخفض، ولا يمكن أن تزداد. لذلك تستخدم كل نداءات الاستدعاء الذاتي أقوى حد معروف حتى تلك اللحظة.
أما الفروع التي تحقق \(d=\text{best}(n)\) فلا تُحذف. فقد تصل سلسلتان مختلفتان إلى الأس الوسيط نفسه بالطول نفسه، لكن امتداداتهما اللاحقة قد تختلف. والاحتفاظ بهذه البدائل المتساوية في العمق مهم، لأن أحدها قد يقود لاحقًا إلى سلسلة أقصر لهدف أكبر.
إحدى السلاسل الملموسة للعدد \(15\) هي
$$1,2,3,6,12,15.$$
وعند تفسيرها على مستوى القوى نحصل على
$$a^2=a\cdot a,\quad a^3=a^2\cdot a,\quad a^6=a^3\cdot a^3,\quad a^{12}=a^6\cdot a^6,\quad a^{15}=a^{12}\cdot a^3.$$
إذن \(m(15)\le 5\). ويبرهن البحث بالتعميق التكراري أن هذا هو الأمثل فعلًا: فالمسح الكامل عند العمق \(4\) لا يجد أي سلسلة تنتهي عند \(15\)، بينما يظهر ذلك لأول مرة عند العمق \(5\). ومن ثم
$$m(15)=5.$$
والمنطق نفسه يطبَّق في الوقت نفسه على جميع القيم \(k \le 200\)، ثم يُحسب الجواب النهائي بجمع هذه الأطوال الدنيا كلها.
تبدأ التنفيذات في C++ وPython وJava بإنشاء مصفوفة تحفظ أفضل عدد معروف من عمليات الضرب للأسس من \(1\) إلى \(200\). تُضبط القيمة الموافقة لـ \(1\) على \(0\)، بينما تبدأ بقية القيم على أنها "غير معروفة". أما السلسلة الحالية فتبدأ بالسلسلة ذات العنصر الواحد \([1]\).
بعد ذلك يبدأ التعميق التكراري. عند كل عمق مسموح، تنفّذ الشيفرة بحثًا عمق-أول يأخذ آخر أس في السلسلة الحالية ويجمعه مع كل أس سابق، مع تجربة المجاميع الأكبر أولًا. وكل مرشح من الشكل
$$n=a_t+a_i$$
يُهمَل إذا كان \(n>200\). وإلا فإن الجدول يُحدَّث متى ما كانت السلسلة الجديدة أقصر من أفضل سلسلة معروفة حتى الآن للوصول إلى \(n\).
بعد تسجيل المرشح، يتابع البحث بشكل عودي باستخدام السلسلة الممتدة، ثم يحذف الحد الأخير عند الرجوع. وبهذا تُستكشف شجرة الاحتمالات كاملة مع الاحتفاظ بالمسار الحالي فقط في الذاكرة. وبعد كل جولة عند عمق ثابت، تتحقق الشيفرة مما إذا كانت جميع الأسس حتى \(200\) قد حصلت على قيم منتهية. وما إن يتحقق ذلك حتى يتوقف البحث وتُجمع قيم الجدول.
تطبّق النسخ الثلاث الفكرة الرياضية نفسها: تعميق تكراري فوق السلاسل النجمية، وتقليم باستعمال جدول عالمي لأفضل الأعماق، ثم جمع نهائي على الجدول بعد اكتماله.
البحث الدقيق عن سلاسل الإضافة يتصرف أسّيًا بالنسبة إلى أكبر عمق يجري فحصه. فعند العمق \(t\)، يوجد على الأكثر \(t+1\) اختيارات للحد الذي سيُجمع مع أكبر أس حالي، ولهذا تنمو شجرة البحث الخام بسرعة كبيرة كلما ازداد العمق المسموح.
لكن ثوابت هذه المسألة من Project Euler صغيرة. فمجال الأهداف ينتهي عند \(200\)، ويتوقف البحث فور تغطية جميع القيم، كما أن جدول أفضل القيم يحذف مبكرًا عددًا كبيرًا من الفروع التي لن تعطي أي تحسين إضافي. أما الذاكرة المطلوبة فمتواضعة: \(O(200)\) للجدول و\(O(D)\) للسلسلة الحالية ولمكدس الاستدعاء، حيث يمثل \(D\) أعمق طول سلسلة جرى استكشافه فعلًا.