For a given digit count \(d\), define
$$L=10^{d-1},\qquad H=10^d-1.$$
Write \(\operatorname{Pal}(x)\) for the statement that \(x\) is a decimal palindrome. The target quantity is then
$$M_d=\max\{ab \mid L \le a,b \le H,\ \operatorname{Pal}(ab)\}.$$
In the original Project Euler instance \(d=3\), so both factors are three-digit numbers, but the implementations are structured for a general input \(d \ge 1\). The difficulty is not describing the candidate set; it is searching that set without wasting time on products that cannot possibly beat the current record.
The solution uses three ideas that are completely specific to this problem: the search space can be reduced to an upper triangle because multiplication is commutative, palindromicity is a digit-symmetry predicate, and descending order gives monotone bounds that justify early termination. There is no recurrence here; the central invariant is a best-so-far lower bound on the true optimum.
If \((a,b)\) is admissible, then so is \((b,a)\), and both yield the same product. It is therefore enough to search
$$T_d=\{(a,b)\mid L \le b \le a \le H\}.$$
Every valid factorization appears exactly once in \(T_d\): if a pair satisfies \(a \lt b\), we simply swap the factors. Hence
$$M_d=\max\{ab \mid (a,b)\in T_d,\ \operatorname{Pal}(ab)\}.$$
This halves the search space up to lower-order terms, reducing the candidate count from \(N^2\) ordered pairs to \(N(N+1)/2\), where \(N=H-L+1=9\cdot 10^{d-1}\).
If a non-negative integer has decimal expansion
$$x=\sum_{i=0}^{m} c_i 10^i,$$
then \(x\) is palindromic exactly when
$$c_i=c_{m-i}\qquad(0 \le i \le m).$$
So the mathematical predicate is simply mirror symmetry of digits around the center. Because a product of two \(d\)-digit numbers has at most \(2d\) digits, checking \(\operatorname{Pal}(x)\) costs only \(O(d)\) time. The implementations realize this with decimal strings: Python compares the string with its reversal, while C++ and Java compare mirrored characters from the two ends.
For a fixed first factor \(a\), the products \(ab\) decrease as \(b\) decreases. Across rows, the largest value attainable with first factor \(a\) is \(aH\), and these row maxima also decrease as \(a\) decreases.
Let \(B\) denote the largest palindromic product found so far. Then the first key bound is
$$aH \lt B.$$
If this happens, then every remaining pair with first factor \(a' \le a\) satisfies \(a'b \le aH \lt B\), so no later row can improve the record. The outer loop may stop.
The second key bound is
$$ab \le B.$$
At that moment, every later candidate in the same row has the form \(ab'\) with \(b' \le b\), hence \(ab' \le ab \le B\). So the rest of the current row can be skipped. These two monotonicity facts are the mathematical reason the search is fast in practice.
For \(d=2\) we have \(L=10\) and \(H=99\). The scan starts at the top row \(a=99\), examining
$$99\cdot 99,\ 99\cdot 98,\ 99\cdot 97,\ \dots$$
Eventually it reaches
$$99\cdot 91=9009,$$
which is palindromic, so the running record becomes \(B=9009\). Now inspect what happens when the outer loop would move down to \(a=90\): the largest product still available in that entire row is
$$90\cdot 99=8910 \lt 9009.$$
Therefore every row with first factor \(90\) or smaller is already hopeless, and the outer loop can terminate. The famous two-digit answer is not just a checkpoint; it is also a clean demonstration of how the pruning logic works.
A classical fact about decimal palindromes is that every palindrome with an even number of digits is divisible by 11. Suppose
$$x=\sum_{i=0}^{2k-1} c_i 10^i,\qquad c_i=c_{2k-1-i}.$$
Since \(10\equiv -1 \pmod{11}\), we obtain
$$x\equiv \sum_{i=0}^{2k-1} c_i(-1)^i \pmod{11}.$$
Now pair the terms with indices \(i\) and \(2k-1-i\). Their contribution is
$$c_i(-1)^i+c_{2k-1-i}(-1)^{2k-1-i}=c_i\bigl((-1)^i+(-1)^{2k-1-i}\bigr)=0,$$
because the digits are equal and the signs are opposite. Summing over all pairs gives \(x\equiv 0 \pmod{11}\).
In the three-digit problem this means every six-digit palindromic candidate is a multiple of 11, so a specialized solver may insist that one factor be divisible by 11. The present implementations deliberately keep the simpler general scan, but this theorem explains a well-known optimization for the same task.
The implementations first compute the lower and upper endpoints \(L\) and \(H\). Python uses powers of ten directly. C++ and Java arrive at the same interval by repeated multiplication to form \(10^{d-1}\), then subtract one from the next power of ten to obtain the upper endpoint.
After the interval is known, the implementation loops downward over the first factor and, inside each row, loops downward over the second factor starting from the diagonal \(b=a\). This realizes the triangular search region \(T_d\) exactly once.
Before spending time on the palindrome predicate, the code first asks whether the current product can still beat the running record. If the answer is no, one of the two pruning inequalities triggers and the relevant loop ends immediately. Only products that still have a mathematical chance to improve the answer are tested for decimal symmetry.
All three implementations also verify the known two-digit case by checking that the computed value is \(9009\). That small checkpoint is useful because any off-by-one error in the interval bounds or loop directions would break it immediately.
Let \(N=H-L+1=9\cdot 10^{d-1}\). Because only the triangle \(b \le a\) is scanned, the worst-case number of candidate products is
$$\frac{N(N+1)}{2}=\Theta(N^2)=\Theta(10^{2d}).$$
Each palindrome test inspects at most \(2d\) decimal digits, so a precise worst-case time bound is
$$O(d\,10^{2d}).$$
If \(d\) is treated as fixed, as in the original three-digit problem, this is simply quadratic in the size of the factor range. In practice the runtime is much smaller than the worst-case bound because the running record rises quickly and then excludes entire rows and long suffixes of rows. Memory use is \(O(d)\) for the temporary decimal representation, which is effectively \(O(1)\) when \(d\) is fixed.
Für eine gegebene Stellenzahl \(d\) setzen wir
$$L=10^{d-1},\qquad H=10^d-1.$$
Mit \(\operatorname{Pal}(x)\) bezeichnen wir die Aussage, dass \(x\) in Dezimalschreibweise ein Palindrom ist. Gesucht ist also
$$M_d=\max\{ab \mid L \le a,b \le H,\ \operatorname{Pal}(ab)\}.$$
Im ursprünglichen Project-Euler-Fall ist \(d=3\), also sind beide Faktoren dreistellig. Die Implementierungen sind jedoch für allgemeines \(d \ge 1\) formuliert. Die eigentliche Schwierigkeit liegt nicht in der Definition der Kandidatenmenge, sondern darin, den Suchraum so zu durchlaufen, dass offensichtlich aussichtslose Produkte früh verworfen werden.
Die Lösung beruht auf drei exakt zu dieser Aufgabe passenden Beobachtungen: Wegen der Kommutativität der Multiplikation reicht ein Dreieck statt des ganzen Quadrats, Palindromizität ist reine Ziffernsymmetrie, und die absteigende Durchmusterung liefert monotone Schranken für korrektes Pruning. Eine Rekurrenz wird nicht benötigt; die zentrale Invariante ist eine stets wachsende Untergrenze für das Optimum.
Wenn \((a,b)\) zulässig ist, dann ist auch \((b,a)\) zulässig, und beide Paare erzeugen dasselbe Produkt. Daher genügt es, nur
$$T_d=\{(a,b)\mid L \le b \le a \le H\}$$
zu durchsuchen. Jede gültige Faktorisierung erscheint dort genau einmal: Falls \(a \lt b\), vertauscht man einfach die Faktoren. Also gilt
$$M_d=\max\{ab \mid (a,b)\in T_d,\ \operatorname{Pal}(ab)\}.$$
Damit schrumpft die Kandidatenzahl von \(N^2\) geordneten Paaren auf \(N(N+1)/2\), wobei \(N=H-L+1=9\cdot 10^{d-1}\) ist.
Hat eine nichtnegative ganze Zahl die Dezimaldarstellung
$$x=\sum_{i=0}^{m} c_i 10^i,$$
dann ist \(x\) genau dann ein Palindrom, wenn
$$c_i=c_{m-i}\qquad(0 \le i \le m)$$
für alle Positionen gilt. Mathematisch ist das also nichts anderes als Spiegelung der Ziffern um die Mitte. Da das Produkt zweier \(d\)-stelliger Zahlen höchstens \(2d\) Stellen hat, kostet der Test \(\operatorname{Pal}(x)\) nur \(O(d)\) Zeit. Die Implementierungen setzen das über Dezimalstrings um: Python vergleicht mit der umgedrehten Zeichenfolge, C++ und Java vergleichen symmetrische Zeichen von außen nach innen.
Für festes \(a\) werden die Produkte \(ab\) kleiner, wenn \(b\) kleiner wird. Zwischen verschiedenen Zeilen ist das größte noch erreichbare Produkt der Zeile \(a\) gleich \(aH\), und auch diese Zeilenmaxima werden kleiner, wenn \(a\) sinkt.
Sei \(B\) das bislang größte gefundene palindromische Produkt. Die erste Schrankung lautet
$$aH \lt B.$$
Dann erfüllt jedes verbleibende Paar mit erstem Faktor \(a' \le a\) die Ungleichung \(a'b \le aH \lt B\). Spätere Zeilen können den Rekord also nicht mehr verbessern, und die äußere Schleife darf enden.
Die zweite Schrankung lautet
$$ab \le B.$$
In diesem Moment gilt für jedes weitere Paar derselben Zeile \(ab' \le ab \le B\), weil \(b' \le b\) ist. Also darf der Rest der aktuellen Zeile übersprungen werden. Genau diese beiden Monotonieaussagen machen das Verfahren praktisch schnell.
Für \(d=2\) gilt \(L=10\) und \(H=99\). Die Suche beginnt ganz oben bei \(a=99\) und betrachtet
$$99\cdot 99,\ 99\cdot 98,\ 99\cdot 97,\ \dots$$
Schließlich erreicht sie
$$99\cdot 91=9009,$$
und \(9009\) ist ein Palindrom. Damit wird der laufende Rekord zu \(B=9009\). Nun betrachtet man die nächste relevante Zeilengrenze: Für \(a=90\) ist selbst das größte noch mögliche Produkt nur
$$90\cdot 99=8910 \lt 9009.$$
Also kann keine Zeile mit erstem Faktor \(90\) oder kleiner noch gewinnen. Die äußere Schleife darf abbrechen. Das bekannte zweistellige Ergebnis ist damit zugleich ein anschauliches Beispiel für die Korrektheit des Prunings.
Eine klassische Zahlentheorie-Beobachtung besagt: Jedes Palindrom mit gerader Ziffernanzahl ist durch 11 teilbar. Sei dazu
$$x=\sum_{i=0}^{2k-1} c_i 10^i,\qquad c_i=c_{2k-1-i}.$$
Wegen \(10\equiv -1 \pmod{11}\) folgt
$$x\equiv \sum_{i=0}^{2k-1} c_i(-1)^i \pmod{11}.$$
Fasst man die Terme mit Indizes \(i\) und \(2k-1-i\) zusammen, erhält man
$$c_i(-1)^i+c_{2k-1-i}(-1)^{2k-1-i}=c_i\bigl((-1)^i+(-1)^{2k-1-i}\bigr)=0.$$
Alle Paare heben sich also weg, und insgesamt ist \(x\equiv 0 \pmod{11}\).
Im dreistelligen Problem heißt das: Jeder sechsstellige palindromische Kandidat ist ein Vielfaches von 11, also kann ein spezialisierter Suchalgorithmus einen Faktor auf Vielfache von 11 beschränken. Die vorliegenden Implementierungen verwenden bewusst die allgemeinere absteigende Suche, aber der Satz erklärt eine bekannte Optimierung derselben Aufgabe.
Zuerst werden die Intervallgrenzen \(L\) und \(H\) berechnet. Python verwendet Potenzen von 10 direkt. C++ und Java erzeugen \(10^{d-1}\) durch wiederholte Multiplikation und gewinnen die obere Grenze dann als „nächste Zehnerpotenz minus eins“.
Danach läuft die Implementierung den ersten Faktor von \(H\) nach \(L\) ab und innerhalb jeder Zeile den zweiten Faktor von \(a\) nach \(L\). Dadurch wird der Bereich \(T_d\) genau einmal untersucht.
Bevor überhaupt ein Palindromtest durchgeführt wird, prüft der Code, ob das aktuelle Produkt den Rekord noch schlagen kann. Falls nicht, beendet eine der beiden oben hergeleiteten Schranken sofort die innere oder äußere Schleife. Nur Produkte, die numerisch noch Aussicht auf Verbesserung haben, werden auf Ziffernsymmetrie geprüft.
Alle drei Implementierungen prüfen zusätzlich den bekannten zweistelligen Fall und erwarten dort den Wert \(9009\). Das ist ein nützlicher Schutz gegen Off-by-one-Fehler bei den Intervallgrenzen oder der Laufrichtung der Schleifen.
Mit \(N=H-L+1=9\cdot 10^{d-1}\) werden im schlimmsten Fall höchstens
$$\frac{N(N+1)}{2}=\Theta(N^2)=\Theta(10^{2d})$$
Kandidatenprodukte erzeugt, weil nur das Dreieck \(b \le a\) durchsucht wird. Jeder Palindromtest betrachtet höchstens \(2d\) Dezimalstellen, also lautet eine präzise Worst-Case-Zeitabschätzung
$$O(d\,10^{2d}).$$
Für festes \(d\), insbesondere im ursprünglichen Fall \(d=3\), ist das einfach quadratisch in der Größe des Faktorenintervalls. Praktisch ist die Laufzeit deutlich kleiner, weil der Rekordwert meist früh ansteigt und danach ganze Zeilen oder lange Zeilenenden ausgeschlossen werden. Der Speicherverbrauch beträgt \(O(d)\) für die temporäre Dezimaldarstellung und damit bei festem \(d\) effektiv \(O(1)\).
Verilen bir \(d\) basamak sayısı için
$$L=10^{d-1},\qquad H=10^d-1$$
olsun. \(\operatorname{Pal}(x)\) ifadesi, \(x\)'in onluk tabanda palindrom olduğunu göstersin. Aranan değer
$$M_d=\max\{ab \mid L \le a,b \le H,\ \operatorname{Pal}(ab)\}$$
şeklindedir. Orijinal Project Euler sorusunda \(d=3\) olduğu için iki çarpan da üç basamaklıdır; fakat uygulamalar genel olarak \(d \ge 1\) için yazılmıştır. Asıl mesele aday kümesini tanımlamak değil, açıkça kazanma şansı olmayan çarpımları erkenden eleyerek aramayı verimli hale getirmektir.
Çözüm bu probleme tam oturan üç fikre dayanır: çarpmanın değişme özelliği sayesinde kare yerine üçgensel bir arama bölgesi yeterlidir, palindrom koşulu basamak simetrisidir ve azalan sırada tarama yapmak iki güçlü budama eşitsizliği verir. Bir özyineleme veya kapalı form yoktur; temel değişmez, şimdiye kadar bulunan en iyi palindromun oluşturduğu alt sınırdır.
\((a,b)\) geçerliyse \((b,a)\) da geçerlidir ve her ikisi de aynı çarpımı verir. Bu yüzden yalnızca
$$T_d=\{(a,b)\mid L \le b \le a \le H\}$$
bölgesini taramak yeterlidir. Her uygun çarpan çifti burada tam bir kez görünür; eğer \(a \lt b\) ise çarpanları yer değiştiririz. Dolayısıyla
$$M_d=\max\{ab \mid (a,b)\in T_d,\ \operatorname{Pal}(ab)\}$$
yazılabilir. Böylece aday sayısı \(N^2\) sıralı çiftten \(N(N+1)/2\) çifte iner; burada \(N=H-L+1=9\cdot 10^{d-1}\).
Negatif olmayan bir tamsayının ondalık açılımı
$$x=\sum_{i=0}^{m} c_i 10^i$$
olsun. O halde \(x\), ancak ve ancak
$$c_i=c_{m-i}\qquad(0 \le i \le m)$$
koşulu sağlanıyorsa palindromdur. Yani matematiksel olarak aranan şey, basamakların ortaya göre aynalı olmasıdır. İki \(d\) basamaklı sayının çarpımı en fazla \(2d\) basamaklı olacağından \(\operatorname{Pal}(x)\) testinin maliyeti \(O(d)\) olur. Uygulamalarda bu test ondalık string üzerinden yapılır: Python string'i ters çevirip karşılaştırır; C++ ve Java ise iki uçtan merkeze doğru simetrik karakterleri karşılaştırır.
Sabit bir \(a\) için \(ab\) çarpımları, \(b\) azaldıkça azalır. Farklı satırlar arasında ise ilk çarpanı \(a\) olan satırın ulaşabileceği en büyük değer \(aH\)'dir ve bu üst sınır da \(a\) küçüldükçe azalır.
\(B\), o ana kadar bulunan en büyük palindrom çarpım olsun. İlk kritik eşitsizlik
$$aH \lt B$$
şeklindedir. Bu durumda birinci çarpanı \(a' \le a\) olan her kalan çift için \(a'b \le aH \lt B\) geçerlidir. Demek ki sonraki hiçbir satır rekoru geçemez; dış döngü durdurulabilir.
İkinci kritik eşitsizlik ise
$$ab \le B$$
olur. Çünkü aynı satırda bundan sonra bakılacak her değer \(ab'\) biçimindedir ve \(b' \le b\) olduğundan \(ab' \le ab \le B\) olur. Yani satırın geri kalanı atlanabilir. Uygulamaların pratikte hızlı olmasının nedeni tam olarak bu iki monotonluk olgusudur.
\(d=2\) için \(L=10\) ve \(H=99\) olur. Arama en üst satırdan, yani \(a=99\) ile başlar ve
$$99\cdot 99,\ 99\cdot 98,\ 99\cdot 97,\ \dots$$
ürünlerini inceler. Bir süre sonra
$$99\cdot 91=9009$$
değerine ulaşılır ve bu sayı palindromdur. Böylece geçici rekor \(B=9009\) olur. Şimdi dış döngünün \(a=90\) satırına gelmesi durumuna bakalım: bu satırdaki en büyük mümkün çarpım
$$90\cdot 99=8910 \lt 9009$$
olduğundan, \(90\) ve daha küçük ilk çarpanlarla kurulacak hiçbir satır artık kazanamaz. Dış döngü durur. İki basamaklı meşhur sonuç sadece bir doğrulama noktası değil, budamanın neden doğru olduğunu gösteren somut bir örnektir.
Onluk tabanda çift sayıda basamağa sahip her palindromun 11'e bölündüğü bilinir. Şöyle yazalım:
$$x=\sum_{i=0}^{2k-1} c_i 10^i,\qquad c_i=c_{2k-1-i}.$$
\(10\equiv -1 \pmod{11}\) olduğundan
$$x\equiv \sum_{i=0}^{2k-1} c_i(-1)^i \pmod{11}$$
elde edilir. \(i\) ile \(2k-1-i\) indeksli terimleri eşleyince katkı
$$c_i(-1)^i+c_{2k-1-i}(-1)^{2k-1-i}=c_i\bigl((-1)^i+(-1)^{2k-1-i}\bigr)=0$$
olur; çünkü basamaklar eşit, işaretler zıttır. Tüm çiftler toplanınca \(x\equiv 0 \pmod{11}\) bulunur.
Üç basamaklı çarpanlar probleminde bunun anlamı şudur: altı basamaklı her palindrom aday 11'in katıdır. O halde altı basamaklı adaylara özel bir çözüm, çarpanlardan en az birini 11'in katı olmak üzere sınırlayabilir. Mevcut uygulamalar daha sade olan genel azalan taramayı korur; yine de bu teorem, aynı problem için bilinen klasik optimizasyonu açıklar.
Önce \(L\) ve \(H\) sınırları hesaplanır. Python bunu doğrudan 10'un kuvvetleriyle yapar. C++ ve Java ise tekrar tekrar 10 ile çarparak \(10^{d-1}\) değerini oluşturur, ardından bir sonraki 10 kuvvetinden 1 çıkararak üst sınırı elde eder.
Daha sonra uygulama birinci çarpanı \(H\)'den \(L\)'ye doğru azaltır; her satırda ikinci çarpan da \(a\)'dan \(L\)'ye doğru azaltılır. Böylece \(T_d\) bölgesi tam bir kez ziyaret edilir.
Palindrom testi yapılmadan önce, o anki çarpımın mevcut rekoru geçme ihtimali olup olmadığına bakılır. Eğer bu ihtimal yoksa yukarıda türetilen iki eşitsizlikten biri devreye girer ve ilgili döngü hemen biter. Yalnızca gerçekten kazanma şansı olan çarpımlar basamak simetrisi açısından incelenir.
Üç uygulamanın hepsi ayrıca iki basamaklı örneği kontrol eder ve elde edilen değerin \(9009\) olmasını bekler. Bu küçük test, aralık sınırlarında veya döngü yönlerinde yapılacak bir sınır hatasını anında ortaya çıkarır.
\(N=H-L+1=9\cdot 10^{d-1}\) olsun. Yalnızca \(b \le a\) üçgeni tarandığı için en kötü durumda incelenen aday çarpım sayısı
$$\frac{N(N+1)}{2}=\Theta(N^2)=\Theta(10^{2d})$$
olur. Her palindrom testi en fazla \(2d\) ondalık basamağa baktığından, kesin worst-case zaman sınırı
$$O(d\,10^{2d})$$
şeklindedir. \(d\) sabit kabul edilirse, özellikle orijinal \(d=3\) probleminde bu sadece faktör aralığının büyüklüğü açısından karesel davranış demektir. Pratikte çalışma süresi bundan çok daha küçüktür; çünkü rekor değer genellikle erken yükselir ve sonra bütün satırları veya satır kuyruklarını oyunun dışına iter. Bellek kullanımı geçici ondalık gösterim için \(O(d)\), sabit \(d\) için ise fiilen \(O(1)\)'dir.
Para un número de dígitos \(d\), definimos
$$L=10^{d-1},\qquad H=10^d-1.$$
Escribimos \(\operatorname{Pal}(x)\) para indicar que \(x\) es un palíndromo decimal. Entonces el objetivo es
$$M_d=\max\{ab \mid L \le a,b \le H,\ \operatorname{Pal}(ab)\}.$$
En la versión original de Project Euler se toma \(d=3\), de modo que ambos factores tienen tres cifras, aunque las implementaciones están escritas para un \(d \ge 1\) general. El reto no consiste en formular el conjunto de candidatos, sino en recorrerlo de forma inteligente y descartar pronto los productos que ya no pueden mejorar la mejor respuesta conocida.
La solución se apoya en tres observaciones muy concretas para este problema: por conmutatividad basta un triángulo en vez de todo el cuadrado, la condición de palíndromo es una simetría de cifras, y el orden descendente produce cotas monótonas que justifican la poda. No hace falta ninguna recurrencia; el invariante central es la mejor cota inferior disponible para el óptimo verdadero.
Si \((a,b)\) es un par válido, entonces \((b,a)\) también lo es y ambos dan el mismo producto. Por eso basta recorrer
$$T_d=\{(a,b)\mid L \le b \le a \le H\}.$$
Toda factorización admisible aparece exactamente una vez en \(T_d\): si \(a \lt b\), simplemente se intercambian los factores. En consecuencia,
$$M_d=\max\{ab \mid (a,b)\in T_d,\ \operatorname{Pal}(ab)\}.$$
Esto reduce el número de candidatos desde \(N^2\) pares ordenados hasta \(N(N+1)/2\), donde \(N=H-L+1=9\cdot 10^{d-1}\).
Si un entero no negativo tiene expansión decimal
$$x=\sum_{i=0}^{m} c_i 10^i,$$
entonces \(x\) es palíndromo exactamente cuando
$$c_i=c_{m-i}\qquad(0 \le i \le m).$$
Es decir, las cifras deben reflejarse alrededor del centro. Como el producto de dos números de \(d\) cifras tiene a lo sumo \(2d\) cifras, comprobar \(\operatorname{Pal}(x)\) cuesta solo \(O(d)\). Las implementaciones lo realizan con cadenas decimales: Python compara la cadena con su reverso, mientras que C++ y Java comparan caracteres simétricos desde ambos extremos.
Para un primer factor fijo \(a\), los productos \(ab\) disminuyen cuando \(b\) disminuye. Entre filas distintas, el mayor valor que puede producir la fila de \(a\) es \(aH\), y esos máximos de fila también decrecen cuando \(a\) decrece.
Sea \(B\) el mayor producto palindrómico hallado hasta el momento. La primera cota clave es
$$aH \lt B.$$
Si eso ocurre, entonces cualquier par restante con primer factor \(a' \le a\) satisface \(a'b \le aH \lt B\). Ninguna fila posterior puede mejorar el récord, así que el bucle exterior puede terminar.
La segunda cota clave es
$$ab \le B.$$
En ese instante, cualquier candidato posterior de la misma fila tiene la forma \(ab'\) con \(b' \le b\), luego \(ab' \le ab \le B\). Por tanto, el resto de la fila puede omitirse. Estas dos monotonicidades son la razón matemática por la que el algoritmo resulta rápido en la práctica.
Para \(d=2\), se tiene \(L=10\) y \(H=99\). La búsqueda empieza en la fila superior \(a=99\), examinando
$$99\cdot 99,\ 99\cdot 98,\ 99\cdot 97,\ \dots$$
Finalmente aparece
$$99\cdot 91=9009,$$
que sí es palindrómico, de modo que el récord provisional pasa a ser \(B=9009\). Ahora observemos qué sucede cuando el bucle exterior alcanzaría \(a=90\): incluso el mayor producto de esa fila vale
$$90\cdot 99=8910 \lt 9009.$$
Así, ninguna fila con primer factor \(90\) o menor puede superar el récord y el bucle exterior puede detenerse. El resultado clásico de dos cifras no solo sirve como comprobación; también ilustra con claridad por qué la poda es correcta.
Un hecho clásico es que todo palíndromo decimal con un número par de cifras es divisible por 11. Supongamos
$$x=\sum_{i=0}^{2k-1} c_i 10^i,\qquad c_i=c_{2k-1-i}.$$
Como \(10\equiv -1 \pmod{11}\), obtenemos
$$x\equiv \sum_{i=0}^{2k-1} c_i(-1)^i \pmod{11}.$$
Al emparejar los términos de índices \(i\) y \(2k-1-i\), la contribución es
$$c_i(-1)^i+c_{2k-1-i}(-1)^{2k-1-i}=c_i\bigl((-1)^i+(-1)^{2k-1-i}\bigr)=0,$$
porque las cifras son iguales y los signos opuestos. La suma total es, por tanto, \(0 \pmod{11}\).
En el problema de tres cifras esto implica que cualquier candidato palindrómico de seis cifras es múltiplo de 11, de modo que una búsqueda especializada puede imponer que al menos uno de los factores sea divisible por 11. Las implementaciones actuales prefieren el barrido descendente general, pero este teorema explica una optimización clásica del mismo problema.
Primero se calculan los extremos \(L\) y \(H\). Python usa potencias de 10 de forma directa. C++ y Java llegan al mismo intervalo mediante multiplicaciones repetidas para formar \(10^{d-1}\), y después obtienen el extremo superior como la siguiente potencia de 10 menos uno.
Después, la implementación recorre el primer factor desde \(H\) hasta \(L\), y dentro de cada fila recorre el segundo factor desde \(a\) hasta \(L\). Así se visita exactamente una vez la región triangular \(T_d\).
Antes de aplicar el predicado de palíndromo, el código pregunta si el producto actual todavía puede superar el mejor valor registrado. Si la respuesta es negativa, una de las dos desigualdades de poda termina inmediatamente el bucle interior o el exterior. Solo los productos que aún tienen posibilidades matemáticas de ganar se someten a la comprobación de simetría decimal.
Las tres implementaciones también validan el caso conocido de dos cifras y esperan obtener \(9009\). Ese control pequeño detecta de inmediato errores de límites o de dirección en los bucles.
Sea \(N=H-L+1=9\cdot 10^{d-1}\). Como solo se examina el triángulo \(b \le a\), el número máximo de productos candidatos es
$$\frac{N(N+1)}{2}=\Theta(N^2)=\Theta(10^{2d}).$$
Cada prueba de palíndromo inspecciona a lo sumo \(2d\) cifras decimales, así que una cota precisa en el peor caso es
$$O(d\,10^{2d}).$$
Si \(d\) se trata como constante, como ocurre en el problema original con \(d=3\), esto equivale simplemente a un comportamiento cuadrático en el tamaño del intervalo de factores. En la práctica el tiempo es mucho menor porque el récord crece pronto y luego descarta filas completas y largos sufijos de fila. El uso de memoria es \(O(d)\) por la representación decimal temporal y, por tanto, efectivamente \(O(1)\) cuando \(d\) es fijo.
给定一个位数参数 \(d\)，记
$$L=10^{d-1},\qquad H=10^d-1.$$
用 \(\operatorname{Pal}(x)\) 表示“\(x\) 是十进制回文数”。那么目标可以写成
$$M_d=\max\{ab \mid L \le a,b \le H,\ \operatorname{Pal}(ab)\}.$$
原始的 Project Euler 题目取 \(d=3\)，也就是寻找两个三位数乘积中的最大回文数。不过实现本身对任意 \(d \ge 1\) 都适用。真正的难点不是写下这个定义，而是在不遗漏正确答案的前提下，尽快排除那些已经不可能刷新当前最优值的候选乘积。
这个解法没有用到复杂递推或高深公式，而是牢牢抓住了本题最核心的三个对象：乘法的对称性、十进制回文的镜像结构，以及按降序枚举时自然出现的单调上界。换句话说，算法的力量来自正确地组织搜索空间，并维护“当前已知最好值”这个不变信息。
如果 \((a,b)\) 是合法因子对，那么 \((b,a)\) 也是合法的，而且两者给出的乘积完全相同。这意味着没有必要在整个正方形区域上重复搜索，只需要考察
$$T_d=\{(a,b)\mid L \le b \le a \le H\}.$$
任何满足 \(L \le a,b \le H\) 的分解都能在这里恰好出现一次：若原本 \(a \lt b\)，交换两个因子即可。因此
$$M_d=\max\{ab \mid (a,b)\in T_d,\ \operatorname{Pal}(ab)\}.$$
设可选因子的总数为 \(N=H-L+1=9\cdot 10^{d-1}\)。若搜索整个正方形，需要考虑 \(N^2\) 个有序对；改成三角形后，候选数立刻降为 \(N(N+1)/2\)。这一步虽然朴素，却是后续一切优化的基础。
设一个非负整数的十进制展开为
$$x=\sum_{i=0}^{m} c_i 10^i.$$
那么 \(x\) 是回文数，当且仅当
$$c_i=c_{m-i}\qquad(0 \le i \le m).$$
也就是说，从最低位往上数的第 \(i\) 位，必须与从最高位往下数的第 \(i\) 位完全相同。这个条件与本题的乘积结构结合得非常自然，因为两个 \(d\) 位数的乘积最多只有 \(2d\) 位，所以一次回文判断只需要检查至多 \(2d\) 个字符，代价是 \(O(d)\)。实现层面上，Python 直接把十进制字符串反转后比较；C++ 和 Java 则从两端向中间逐位对比。这两种写法在数学上做的是同一件事。
固定第一因子 \(a\) 后，函数 \(b \mapsto ab\) 会随着 \(b\) 的减小而单调下降。另一方面，在整行搜索中，第一因子固定为 \(a\) 时所能得到的最大乘积是 \(aH\)，而当 \(a\) 继续减小时，这个行上界也会继续下降。
设 \(B\) 是当前已经找到的最大回文乘积。第一个核心判据是
$$aH \lt B.$$
一旦这个不等式成立，那么所有尚未扫描的后续行都满足第一因子 \(a' \le a\)，于是任意剩余乘积都有 \(a'b \le aH \lt B\)。这说明后面整片区域都不可能超过当前记录，外层循环可以直接停止。
第二个核心判据是
$$ab \le B.$$
这时在同一行中后续要看的任何候选都形如 \(ab'\)，其中 \(b' \le b\)，所以必有 \(ab' \le ab \le B\)。于是当前行剩下的部分也不可能再产生更优答案，内层循环可以提前结束。
这两个不等式不是经验技巧，而是由乘积的单调性直接推出的严格结论。它们也是代码真正快起来的原因：一旦出现足够大的回文数，后面大量候选就会被整体剪掉。
当 \(d=2\) 时，区间是 \(L=10\)、\(H=99\)。搜索从最上方一行 \(a=99\) 开始，依次考察
$$99\cdot 99,\ 99\cdot 98,\ 99\cdot 97,\ \dots$$
继续向下检查时，会遇到
$$99\cdot 91=9009,$$
而 \(9009\) 正是回文数，于是记录值更新为 \(B=9009\)。接下来观察外层循环如果下降到 \(a=90\) 会发生什么：这一整行里能得到的最大乘积也不过是
$$90\cdot 99=8910 \lt 9009.$$
这就意味着第一因子不超过 \(90\) 的任何后续行都已经彻底失去竞争力，外层循环立刻可以停止。这个两位数例子不仅是一个已知校验值，更是剪枝正确性的完整微型示范。
本题还有一个很有名的数论事实可用：十进制下只要回文数的位数是偶数，它就一定是 11 的倍数。设
$$x=\sum_{i=0}^{2k-1} c_i 10^i,\qquad c_i=c_{2k-1-i}.$$
由于 \(10\equiv -1 \pmod{11}\)，有
$$x\equiv \sum_{i=0}^{2k-1} c_i(-1)^i \pmod{11}.$$
现在把第 \(i\) 项和第 \(2k-1-i\) 项配成一对，它们的贡献为
$$c_i(-1)^i+c_{2k-1-i}(-1)^{2k-1-i}=c_i\bigl((-1)^i+(-1)^{2k-1-i}\bigr)=0.$$
原因很简单：对应数字相等，而符号一正一负。所有成对项都相消，所以总和模 11 为 0。
放回本题语境，如果关注的是两个三位数相乘，那么任何六位回文候选一定是 11 的倍数，因此可以构造一种更专门的搜索：强制至少一个因子是 11 的倍数。当前实现没有采用这条优化，而是保留了更一般、更直接的降序扫描，但这个定理解释了为什么许多关于本题的经典解法都会提到 11。
实现的第一步是求出 \(L\) 与 \(H\)。Python 直接使用 10 的幂来得到区间；C++ 和 Java 则通过重复乘以 10 构造出 \(10^{d-1}\)，再用“下一幂减一”的方式得到上界。这些写法不同，但数学对象完全一致。
在边界确定后，程序从 \(H\) 向下枚举第一因子；对每个固定的第一因子，再从 \(a\) 向下枚举第二因子。这样正好覆盖 \(T_d\) 而不会重复考察同一个无序因子对。
真正重要的是顺序安排：程序不会先对每个乘积做回文判断，而是先看它是否还有可能超过当前记录。如果连数值上都不可能改写答案，就直接依据前面的两个不等式结束内层或外层循环。只有仍有获胜机会的乘积，才会进入回文判定步骤。
三个语言版本还都会检查两位数情形，并要求算出的值等于 \(9009\)。这一步虽然很小，却能有效防止上下界写错、循环方向写反或终止条件失误等边界问题。
设 \(N=H-L+1=9\cdot 10^{d-1}\)。由于只扫描 \(b \le a\) 的三角区域，最坏情况下最多生成
$$\frac{N(N+1)}{2}=\Theta(N^2)=\Theta(10^{2d})$$
个候选乘积。每次回文判断最多检查 \(2d\) 个十进制字符，因此更精确的最坏时间复杂度是
$$O(d\,10^{2d}).$$
如果把 \(d\) 看成固定常数，尤其在原题 \(d=3\) 时，这就等价于对因子区间做平方级搜索。实际运行往往明显快于这个上界，因为一旦找到较大的回文数，整行和行尾就会被大量剪掉。额外空间主要来自临时十进制表示，规模为 \(O(d)\)；当 \(d\) 固定时可视为 \(O(1)\)。
Для заданного числа цифр \(d\) положим
$$L=10^{d-1},\qquad H=10^d-1.$$
Обозначим через \(\operatorname{Pal}(x)\) утверждение, что \(x\) является десятичным палиндромом. Тогда нужно найти
$$M_d=\max\{ab \mid L \le a,b \le H,\ \operatorname{Pal}(ab)\}.$$
В исходной задаче Project Euler берётся \(d=3\), то есть оба множителя трёхзначные, однако сами реализации написаны так, чтобы работать и для общего \(d \ge 1\). Трудность здесь не в формуле для ответа, а в том, чтобы обойти пространство кандидатов без бессмысленной проверки произведений, которые уже точно не смогут улучшить текущий рекорд.
Решение опирается на три строго предметные идеи: коммутативность умножения позволяет заменить квадрат поиска треугольником, условие палиндрома есть условие зеркальной симметрии цифр, а перебор по убыванию даёт монотонные границы для ранней остановки. Рекуррентных соотношений здесь нет; главный инвариант — это наилучшая палиндромная нижняя граница, найденная к текущему моменту.
Если пара \((a,b)\) допустима, то допустима и пара \((b,a)\), причём произведение одно и то же. Поэтому достаточно просматривать только область
$$T_d=\{(a,b)\mid L \le b \le a \le H\}.$$
Любое допустимое разложение появляется в \(T_d\) ровно один раз: если исходно \(a \lt b\), множители просто меняются местами. Следовательно,
$$M_d=\max\{ab \mid (a,b)\in T_d,\ \operatorname{Pal}(ab)\}.$$
Если обозначить число допустимых множителей через \(N=H-L+1=9\cdot 10^{d-1}\), то количество кандидатов снижается с \(N^2\) упорядоченных пар до \(N(N+1)/2\).
Пусть неотрицательное целое число имеет десятичное разложение
$$x=\sum_{i=0}^{m} c_i 10^i.$$
Тогда \(x\) является палиндромом тогда и только тогда, когда
$$c_i=c_{m-i}\qquad(0 \le i \le m).$$
Иначе говоря, цифры должны зеркально совпадать относительно центра. Поскольку произведение двух \(d\)-значных чисел содержит не более \(2d\) цифр, стоимость предиката \(\operatorname{Pal}(x)\) равна \(O(d)\). В реализациях это выражено через строки: Python сравнивает строку с перевёрнутой копией, а C++ и Java идут от концов к середине и сверяют симметричные символы.
При фиксированном первом множителе \(a\) значения \(ab\) убывают вместе с уменьшением \(b\). Между разными строками максимальный продукт, который вообще может дать строка с первым множителем \(a\), равен \(aH\), и эта верхняя граница тоже убывает вместе с \(a\).
Пусть \(B\) — наибольший палиндромный продукт, найденный к текущему моменту. Первая ключевая оценка имеет вид
$$aH \lt B.$$
Если она выполняется, то для любого ещё не просмотренного ряда с первым множителем \(a' \le a\) и любого второго множителя \(b\) верно \(a'b \le aH \lt B\). Значит, улучшить рекорд уже невозможно, и внешний цикл можно завершить.
Вторая ключевая оценка такова:
$$ab \le B.$$
Тогда любой следующий кандидат в той же строке имеет вид \(ab'\) с \(b' \le b\), следовательно \(ab' \le ab \le B\). Оставшуюся часть строки можно не рассматривать. Эти две монотонности и составляют математическую основу практического ускорения.
При \(d=2\) имеем \(L=10\) и \(H=99\). Поиск начинается с верхней строки \(a=99\) и рассматривает
$$99\cdot 99,\ 99\cdot 98,\ 99\cdot 97,\ \dots$$
Через некоторое время встречается
$$99\cdot 91=9009,$$
а это уже палиндром. Значит, текущий рекорд становится равным \(B=9009\). Теперь посмотрим, что произойдёт, когда внешний цикл дойдёт до \(a=90\): даже наибольший продукт в этой строке равен
$$90\cdot 99=8910 \lt 9009.$$
Следовательно, ни одна строка с первым множителем \(90\) или меньше уже не способна улучшить ответ. Внешний цикл можно прервать. Известный двузначный результат служит здесь не только тестом, но и наглядным примером корректности отсечения.
Есть и полезный теоретический факт: любой десятичный палиндром с чётным числом цифр делится на 11. Пусть
$$x=\sum_{i=0}^{2k-1} c_i 10^i,\qquad c_i=c_{2k-1-i}.$$
Так как \(10\equiv -1 \pmod{11}\), имеем
$$x\equiv \sum_{i=0}^{2k-1} c_i(-1)^i \pmod{11}.$$
Складывая попарно члены с индексами \(i\) и \(2k-1-i\), получаем вклад
$$c_i(-1)^i+c_{2k-1-i}(-1)^{2k-1-i}=c_i\bigl((-1)^i+(-1)^{2k-1-i}\bigr)=0,$$
потому что цифры равны, а знаки противоположны. Значит, вся сумма равна \(0 \pmod{11}\).
Для задачи о произведении трёхзначных чисел это означает: любой шестизначный палиндромный кандидат кратен 11, и специализированный алгоритм мог бы требовать, чтобы хотя бы один множитель делился на 11. Текущие реализации сохраняют более общий нисходящий перебор, но этот факт объясняет популярную оптимизацию той же задачи.
Сначала вычисляются границы \(L\) и \(H\). В Python это делается напрямую через степени десяти. В C++ и Java нижняя граница строится повторным умножением на 10, а верхняя получается как следующая степень десяти минус единица.
После вычисления границ программа идёт по первому множителю от \(H\) вниз к \(L\), а внутри каждой строки по второму множителю от \(a\) вниз к \(L\). Так область \(T_d\) просматривается ровно один раз без повторов симметричных пар.
Перед проверкой палиндромности код сначала оценивает, способен ли текущий продукт вообще превзойти рекорд. Если нет, немедленно срабатывает одна из двух описанных выше отсечек, и внутренний или внешний цикл завершается. На проверку симметрии попадают только те произведения, которые ещё имеют математический шанс стать новым максимумом.
Все три реализации также контролируют двузначный пример и ожидают получить \(9009\). Это небольшая, но полезная защита от ошибок на границах диапазона и в логике циклов.
Пусть \(N=H-L+1=9\cdot 10^{d-1}\). Поскольку просматривается только треугольник \(b \le a\), в худшем случае возникает не более
$$\frac{N(N+1)}{2}=\Theta(N^2)=\Theta(10^{2d})$$
кандидатных произведений. Каждая проверка палиндрома рассматривает не более \(2d\) десятичных цифр, поэтому точная верхняя оценка времени равна
$$O(d\,10^{2d}).$$
Если считать \(d\) фиксированным, как в исходной задаче с \(d=3\), это просто квадратичное поведение по размеру диапазона множителей. На практике время заметно меньше, потому что большой палиндром обычно находится довольно рано, после чего отсечки исключают целые строки и длинные хвосты строк. Дополнительная память составляет \(O(d)\) на временное десятичное представление, то есть фактически \(O(1)\) для фиксированного \(d\).
لعدد خانات معطى \(d\)، نعرّف
$$L=10^{d-1},\qquad H=10^d-1.$$
ولنرمز بـ \(\operatorname{Pal}(x)\) إلى كون \(x\) عدداً متناظراً في الكتابة العشرية. عندئذ تصبح الكمية المطلوبة
$$M_d=\max\{ab \mid L \le a,b \le H,\ \operatorname{Pal}(ab)\}.$$
في صيغة Project Euler الأصلية نأخذ \(d=3\)، أي إن العاملين كلاهما من ثلاثة أرقام، لكن التنفيذات نفسها قابلة للتعميم على أي \(d \ge 1\). الصعوبة الحقيقية ليست في تعريف مجموعة المرشحين، بل في المرور عليها بطريقة تستبعد مبكراً كل حاصل ضرب لم يعد قادراً على تحسين أفضل قيمة عُثر عليها حتى الآن.
يعتمد الحل على ثلاث أفكار مرتبطة مباشرة بهذه المسألة: خاصية التبديل في الضرب تسمح باختزال مربع البحث إلى مثلث، وشرط التناظر هو مجرد تماثل في الأرقام العشرية، والترتيب التنازلي يولّد حدوداً أحادية الاتجاه تبرر الإيقاف المبكر. لا توجد هنا علاقة عودية؛ الفكرة المحورية هي الاحتفاظ بأفضل حد سفلي معروف للحل الأمثل الحقيقي.
إذا كانت \((a,b)\) زوجاً مقبولاً، فإن \((b,a)\) مقبول أيضاً ويعطي الناتج نفسه. لذلك يكفي أن نفتش في المنطقة
$$T_d=\{(a,b)\mid L \le b \le a \le H\}.$$
كل تحليل صحيح يظهر داخل \(T_d\) مرة واحدة بالضبط؛ فإذا كان \(a \lt b\) نبدّل العاملين فقط. ومن ثم
$$M_d=\max\{ab \mid (a,b)\in T_d,\ \operatorname{Pal}(ab)\}.$$
إذا كان عدد العوامل الممكنة هو \(N=H-L+1=9\cdot 10^{d-1}\)، فإن هذا الاختزال ينقلنا من \(N^2\) أزواج مرتبة إلى \(N(N+1)/2\) زوجاً فقط. هذه خطوة بسيطة شكلاً، لكنها أساس كل ما بعدها.
إذا كان لدينا عدد صحيح غير سالب على الصورة
$$x=\sum_{i=0}^{m} c_i 10^i,$$
فإنه يكون متناظراً إذا وفقط إذا تحقق
$$c_i=c_{m-i}\qquad(0 \le i \le m).$$
أي إن الرقم في الموضع \(i\) من اليمين يجب أن يساوي الرقم في الموضع المقابل من اليسار. وبما أن حاصل ضرب عددين من \(d\) خانات لا يملك أكثر من \(2d\) خانة، فإن فحص \(\operatorname{Pal}(x)\) يحتاج إلى \(O(d)\) فقط. التنفيذات تعبّر عن ذلك عبر السلاسل النصية العشرية: Python يقارن السلسلة مع معكوسها، أما C++ وJava فيقارن كل منهما الأحرف المتناظرة من الطرفين إلى الوسط.
عند تثبيت العامل الأول \(a\)، فإن القيم \(ab\) تنخفض كلما انخفض \(b\). وبين الصفوف المختلفة، فإن أكبر قيمة يمكن أن ينتجها الصف ذو العامل الأول \(a\) هي \(aH\)، وهذه الحدود العليا نفسها تنخفض عندما ينخفض \(a\).
لنفرض أن \(B\) هو أكبر حاصل ضرب متناظر عُثر عليه حتى اللحظة. المتباينة الأولى هي
$$aH \lt B.$$
إذا تحققت هذه العلاقة، فإن أي صف لاحق يملك عاملاً أول \(a' \le a\)، وبالتالي فإن أي حاصل ضرب متبقٍ يحقق \(a'b \le aH \lt B\). هذا يعني أن بقية الصفوف كلها عاجزة عن تحسين الرقم القياسي الحالي، ومن ثم يمكن إنهاء الحلقة الخارجية.
أما المتباينة الثانية فهي
$$ab \le B.$$
فعند هذه النقطة يصبح أي مرشح لاحق في الصف نفسه على الصورة \(ab'\) مع \(b' \le b\)، ومن ثم \(ab' \le ab \le B\). لذلك يمكن تجاوز ما تبقى من هذا الصف كله. هاتان الحقيقتان الأحاديتان هما السبب الرياضي الفعلي وراء السرعة العملية للخوارزمية.
عندما \(d=2\)، يكون \(L=10\) و\(H=99\). يبدأ البحث من الصف الأعلى \(a=99\)، فيفحص
$$99\cdot 99,\ 99\cdot 98,\ 99\cdot 97,\ \dots$$
ومع الاستمرار يصل إلى
$$99\cdot 91=9009,$$
وهو عدد متناظر، فتُحدَّث القيمة القياسية إلى \(B=9009\). الآن انظر إلى ما سيحدث إذا هبطت الحلقة الخارجية إلى \(a=90\): أكبر حاصل ضرب ممكن في هذا الصف هو
$$90\cdot 99=8910 \lt 9009.$$
إذن كل صف يبدأ بعامل أول لا يتجاوز \(90\) قد خرج تماماً من المنافسة، ويمكن إيقاف الحلقة الخارجية. هذه القيمة المعروفة في حالة الخانتين ليست مجرد نقطة تحقق، بل مثال صريح يوضح لماذا يعمل التقليم بصورة صحيحة.
هناك حقيقة عددية مفيدة هنا: كل عدد متناظر عشري بعدد زوجي من الخانات يقبل القسمة على 11. لنكتب
$$x=\sum_{i=0}^{2k-1} c_i 10^i,\qquad c_i=c_{2k-1-i}.$$
وبما أن \(10\equiv -1 \pmod{11}\)، فإن
$$x\equiv \sum_{i=0}^{2k-1} c_i(-1)^i \pmod{11}.$$
وعند جمع الحدين ذوي الفهرسين \(i\) و\(2k-1-i\) معاً نحصل على
$$c_i(-1)^i+c_{2k-1-i}(-1)^{2k-1-i}=c_i\bigl((-1)^i+(-1)^{2k-1-i}\bigr)=0,$$
لأن الرقمين متساويان بينما الإشارتان متعاكستان. وبجمع كل الأزواج نستنتج أن \(x\equiv 0 \pmod{11}\).
في مسألة العددين ذوي الثلاث خانات، يعني ذلك أن أي مرشح متناظر من ست خانات هو مضاعف للعدد 11، ومن ثم يمكن لحل متخصص أن يفرض كون أحد العاملين مضاعفاً لـ 11. التنفيذات الحالية تحافظ على المسح التنازلي العام الأبسط، لكن هذه الحقيقة تفسر تحسيناً كلاسيكياً مشهوراً للمسألة نفسها.
تبدأ التنفيذات بحساب الحدين \(L\) و\(H\). Python يستعمل قوى العدد 10 مباشرة. أما C++ وJava فيبنيان \(10^{d-1}\) عبر ضرب متكرر في 10، ثم يستخرجان الحد الأعلى بطرح واحد من القوة التالية للعدد 10.
بعد معرفة المجال، يمر التنفيذ على العامل الأول من \(H\) نزولاً إلى \(L\)، وداخل كل صف يمر على العامل الثاني من \(a\) نزولاً إلى \(L\). بهذه الطريقة تُزار المنطقة \(T_d\) مرة واحدة من غير تكرار الأزواج المتناظرة.
وقبل تنفيذ اختبار التناظر، يسأل الكود أولاً: هل ما زال هذا الناتج قادراً عددياً على تجاوز أفضل قيمة حالية؟ إذا كانت الإجابة لا، تُفعِّل إحدى المتباينتين السابقتين خروجاً فورياً من الحلقة المناسبة. وحدها النواتج التي ما تزال تملك فرصة حقيقية للفوز تُفحص من ناحية تماثل الأرقام.
كما أن التنفيذات الثلاث تتحقق أيضاً من المثال المعروف في حالة الخانتين، وتنتظر الحصول على \(9009\). هذه المراجعة الصغيرة كفيلة بكشف أخطاء الحدود أو اتجاهات الحلقات منذ البداية.
إذا كان \(N=H-L+1=9\cdot 10^{d-1}\)، فإن عدد النواتج المرشحة في أسوأ الأحوال، مع الاكتفاء بالمثلث \(b \le a\)، هو
$$\frac{N(N+1)}{2}=\Theta(N^2)=\Theta(10^{2d}).$$
وكل اختبار تناظر يفحص في أقصى الأحوال \(2d\) خانة عشرية، لذا يكون الحد الزمني الأدق في أسوأ حالة هو
$$O(d\,10^{2d}).$$
إذا اعتُبر \(d\) ثابتاً، كما في المسألة الأصلية حيث \(d=3\)، فالسلوك يصبح ببساطة تربيعياً بالنسبة إلى حجم مجال العوامل. عملياً يكون الزمن أقل بكثير، لأن العثور المبكر على متناظر كبير يؤدي إلى استبعاد صفوف كاملة ونهايات طويلة من الصفوف. الذاكرة الإضافية هي \(O(d)\) بسبب التمثيل العشري المؤقت، أي إنها فعلياً \(O(1)\) عندما يكون \(d\) ثابتاً.