Start with a positive integer \(n\), replace it by the sum of the squares of its decimal digits, and repeat. This produces a chain $$n,\ \sigma(n),\ \sigma(\sigma(n)),\dots,$$ where $$\sigma(n)=\sum (\text{decimal digit})^2.$$ For all starting values in this problem, the chain eventually reaches either the fixed point \(1\) or the loop $$89 \to 145 \to 42 \to 20 \to 4 \to 16 \to 37 \to 58 \to 89.$$ The goal is to count how many starting numbers satisfy \(1 \le n \lt 10^7\) and end in the \(89\)-loop.
The important observation is that the chain dynamics collapse very quickly. Even though there are almost ten million starting values, after one digit-square step every chain has already fallen into a tiny finite state space. The whole problem is therefore a classification problem on that reduced space.
The implementations are built around a single reduction: instead of reasoning about all numbers below \(10^7\) separately, classify the possible values of the digit-square map and then reuse those classifications for every starting value.
Define $$\sigma(n)=\sum_{r=0}^{k-1} d_r^2,$$ where \(d_0,d_1,\dots,d_{k-1}\) are the decimal digits of \(n\). Repeated application of \(\sigma\) gives a deterministic sequence, so each starting value lies on a path in a finite functional graph once the values become small enough.
For this problem, the only two outcomes that matter are: $$1 \to 1$$ and the \(89\)-cycle shown above. It is convenient to encode the result of a chain by a terminal-label function $$E(n)\in\{1,89\},$$ meaning that \(E(n)=1\) if the chain starting at \(n\) reaches \(1\), and \(E(n)=89\) if it reaches the \(89\)-cycle.
Every starting value satisfies \(n \lt 10^7\), so it has at most 7 decimal digits. The largest possible digit-square sum is therefore obtained when every digit is \(9\): $$\sigma(n)\le 7\cdot 9^2=7\cdot 81=567.$$ This means that after a single application of \(\sigma\), every chain has entered the set $$S=\{1,2,\dots,567\}.$$ That is the decisive compression step in the problem.
The set \(S\) is also closed under further applications of \(\sigma\). Indeed, any \(m\in S\) has at most 3 digits, so $$\sigma(m)\le 3\cdot 9^2=243 \lt 567.$$ Once a chain enters \(S\), it never leaves. So the infinite-looking process is actually governed by a functional graph on only 567 states.
On the reduced state space, the classification obeys the simple recurrence $$E(1)=1,\qquad E(89)=89,\qquad E(m)=E(\sigma(m))\text{ for }m\notin\{1,89\}.$$ This formula is exactly what the implementations evaluate. If the fate of \(\sigma(m)\) is already known, then the fate of \(m\) is identical. Memoization turns that recurrence into an efficient lookup process: once a reduced state has been classified, every future chain that reaches it is resolved immediately.
A second way to justify termination is numerical descent. If \(n\) has \(d\) digits, then \(n\ge 10^{d-1}\) while \(\sigma(n)\le 81d\). For \(d\ge 4\), one has \(81d \lt 10^{d-1}\), so \(\sigma(n)\lt n\). Thus sufficiently large numbers strictly decrease after one step, and in the present problem all starting values drop into \(S\) immediately anyway.
The chain for \(44\) is $$44 \to 4^2+4^2=32 \to 3^2+2^2=13 \to 1^2+3^2=10 \to 1.$$ Hence \(E(44)=1\).
A more informative example uses the largest possible reduced state. Since $$\sigma(9{,}999{,}999)=7\cdot 81=567,$$ we can continue from there: $$567 \to 110 \to 2 \to 4 \to 16 \to 37 \to 58 \to 89.$$ So any starting value whose first digit-square sum is \(567\) is automatically counted as a chain ending at \(89\).
Once \(E(m)\) has been determined for every \(m\in S\), the answer is simply $$\#\{1\le n \lt 10^7 : E(\sigma(n))=89\}.$$ That is the exact quantity accumulated by the efficient implementations. The key economy is that the reduced states are solved once and then reused millions of times.
The C++, Python, and Java implementations all compute the same mathematical object, namely the terminal label \(E(n)\), but they package the memoization slightly differently.
The computation begins with the two known labels \(1\) and \(89\). Reaching \(1\) settles the chain immediately, and reaching \(89\) also settles it for classification purposes because the subsequent values stay on the 8-cycle through \(145,42,20,4,16,37,58\).
When the implementation meets a value whose outcome is not yet known, it keeps applying the digit-square map until it reaches a value that is already classified. At that point, the same label is assigned back through the states just visited. This is the memoization step. The C++ and Java implementations keep the stored table very close to the reduced range bounded by \(567\), while the Python implementation applies the same recurrence recursively with a dictionary cache.
The main loop checks each starting value from \(1\) up to \(9{,}999{,}999\). For each one, it computes the sum of squared digits and asks whether the resulting reduced state has label \(89\). One implementation also contains small checkpoint verifications that match the standard examples: there are 7 such chains below \(10\) and 80 below \(100\).
Let \(N=10^7-1\). Computing one digit-square sum takes at most 7 digit operations, so the dominant cost is linear in the number of starting values, namely \(O(N)\) with a small constant, or \(O(N\log_{10}N)\) if the digit extraction is written explicitly. The reduced-state resolution is negligible by comparison because only 567 core states need classification.
The mathematical core needs only \(O(567)\) memory for terminal labels. That is essentially what the C++ and Java implementations use, up to small fixed overhead. The Python implementation follows the same recurrence but can retain more cached values because it memoizes recursively in a dictionary as it resolves inputs.
Man startet mit einer positiven ganzen Zahl \(n\), ersetzt sie wiederholt durch die Summe der Quadrate ihrer Dezimalziffern und erhält so die Kette $$n,\ \sigma(n),\ \sigma(\sigma(n)),\dots,$$ wobei $$\sigma(n)=\sum (\text{Dezimalziffer})^2.$$ Für alle Startwerte dieser Aufgabe endet die Kette schließlich entweder im Fixpunkt \(1\) oder im Zyklus $$89 \to 145 \to 42 \to 20 \to 4 \to 16 \to 37 \to 58 \to 89.$$ Gesucht ist die Anzahl der Startzahlen mit \(1 \le n \lt 10^7\), die im \(89\)-Zyklus landen.
Der entscheidende Punkt ist, dass die Dynamik sehr schnell kollabiert. Obwohl es fast zehn Millionen Startwerte gibt, fällt jede Kette schon nach einem einzigen Ziffernquadratschritt in einen sehr kleinen endlichen Zustandsraum. Das Problem ist also keine lange Simulation, sondern eine Klassifikation dieser reduzierten Zustände.
Die Implementierungen beruhen auf einer einzigen Reduktion: Statt alle Zahlen unter \(10^7\) separat zu behandeln, klassifiziert man die möglichen Werte der Ziffernquadratsumme und verwendet diese Klassifikation dann für alle Startwerte wieder.
Definiere $$\sigma(n)=\sum_{r=0}^{k-1} d_r^2,$$ wobei \(d_0,d_1,\dots,d_{k-1}\) die Dezimalziffern von \(n\) sind. Wiederholtes Anwenden von \(\sigma\) erzeugt eine deterministische Folge, also liegt jeder Startwert auf einem Pfad in einem endlichen funktionalen Graphen, sobald die Werte klein genug geworden sind.
Für diese Aufgabe sind nur zwei Endverhalten relevant: $$1 \to 1$$ und der oben angegebene \(89\)-Zyklus. Praktisch ist daher eine Endetikett-Funktion $$E(n)\in\{1,89\},$$ wobei \(E(n)=1\) bedeutet, dass die Kette ab \(n\) die \(1\) erreicht, und \(E(n)=89\), dass sie den \(89\)-Zyklus erreicht.
Jeder Startwert erfüllt \(n \lt 10^7\) und besitzt daher höchstens 7 Dezimalziffern. Die größte mögliche Ziffernquadratsumme entsteht also bei lauter Neunen: $$\sigma(n)\le 7\cdot 9^2=7\cdot 81=567.$$ Nach einer einzigen Anwendung von \(\sigma\) ist jede Kette also bereits in der Menge $$S=\{1,2,\dots,567\}.$$ Genau diese Kompression macht die Aufgabe handhabbar.
Die Menge \(S\) ist außerdem unter weiterer Anwendung von \(\sigma\) abgeschlossen. Denn jedes \(m\in S\) hat höchstens 3 Ziffern, also $$\sigma(m)\le 3\cdot 9^2=243 \lt 567.$$ Sobald eine Kette \(S\) betreten hat, verlässt sie \(S\) nie wieder. Die gesamte Aufgabe wird dadurch auf einen funktionalen Graphen mit nur 567 Knoten reduziert.
Auf diesem reduzierten Zustandsraum gilt die einfache Rekursion $$E(1)=1,\qquad E(89)=89,\qquad E(m)=E(\sigma(m))\text{ für }m\notin\{1,89\}.$$ Genau diese Formel werten die Implementierungen aus. Ist das Schicksal von \(\sigma(m)\) bereits bekannt, dann ist auch das Schicksal von \(m\) bekannt. Memoisierung macht daraus einen effizienten Nachschlageprozess: Jeder reduzierte Zustand wird höchstens einmal klassifiziert und danach nur noch gelesen.
Man kann die Terminierung auch über numerischen Abstieg sehen. Hat \(n\) genau \(d\) Ziffern, dann gilt \(n\ge 10^{d-1}\) und zugleich \(\sigma(n)\le 81d\). Für \(d\ge 4\) folgt \(81d \lt 10^{d-1}\), also \(\sigma(n)\lt n\). In der vorliegenden Aufgabe fallen alle Startwerte ohnehin sofort in \(S\), aber dieses Ungleichungsargument erklärt, warum keine Kette beliebig wachsen kann.
Für \(44\) ergibt sich die Kette $$44 \to 4^2+4^2=32 \to 3^2+2^2=13 \to 1^2+3^2=10 \to 1.$$ Also ist \(E(44)=1\).
Ein besonders aufschlussreiches Beispiel ist der größte mögliche reduzierte Zustand. Da $$\sigma(9{,}999{,}999)=7\cdot 81=567,$$ geht es weiter mit $$567 \to 110 \to 2 \to 4 \to 16 \to 37 \to 58 \to 89.$$ Jeder Startwert, dessen erste Ziffernquadratsumme \(567\) ist, wird also zur \(89\)-Klasse gezählt.
Sobald \(E(m)\) für alle \(m\in S\) bestimmt ist, lautet die gesuchte Anzahl einfach $$\#\{1\le n \lt 10^7 : E(\sigma(n))=89\}.$$ Genau diese Größe akkumulieren die effizienten Implementierungen. Der Gewinn besteht darin, dass die reduzierten Zustände einmal gelöst und anschließend millionenfach wiederverwendet werden.
Die C++-, Python- und Java-Implementierungen berechnen alle dasselbe mathematische Objekt, nämlich das Endetikett \(E(n)\), organisieren die Memoisierung aber leicht unterschiedlich.
Zu Beginn werden die beiden bekannten Labels \(1\) und \(89\) gesetzt. Wer \(1\) erreicht, ist sofort entschieden; wer \(89\) erreicht, ist für die Klassifikation ebenfalls entschieden, weil die weiteren Werte auf dem 8-Zyklus über \(145,42,20,4,16,37,58\) bleiben.
Trifft die Implementierung auf einen Wert, dessen Ausgang noch unbekannt ist, wendet sie die Ziffernquadratsumme so lange an, bis ein bereits klassifizierter Zustand erreicht wird. Anschließend wird dasselbe Endetikett rückwärts auf die gerade besuchten Zustände übertragen. Das ist der Memoisierungsschritt. C++ und Java halten die gespeicherte Tabelle dabei eng am reduzierten Bereich bis \(567\), während die Python-Implementierung dieselbe Rekursion mit einem Dictionary-Cache ausführt.
Die Hauptschleife prüft alle Startwerte von \(1\) bis \(9{,}999{,}999\). Für jeden Wert wird die Ziffernquadratsumme berechnet und anschließend gefragt, ob der resultierende reduzierte Zustand das Label \(89\) besitzt. Eine Implementierung enthält außerdem kleine Kontrolltests, die zu den bekannten Beispielen passen: Unter \(10\) gibt es 7 solche Startwerte, unter \(100\) genau 80.
Sei \(N=10^7-1\). Eine einzelne Ziffernquadratsumme benötigt höchstens 7 Ziffernoperationen, also ist die dominierende Laufzeit linear in der Zahl der Startwerte, also \(O(N)\) mit kleinem konstanten Faktor, beziehungsweise \(O(N\log_{10}N)\), wenn man die Ziffernextraktion explizit hinschreibt. Die Auflösung im reduzierten Zustandsraum ist dagegen vernachlässigbar, weil nur 567 Kernzustände klassifiziert werden müssen.
Der mathematische Kern benötigt nur \(O(567)\) Speicher für die Endetiketten. Daran liegen die C++- und Java-Implementierungen bis auf kleine Konstanten sehr nahe. Die Python-Implementierung folgt derselben Rekursion, kann aber mehr Cache-Einträge behalten, weil sie Eingaben rekursiv in einem Dictionary memoisiert.
Pozitif bir \(n\) tamsayısıyla başlanır, sayı tekrar tekrar ondalık basamaklarının kareleri toplamıyla değiştirilir ve şu zincir elde edilir: $$n,\ \sigma(n),\ \sigma(\sigma(n)),\dots,$$ burada $$\sigma(n)=\sum (\text{ondalık basamak})^2.$$ Bu problemdeki bütün başlangıç değerleri sonunda ya sabit nokta \(1\)'e ya da $$89 \to 145 \to 42 \to 20 \to 4 \to 16 \to 37 \to 58 \to 89$$ döngüsüne ulaşır. Amaç, \(1 \le n \lt 10^7\) koşulunu sağlayan başlangıç sayılarından kaç tanesinin \(89\) döngüsünde sonlandığını saymaktır.
Asıl kilit nokta, zincir davranışının çok hızlı biçimde daralmasıdır. Başlangıçta neredeyse on milyon farklı değer olsa da, bir tek basamak-kare toplamı adımından sonra bütün zincirler çok küçük bir sonlu durum uzayına düşer. Dolayısıyla sorun uzun zincirleri tek tek çözmek değil, bu küçük uzaydaki durumları sınıflandırmaktır.
Uygulamalar tek bir indirgemeye dayanır: \(10^7\)'den küçük bütün sayıları ayrı ayrı analiz etmek yerine, basamak-kare toplamının alabileceği değerleri sınıflandırır ve sonra bu sınıflandırmayı her başlangıç değeri için tekrar kullanırız.
$$\sigma(n)=\sum_{r=0}^{k-1} d_r^2$$ tanımını yapalım; burada \(d_0,d_1,\dots,d_{k-1}\), \(n\)'nin ondalık basamaklarıdır. \(\sigma\)'nın ardışık uygulanması deterministik bir dizi oluşturur; dolayısıyla değerler yeterince küçüldükten sonra her başlangıç değeri sonlu bir fonksiyonel graf üzerinde bir yol izler.
Bu problem için önemli olan yalnızca iki son davranıştır: $$1 \to 1$$ ve yukarıdaki \(89\) döngüsü. Bu yüzden sonucu $$E(n)\in\{1,89\}$$ biçiminde kodlamak uygundur. Burada \(E(n)=1\), \(n\) ile başlayan zincirin \(1\)'e ulaştığını; \(E(n)=89\) ise \(89\) döngüsüne ulaştığını belirtir.
Her başlangıç değeri için \(n \lt 10^7\) olduğundan en fazla 7 ondalık basamak vardır. Basamak-kare toplamının alabileceği en büyük değer bütün basamaklar \(9\) olduğunda elde edilir: $$\sigma(n)\le 7\cdot 9^2=7\cdot 81=567.$$ Demek ki \(\sigma\)'nın tek bir uygulamasından sonra bütün zincirler $$S=\{1,2,\dots,567\}$$ kümesine girmiş olur. Problemi küçük hale getiren temel sıkıştırma tam olarak budur.
Üstelik \(S\) kümesi \(\sigma\) altında kapalıdır. Gerçekten, \(m\in S\) ise \(m\) en fazla 3 basamaklıdır ve bu nedenle $$\sigma(m)\le 3\cdot 9^2=243 \lt 567.$$ Zincir bir kez \(S\)'ye girdikten sonra artık dışarı çıkmaz. Böylece bütün problem yalnızca 567 düğümlü bir fonksiyonel graf üzerinde çözülür.
İndirgenmiş durum uzayında sınıflandırma şu basit bağıntıya uyar: $$E(1)=1,\qquad E(89)=89,\qquad E(m)=E(\sigma(m))\text{ ve }m\notin\{1,89\}.$$ Uygulamaların hesapladığı şey tam olarak budur. \(\sigma(m)\)'nin kaderi biliniyorsa, \(m\)'nin kaderi de aynıdır. Memoization sayesinde bu bağıntı verimli bir arama tablosuna dönüşür: indirgenmiş bir durum bir kez çözüldüğünde, ona daha sonra gelen bütün zincirler anında sınıflandırılır.
Sonlanmayı sayısal azalma ile de görebiliriz. \(n\), \(d\) basamaklı olsun. O zaman \(n\ge 10^{d-1}\) ve \(\sigma(n)\le 81d\) olur. \(d\ge 4\) için \(81d \lt 10^{d-1}\) sağlandığından \(\sigma(n)\lt n\) elde edilir. Bu problemde bütün başlangıç değerleri zaten tek adımda \(S\)'ye düşer, fakat bu eşitsizlik hiçbir zincirin sınırsız büyümeyeceğini de açıklar.
\(44\) için zincir şöyledir: $$44 \to 4^2+4^2=32 \to 3^2+2^2=13 \to 1^2+3^2=10 \to 1.$$ Dolayısıyla \(E(44)=1\).
Daha öğretici bir örnek, indirgenmiş uzaydaki en büyük değeri kullanır. Çünkü $$\sigma(9{,}999{,}999)=7\cdot 81=567$$ olduğundan devamı $$567 \to 110 \to 2 \to 4 \to 16 \to 37 \to 58 \to 89$$ olur. Yani ilk basamak-kare toplamı \(567\) olan her başlangıç değeri, doğrudan \(89\) sınıfına sayılır.
\(S\) içindeki bütün \(m\) değerleri için \(E(m)\) bulunduğunda cevap doğrudan $$\#\{1\le n \lt 10^7 : E(\sigma(n))=89\}$$ olur. Verimli uygulamaların topladığı büyüklük tam olarak budur. Kazanç şuradan gelir: indirgenmiş durumlar bir kez çözülür, sonra milyonlarca kez yeniden kullanılır.
C++, Python ve Java uygulamalarının hepsi aynı matematiksel nesneyi, yani \(E(n)\) son etiketini hesaplar; yalnızca memoization paketleme biçimleri biraz farklıdır.
Hesaplama, \(1\) ve \(89\) için bilinen iki etiketle başlar. \(1\)'e ulaşmak zinciri hemen bitirir; \(89\)'a ulaşmak da sınıflandırma açısından yeterlidir, çünkü sonraki değerler \(145,42,20,4,16,37,58\) üzerinden aynı 8 döngüde kalır.
Uygulama sonucu bilinmeyen bir değer gördüğünde, zaten sınıflandırılmış bir değere ulaşana kadar basamak-kare toplamını uygulamaya devam eder. Daha sonra ulaşılan etiket, az önce ziyaret edilen değerlere geriye doğru yazılır. Memoization adımı budur. C++ ve Java sürümleri saklanan tabloyu \(567\) ile sınırlı indirgenmiş aralığa çok yakın tutar; Python sürümü ise aynı bağıntıyı sözlük önbelleği kullanan özyinelemeli bir yapı ile uygular.
Ana döngü \(1\)'den \(9{,}999{,}999\)'a kadar her başlangıç değerini kontrol eder. Her değer için basamak-kare toplamı hesaplanır ve elde edilen indirgenmiş durumun etiketinin \(89\) olup olmadığına bakılır. Uygulamalardan biri ayrıca klasik küçük örnekleri doğrulayan kısa kontrol testleri içerir: \(10\)'dan küçük sayılar arasında 7 tane, \(100\)'den küçük sayılar arasında ise 80 tane \(89\)'da sonlanan zincir vardır.
\(N=10^7-1\) olsun. Tek bir basamak-kare toplamı en fazla 7 basamak işlemi gerektirir; bu yüzden baskın maliyet başlangıç sayısı ile doğrusal büyür. Yani çalışma süresi küçük sabit katsayıyla \(O(N)\), basamak çıkarma maliyeti açık yazılırsa \(O(N\log_{10}N)\) olur. İndirgenmiş durum uzayındaki çözümleme ise buna göre ihmal edilebilir, çünkü sınıflandırılması gereken çekirdek durum sayısı yalnızca 567'dir.
Matematiksel çekirdek, son etiketler için yalnızca \(O(567)\) bellek ister. C++ ve Java uygulamaları küçük sabit farklarla buna çok yakındır. Python uygulaması aynı bağıntıyı izler, fakat girdileri sözlük içinde özyinelemeli olarak önbelleğe aldığı için daha fazla saklanmış değer tutabilir.
Se empieza con un entero positivo \(n\), se lo reemplaza repetidamente por la suma de los cuadrados de sus dígitos decimales y así se obtiene la cadena $$n,\ \sigma(n),\ \sigma(\sigma(n)),\dots,$$ donde $$\sigma(n)=\sum (\text{dígito decimal})^2.$$ Para todos los valores iniciales de este problema, la cadena termina llegando al punto fijo \(1\) o al ciclo $$89 \to 145 \to 42 \to 20 \to 4 \to 16 \to 37 \to 58 \to 89.$$ El objetivo es contar cuántos números iniciales cumplen \(1 \le n \lt 10^7\) y acaban en el ciclo de \(89\).
La observación importante es que la dinámica se comprime muy rápido. Aunque hay casi diez millones de valores iniciales, después de un solo paso de suma de cuadrados de dígitos todas las cadenas ya han caído en un espacio de estados finito y pequeño. Por eso el problema real no es una simulación larga, sino una clasificación en ese espacio reducido.
Las implementaciones se apoyan en una sola reducción: en vez de estudiar por separado todos los números menores que \(10^7\), se clasifican primero los posibles valores de la suma de cuadrados de dígitos y luego esa clasificación se reutiliza para todos los valores iniciales.
Definimos $$\sigma(n)=\sum_{r=0}^{k-1} d_r^2,$$ donde \(d_0,d_1,\dots,d_{k-1}\) son los dígitos decimales de \(n\). Al aplicar \(\sigma\) repetidamente obtenemos una sucesión determinista, de modo que cada valor inicial recorre un camino dentro de un grafo funcional finito una vez que los números se vuelven suficientemente pequeños.
En este problema solo importan dos comportamientos finales: $$1 \to 1$$ y el ciclo de \(89\) indicado arriba. Por eso conviene introducir una función de etiqueta terminal $$E(n)\in\{1,89\},$$ donde \(E(n)=1\) significa que la cadena que empieza en \(n\) llega a \(1\), y \(E(n)=89\) significa que llega al ciclo de \(89\).
Todo valor inicial satisface \(n \lt 10^7\), así que tiene a lo sumo 7 dígitos decimales. La suma de cuadrados de dígitos más grande posible se obtiene cuando todos los dígitos son \(9\): $$\sigma(n)\le 7\cdot 9^2=7\cdot 81=567.$$ Eso implica que, después de una sola aplicación de \(\sigma\), toda cadena entra ya en el conjunto $$S=\{1,2,\dots,567\}.$$ Este es el paso de compresión decisivo de toda la solución.
Además, \(S\) es cerrado bajo nuevas aplicaciones de \(\sigma\). En efecto, si \(m\in S\), entonces \(m\) tiene a lo sumo 3 dígitos, y por tanto $$\sigma(m)\le 3\cdot 9^2=243 \lt 567.$$ Una vez que una cadena entra en \(S\), ya no sale de allí. Así, todo el problema queda reducido a un grafo funcional con solo 567 nodos.
En ese espacio reducido, la clasificación satisface la recurrencia $$E(1)=1,\qquad E(89)=89,\qquad E(m)=E(\sigma(m))\text{ para }m\notin\{1,89\}.$$ Esa es exactamente la fórmula que evalúan las implementaciones. Si ya se conoce el destino de \(\sigma(m)\), entonces el destino de \(m\) es el mismo. La memoización convierte esta relación en un mecanismo eficiente de consulta: cada estado reducido se clasifica una sola vez y luego pasa a ser una búsqueda inmediata.
También se puede justificar la terminación mediante descenso numérico. Si \(n\) tiene \(d\) dígitos, entonces \(n\ge 10^{d-1}\) mientras que \(\sigma(n)\le 81d\). Para \(d\ge 4\) se cumple \(81d \lt 10^{d-1}\), luego \(\sigma(n)\lt n\). En esta tarea todos los valores iniciales entran en \(S\) tras un solo paso, pero esta desigualdad explica además por qué ninguna cadena puede crecer indefinidamente.
Para \(44\), la cadena es $$44 \to 4^2+4^2=32 \to 3^2+2^2=13 \to 1^2+3^2=10 \to 1.$$ Por tanto, \(E(44)=1\).
Un ejemplo más instructivo usa el mayor estado reducido posible. Como $$\sigma(9{,}999{,}999)=7\cdot 81=567,$$ la cadena continúa como $$567 \to 110 \to 2 \to 4 \to 16 \to 37 \to 58 \to 89.$$ Así, cualquier valor inicial cuya primera suma de cuadrados de dígitos sea \(567\) cuenta automáticamente como cadena que termina en \(89\).
Una vez conocido \(E(m)\) para todo \(m\in S\), la respuesta es simplemente $$\#\{1\le n \lt 10^7 : E(\sigma(n))=89\}.$$ Esa es exactamente la cantidad que acumulan las implementaciones eficientes. La economía viene de que los estados reducidos se resuelven una sola vez y luego se reutilizan millones de veces.
Las implementaciones en C++, Python y Java calculan el mismo objeto matemático, la etiqueta terminal \(E(n)\), aunque empaquetan la memoización de forma ligeramente distinta.
El cálculo empieza fijando las dos etiquetas conocidas, \(1\) y \(89\). Llegar a \(1\) decide inmediatamente la cadena, y llegar a \(89\) también la decide para fines de clasificación, porque los valores siguientes permanecen en el ciclo de longitud 8 que pasa por \(145,42,20,4,16,37,58\).
Cuando la implementación encuentra un valor cuyo destino aún no está clasificado, sigue aplicando la suma de cuadrados de dígitos hasta alcanzar un estado ya conocido. En ese momento, la misma etiqueta se propaga hacia atrás sobre los estados recién visitados. Ese es el paso de memoización. Las versiones en C++ y Java mantienen la tabla almacenada muy cerca del rango reducido acotado por \(567\), mientras que la versión en Python aplica la misma recurrencia de manera recursiva con una caché tipo diccionario.
El bucle principal examina cada valor inicial desde \(1\) hasta \(9{,}999{,}999\). Para cada uno calcula la suma de cuadrados de dígitos y pregunta si el estado reducido obtenido tiene etiqueta \(89\). Una de las implementaciones incluye además pequeñas verificaciones que coinciden con los ejemplos clásicos: hay 7 cadenas de este tipo por debajo de \(10\) y 80 por debajo de \(100\).
Sea \(N=10^7-1\). Calcular una suma de cuadrados de dígitos requiere como máximo 7 operaciones sobre dígitos, así que el costo dominante es lineal en el número de valores iniciales, es decir, \(O(N)\) con una constante pequeña, o \(O(N\log_{10}N)\) si se escribe explícitamente el costo de extraer los dígitos. La resolución del espacio reducido es despreciable en comparación, porque solo hay 567 estados centrales que clasificar.
El núcleo matemático solo necesita \(O(567)\) memoria para las etiquetas terminales. Eso es esencialmente lo que usan las implementaciones de C++ y Java, salvo pequeños costes fijos. La implementación en Python sigue la misma recurrencia, pero puede conservar más valores en caché porque memoiza recursivamente en un diccionario mientras resuelve las entradas.
从一个正整数 \(n\) 出发，把它反复替换为各位十进制数字平方和，就得到链 $$n,\ \sigma(n),\ \sigma(\sigma(n)),\dots,$$ 其中 $$\sigma(n)=\sum (\text{十进制数字})^2.$$ 在这道题里，所有起始值最终都会落到两种结局之一：要么到达不动点 \(1\)，要么进入循环 $$89 \to 145 \to 42 \to 20 \to 4 \to 16 \to 37 \to 58 \to 89.$$ 题目要求统计满足 \(1 \le n \lt 10^7\) 的起始数中，有多少个最终落入 \(89\) 这一循环。
真正关键的事实是，这个迭代过程会非常快地压缩。虽然起始值接近一千万个，但做完一次“数字平方和”之后，所有链都已经落进一个很小的有限状态空间里。因此问题的本质不是对长链做暴力模拟，而是对这个小状态空间做分类。
三个实现都建立在同一个缩减上：不是把 \(10^7\) 以下的每个数分别研究，而是先把“数字平方和”可能得到的值分类，再把这个分类结果复用于所有起始值。
定义 $$\sigma(n)=\sum_{r=0}^{k-1} d_r^2,$$ 其中 \(d_0,d_1,\dots,d_{k-1}\) 是 \(n\) 的十进制数字。不断应用 \(\sigma\) 会得到一条确定性的轨道，所以当数值缩小到一定范围之后，每个起始值其实都只是在一个有限的函数图上沿着唯一的边前进。
对这道题来说，真正需要区分的只有两种归宿： $$1 \to 1$$ 和上面的 \(89\) 循环。于是可以定义一个终点标签函数 $$E(n)\in\{1,89\},$$ 其中 \(E(n)=1\) 表示从 \(n\) 出发的链最终到达 \(1\)，而 \(E(n)=89\) 表示它最终进入 \(89\) 所在的循环。
因为题目限制 \(n \lt 10^7\)，所以起始值最多只有 7 位十进制数字。数字平方和的最大值出现在所有数字都是 \(9\) 时： $$\sigma(n)\le 7\cdot 9^2=7\cdot 81=567.$$ 这意味着，只要做一次 \(\sigma\)，任意起始值就一定进入集合 $$S=\{1,2,\dots,567\}.$$ 这是整道题最关键的一步压缩。
更进一步，集合 \(S\) 在 \(\sigma\) 作用下还是封闭的。因为 \(m\in S\) 时，\(m\) 最多只有 3 位数字，所以 $$\sigma(m)\le 3\cdot 9^2=243 \lt 567.$$ 也就是说，一条链一旦进入 \(S\)，以后就再也不会离开。于是原来看似无限的迭代，其实完全由一个只有 567 个节点的函数图控制。
在这个缩减后的状态空间上，分类满足非常简单的递推： $$E(1)=1,\qquad E(89)=89,\qquad E(m)=E(\sigma(m)),\qquad m\notin\{1,89\}$$ 这正是实现里真正求解的公式。如果 \(\sigma(m)\) 的归宿已经知道，那么 \(m\) 的归宿就完全一样。记忆化的作用就在这里体现出来：某个缩减状态一旦被判定，以后任何链只要走到它，结果都可以立刻查表得到。
还可以用“数值下降”来解释为什么过程一定会落回小范围。如果 \(n\) 有 \(d\) 位，那么 \(n\ge 10^{d-1}\)，而 \(\sigma(n)\le 81d\)。当 \(d\ge 4\) 时有 \(81d \lt 10^{d-1}\)，因此 \(\sigma(n)\lt n\)。在本题里所有起始值其实第一步就已经掉进 \(S\)，但这个不等式说明了链不可能无限增长。
\(44\) 的链是 $$44 \to 4^2+4^2=32 \to 3^2+2^2=13 \to 1^2+3^2=10 \to 1$$ 所以 \(E(44)=1\)。
更能体现状态压缩的是最大可能缩减值。因为 $$\sigma(9{,}999{,}999)=7\cdot 81=567,$$ 所以后面继续得到 $$567 \to 110 \to 2 \to 4 \to 16 \to 37 \to 58 \to 89$$ 因而，只要某个起始值第一步的数字平方和等于 \(567\)，它就一定被计入“最终到达 \(89\)”这一类。
只要对所有 \(m\in S\) 都求出了 \(E(m)\)，那么答案就是 $$\#\{1\le n \lt 10^7 : E(\sigma(n))=89\}$$ 这正是高效实现所累加的量。真正节省时间的地方在于：缩减状态只需要求解一次，之后就能被几百万次重复利用。
C++、Python 和 Java 三个实现求的都是同一个数学对象，即终点标签 \(E(n)\)，只是记忆化的组织方式略有不同。
计算一开始就把 \(1\) 和 \(89\) 这两个已知结果放入缓存。到达 \(1\) 就说明链已经判定完毕；到达 \(89\) 在分类意义下也已经结束，因为之后的值会一直留在经过 \(145,42,20,4,16,37,58\) 的那个长度为 8 的循环里。
当实现遇到一个尚未分类的值时，就不断应用数字平方和，直到走到一个结果已知的状态为止。然后把这个终点标签回写到刚才访问过的那些状态上。这一步就是记忆化。C++ 和 Java 把保存下来的表尽量限制在由 \(567\) 控制的缩减区间附近，而 Python 则用字典缓存以递归方式实现同样的递推。
主循环逐个检查从 \(1\) 到 \(9{,}999{,}999\) 的每个起始值。对每个数先算数字平方和，再判断对应的缩减状态是否带有标签 \(89\)。其中一个实现还带了很小的检查点验证，与题目里常见示例一致：小于 \(10\) 的这样的起始值有 7 个，小于 \(100\) 的有 80 个。
设 \(N=10^7-1\)。一次数字平方和最多只需要处理 7 个数字，因此主导成本与起始值个数线性相关，也就是小常数下的 \(O(N)\)；如果把取位操作显式写出来，也可以写成 \(O(N\log_{10}N)\)。相比之下，缩减状态空间的求解几乎可以忽略，因为真正需要分类的核心状态只有 567 个。
数学核心只需要 \(O(567)\) 的终点标签存储。C++ 和 Java 的实现基本上就贴近这个量级，只差很小的固定开销。Python 实现遵循完全相同的递推，但因为它在字典里递归缓存已经求过的输入，所以可能保留更多缓存项。
Берем положительное целое число \(n\), затем многократно заменяем его суммой квадратов его десятичных цифр. Так возникает цепочка $$n,\ \sigma(n),\ \sigma(\sigma(n)),\dots,$$ где $$\sigma(n)=\sum (\text{десятичная цифра})^2.$$ Для всех начальных значений в этой задаче цепочка в итоге приходит либо в неподвижную точку \(1\), либо в цикл $$89 \to 145 \to 42 \to 20 \to 4 \to 16 \to 37 \to 58 \to 89.$$ Нужно посчитать, сколько начальных чисел удовлетворяют \(1 \le n \lt 10^7\) и заканчивают именно в цикле с \(89\).
Главное наблюдение состоит в том, что динамика очень быстро сжимается. Хотя стартовых значений почти десять миллионов, уже после одного шага суммы квадратов цифр любая цепочка попадает в очень маленькое конечное пространство состояний. Поэтому здесь важна не длинная симуляция, а правильная классификация состояний в этом уменьшенном пространстве.
Все реализации опираются на одно и то же сокращение: вместо того чтобы разбирать отдельно каждое число меньше \(10^7\), сначала классифицируют возможные значения суммы квадратов цифр, а затем используют эту классификацию повторно для всех стартовых чисел.
Определим $$\sigma(n)=\sum_{r=0}^{k-1} d_r^2,$$ где \(d_0,d_1,\dots,d_{k-1}\) обозначают десятичные цифры числа \(n\). Повторное применение \(\sigma\) задает детерминированную последовательность, так что после перехода к достаточно малым значениям каждая траектория просто идет по единственному пути в конечном функциональном графе.
Для данной задачи важны только два конечных исхода: $$1 \to 1$$ и приведенный выше цикл с \(89\). Поэтому удобно ввести функцию конечной метки $$E(n)\in\{1,89\},$$ где \(E(n)=1\) означает, что цепочка из \(n\) приходит к \(1\), а \(E(n)=89\) означает, что она приходит в цикл с \(89\).
В условии всегда \(n \lt 10^7\), а значит у стартового числа не более 7 десятичных цифр. Максимальная возможная сумма квадратов цифр достигается, когда все цифры равны \(9\): $$\sigma(n)\le 7\cdot 9^2=7\cdot 81=567.$$ Следовательно, уже после одного применения \(\sigma\) любая цепочка попадает в множество $$S=\{1,2,\dots,567\}.$$ Именно это и является ключевым сжатием задачи.
Множество \(S\) замкнуто и относительно дальнейших применений \(\sigma\). Если \(m\in S\), то у него не более 3 цифр, и потому $$\sigma(m)\le 3\cdot 9^2=243 \lt 567.$$ Значит, попав в \(S\), цепочка уже никогда его не покинет. Тем самым вся задача сводится к функциональному графу всего на 567 вершинах.
На уменьшенном пространстве состояний классификация подчиняется простой рекурсии: $$E(1)=1,\qquad E(89)=89,\qquad E(m)=E(\sigma(m))\text{ при }m\notin\{1,89\}.$$ Именно эту формулу и вычисляют реализации. Если уже известно, чем заканчивается \(\sigma(m)\), то исход для \(m\) совпадает с ним. Мемоизация превращает эту рекурсию в эффективную схему запросов: как только уменьшенное состояние классифицировано, все будущие цепочки, попадающие в него, решаются мгновенно.
Остановку можно также объяснить через числовой спад. Если у \(n\) ровно \(d\) цифр, то \(n\ge 10^{d-1}\), а \(\sigma(n)\le 81d\). При \(d\ge 4\) имеем \(81d \lt 10^{d-1}\), следовательно \(\sigma(n)\lt n\). В данной задаче все стартовые значения и так попадают в \(S\) уже за один шаг, но это неравенство показывает, почему цепочка не может расти бесконечно.
Для \(44\) цепочка имеет вид $$44 \to 4^2+4^2=32 \to 3^2+2^2=13 \to 1^2+3^2=10 \to 1.$$ Значит, \(E(44)=1\).
Более показателен пример с максимально возможным уменьшенным состоянием. Поскольку $$\sigma(9{,}999{,}999)=7\cdot 81=567,$$ далее получаем $$567 \to 110 \to 2 \to 4 \to 16 \to 37 \to 58 \to 89.$$ Следовательно, любое стартовое значение, у которого первая сумма квадратов цифр равна \(567\), автоматически относится к классу, заканчивающемуся в \(89\).
Когда \(E(m)\) известно для всех \(m\in S\), ответ просто равен $$\#\{1\le n \lt 10^7 : E(\sigma(n))=89\}.$$ Именно эту величину накапливают эффективные реализации. Выигрыш состоит в том, что уменьшенные состояния решаются один раз, а затем используются повторно миллионы раз.
Реализации на C++, Python и Java вычисляют один и тот же математический объект, а именно конечную метку \(E(n)\), но организуют мемоизацию немного по-разному.
В начале в кэш заносятся два известных результата: \(1\) и \(89\). Попадание в \(1\) немедленно завершает классификацию цепочки, а попадание в \(89\) тоже завершает ее в смысле задачи, потому что дальше значения остаются на цикле длины 8 через \(145,42,20,4,16,37,58\).
Если реализация встречает значение, чей исход еще не известен, она продолжает применять сумму квадратов цифр, пока не достигнет уже классифицированного состояния. После этого та же конечная метка записывается назад на только что посещенные состояния. В этом и состоит мемоизация. Версии на C++ и Java держат сохраненную таблицу очень близко к уменьшенному диапазону, ограниченному числом \(567\), тогда как версия на Python реализует ту же рекурсию с помощью словаря и рекурсивного кэша.
Основной цикл просматривает каждое стартовое число от \(1\) до \(9{,}999{,}999\). Для каждого числа вычисляется сумма квадратов цифр, после чего проверяется, имеет ли соответствующее уменьшенное состояние метку \(89\). В одной из реализаций есть также небольшие контрольные проверки, совпадающие со стандартными примерами: ниже \(10\) таких цепочек 7, а ниже \(100\) их 80.
Пусть \(N=10^7-1\). Вычисление одной суммы квадратов цифр требует не более 7 операций над цифрами, поэтому доминирующая стоимость линейна по числу стартовых значений, то есть \(O(N)\) с малой константой, либо \(O(N\log_{10}N)\), если явно учитывать стоимость извлечения цифр. Разрешение уменьшенного пространства состояний по сравнению с этим пренебрежимо мало, поскольку классифицировать нужно всего 567 основных состояний.
Математическое ядро требует только \(O(567)\) памяти для конечных меток. Именно к такому объему близки реализации на C++ и Java с точностью до малых постоянных накладных расходов. Реализация на Python следует той же рекурсии, но может удерживать больше закэшированных значений, потому что рекурсивно мемоизирует входы в словаре.
نبدأ بعدد صحيح موجب \(n\)، ثم نستبدله مرارًا بمجموع مربعات أرقامه العشرية، فنحصل على السلسلة $$n,\ \sigma(n),\ \sigma(\sigma(n)),\dots,$$ حيث $$\sigma(n)=\sum d^2.$$ في هذه المسألة ينتهي كل عدد ابتدائي في النهاية إلى إحدى حالتين فقط: إما إلى النقطة الثابتة \(1\)، أو إلى الدورة $$89 \to 145 \to 42 \to 20 \to 4 \to 16 \to 37 \to 58 \to 89.$$ والمطلوب هو عدُّ الأعداد الابتدائية التي تحقق \(1 \le n \lt 10^7\) وتنتهي في دورة \(89\).
الملاحظة الحاسمة هي أن هذه الديناميكا تنضغط بسرعة كبيرة. فعلى الرغم من أن عدد القيم الابتدائية يقارب عشرة ملايين، فإن كل سلسلة بعد خطوة واحدة فقط من مجموع مربعات الأرقام تهبط إلى فضاء حالات صغير ومنتهٍ. لذلك فجوهر المسألة ليس محاكاة سلاسل طويلة، بل تصنيف الحالات داخل هذا الفضاء المصغَّر.
تعتمد جميع الحلول على الاختزال نفسه: بدلًا من دراسة كل عدد أصغر من \(10^7\) على حدة، نُصنِّف أولًا القيم الممكنة لمجموع مربعات الأرقام، ثم نعيد استخدام هذا التصنيف لكل القيم الابتدائية.
نعرّف $$\sigma(n)=\sum_{r=0}^{k-1} d_r^2,$$ حيث تمثل \(d_0,d_1,\dots,d_{k-1}\) أرقام \(n\) في النظام العشري. وتكرار تطبيق \(\sigma\) يولّد متتالية حتمية، أي إن كل قيمة ابتدائية تسير في مسار وحيد داخل رسم بياني دالي منتهٍ عندما تصير القيم صغيرة بما يكفي.
في هذه المسألة لا يهمنا إلا نهايتان فقط: $$1 \to 1$$ ودورة \(89\) المذكورة أعلاه. لذلك من المناسب تعريف دالة وسم نهائي $$E(n)\in\{1,89\},$$ بحيث يعني \(E(n)=1\) أن السلسلة التي تبدأ من \(n\) تصل في النهاية إلى \(1\)، ويعني \(E(n)=89\) أنها تصل إلى الدورة التي تحتوي على \(89\).
بما أن كل قيمة ابتدائية تحقق \(n \lt 10^7\)، فهي تملك في أقصى الأحوال 7 أرقام عشرية. وأكبر قيمة ممكنة لمجموع مربعات الأرقام تتحقق عندما تكون جميع الأرقام \(9\): $$\sigma(n)\le 7\cdot 9^2=7\cdot 81=567.$$ وهذا يعني أن كل سلسلة تدخل بعد تطبيق واحد فقط للمؤثر \(\sigma\) إلى المجموعة $$S=\{1,2,\dots,567\}.$$ وهذه هي خطوة الضغط الأساسية التي تجعل المسألة صغيرة.
كما أن المجموعة \(S\) مغلقة تحت تطبيق \(\sigma\) مرة أخرى. فإذا كان \(m\in S\)، فإن \(m\) يملك في أقصى الأحوال 3 أرقام، ومن ثم $$\sigma(m)\le 3\cdot 9^2=243 \lt 567.$$ وما إن تدخل السلسلة إلى \(S\) حتى لا تغادرها أبدًا. وبذلك تصبح المسألة كلها مسألة تصنيف على رسم بياني دالي لا يحتوي إلا على 567 حالة.
على فضاء الحالات المصغَّر هذا نحصل على العلاقة $$E(1)=1,\qquad E(89)=89,\qquad E(m)=E(\sigma(m)),\qquad m\notin\{1,89\}.$$ وهذه هي بالضبط الصيغة التي تحسبها التطبيقات. فإذا كان مصير \(\sigma(m)\) معلومًا، فإن مصير \(m\) يكون نفسه. وتحوّل عملية الحفظ المؤقت هذه العودية إلى آلية سريعة جدًا: فكل حالة مصغَّرة تُصنَّف مرة واحدة فقط، وبعدها تصبح مجرد عملية رجوع إلى جدول.
ويمكن أيضًا تبرير التوقف بفكرة التناقص العددي. إذا كان \(n\) ذا \(d\) أرقام، فلدينا \(n\ge 10^{d-1}\) وفي المقابل \(\sigma(n)\le 81d\). وعندما \(d\ge 4\) نحصل على \(81d \lt 10^{d-1}\)، وبالتالي \(\sigma(n)\lt n\). وفي هذه المسألة تدخل جميع القيم الابتدائية إلى \(S\) من أول خطوة أصلًا، لكن هذا المتباين يوضح لماذا لا يمكن للسلسلة أن تنمو بلا حد.
بالنسبة إلى \(44\) تكون السلسلة $$44 \to 4^2+4^2=32 \to 3^2+2^2=13 \to 1^2+3^2=10 \to 1.$$ إذن \(E(44)=1\).
وهناك مثال أوضح يستخدم أكبر حالة ممكنة في الفضاء المصغَّر. بما أن $$\sigma(9{,}999{,}999)=7\cdot 81=567,$$ فإن السلسلة تكمل على الصورة $$567 \to 110 \to 2 \to 4 \to 16 \to 37 \to 58 \to 89.$$ لذلك فإن أي قيمة ابتدائية يكون أول مجموع لمربعات أرقامها مساويًا لـ \(567\) تُحسب مباشرة ضمن السلاسل المنتهية إلى \(89\).
بمجرد معرفة \(E(m)\) لكل \(m\in S\)، يصبح الجواب هو $$\#\{1\le n \lt 10^7 : E(\sigma(n))=89\}.$$ وهذه هي الكمية نفسها التي تجمعها التطبيقات الفعالة. ومصدر الكفاءة واضح: الحالات المصغَّرة تُحل مرة واحدة فقط، ثم يُعاد استخدامها ملايين المرات.
تقوم تطبيقات C++ وPython وJava كلها بحساب الكائن الرياضي نفسه، وهو الوسم النهائي \(E(n)\)، لكن طريقة تنظيم الحفظ المؤقت تختلف قليلًا بين لغة وأخرى.
تبدأ العملية بتسجيل النتيجتين المعروفتين \(1\) و\(89\). فالخيط الذي يصل إلى \(1\) يُحسم فورًا، والخيط الذي يصل إلى \(89\) يُحسم أيضًا من حيث التصنيف لأن القيم التالية ستبقى على الدورة ذات الطول 8 المارة بـ \(145,42,20,4,16,37,58\).
عندما تصادف الشيفرة قيمة لم يُعرف مصيرها بعد، فإنها تواصل تطبيق مجموع مربعات الأرقام حتى تصل إلى حالة صار تصنيفها معروفًا. عندئذٍ يُعاد إسناد الوسم نفسه إلى القيم التي زارتها للتو. هذه هي خطوة الحفظ المؤقت. وتُبقي نسختا C++ وJava الجدول المخزَّن قريبًا جدًا من المجال المصغَّر المحدود بالعدد \(567\)، بينما تطبّق نسخة Python العودية نفسها باستعمال قاموس كذاكرة مؤقتة.
تمر الحلقة الرئيسية على كل قيمة ابتدائية من \(1\) حتى \(9{,}999{,}999\). ولكل قيمة تُحسب أولًا قيمة مجموع مربعات الأرقام، ثم يُسأل هل الحالة المصغَّرة الناتجة تحمل الوسم \(89\). كما أن إحدى التطبيقات تتضمن اختبارات تحقق صغيرة تطابق الأمثلة المعروفة: يوجد 7 من هذه السلاسل تحت \(10\)، ويوجد 80 منها تحت \(100\).
لنكتب \(N=10^7-1\). إن حساب مجموع مربعات الأرقام مرة واحدة يحتاج في أقصى الأحوال إلى 7 عمليات على الأرقام، ولذلك فإن الكلفة المهيمنة خطية في عدد القيم الابتدائية، أي \(O(N)\) مع ثابت صغير، أو \(O(N\log_{10}N)\) إذا كتبنا كلفة استخراج الأرقام بشكل صريح. أما حل فضاء الحالات المصغَّر فهو ضئيل جدًا مقارنة بذلك، لأن عدد الحالات الجوهرية التي تحتاج إلى تصنيف لا يتجاوز 567.
أما من جهة الذاكرة، فإن اللب الرياضي يحتاج فقط إلى \(O(567)\) من الوسوم النهائية. وهذا هو تقريبًا ما تستخدمه نسختا C++ وJava مع فروق ثابتة صغيرة. أما نسخة Python فتتبع العودية نفسها، لكنها قد تحتفظ بعدد أكبر من القيم المخزنة لأنها تذكّر المُدخلات تذكيرًا قاموسيًا أثناء الحل.