For each base \(B\in[9,18]\), the digits \(0,1,\dots,B-1\) must be distributed exactly once across three positive integers \(a\), \(b\), and \(c\), with no leading zero. We seek all triples satisfying
$$a^2+ab+b^2=c^2,\qquad c\lt a+b.$$
The equation is symmetric in \(a\) and \(b\), and the left-hand side is strictly larger than both \(a^2\) and \(b^2\), so every valid solution may be treated in ordered form \(a\lt b\lt c\). For each base we sum all valid values of \(c\), then add those sums over bases \(9\) through \(18\).
The implementation constructs the numbers from left to right. A search state contains a current prefix for each of the three numbers and the set of digits already used. The key mathematics is what lets the search discard entire subtrees long before all digits are assigned.
Write
$$B=3k+r,\qquad r\in\{0,1,2\}.$$
The solver arranges the final digit lengths as
$$ (\ell_a,\ell_b,\ell_c)= \begin{cases} (k,k,k), & r=0,\\ (k,k,k+1), & r=1,\\ (k,k+1,k+1), & r=2. \end{cases} $$
This is the balanced way to spend all \(B\) digits, and it matches the magnitude restriction \(b\lt c\lt a+b\): \(c\) must be slightly larger than \(b\), but it cannot be dramatically larger. The search therefore starts with one leading digit in each number when \(r=0\), with one extra leading digit already placed in \(c\) when \(r=1\), and with one extra leading digit already placed in both \(b\) and \(c\) when \(r=2\).
If the current prefixes are still called \(a\), \(b\), and \(c\), then appending one new base-\(B\) digit to each gives
$$a'=aB+d_a,\qquad b'=bB+d_b,\qquad c'=cB+d_c,$$
where \(d_a\), \(d_b\), and \(d_c\) are distinct unused digits. Only the leading digits are forced to be nonzero; later appended digits may be zero.
The ordering established at the start is preserved automatically. Indeed, if \(a\lt b\), then for any digits \(d_a,d_b\in\{0,\dots,B-1\}\),
$$aB+d_a\le aB+(B-1) \lt (a+1)B\le bB\le bB+d_b.$$
So once a prefix state is generated in sorted order, every deeper state stays sorted as well. This prevents duplicate counting caused by the symmetry between \(a\) and \(b\).
Suppose there are \(r\) more digits to append to each number, and set
$$p=B^r.$$
Then the final completed values must lie in the intervals
$$A\in[ap,\ ap+p-1],\qquad B\in[bp,\ bp+p-1],\qquad C\in[cp,\ cp+p-1].$$
Because the quadratic form \(x^2+xy+y^2\) is increasing for positive \(x\) and \(y\), the smallest and largest possible left-hand sides over this state are
$$L_{\min}=(ap)^2+(bp)^2+(ap)(bp),$$
$$L_{\max}=(ap+p-1)^2+(bp+p-1)^2+(ap+p-1)(bp+p-1).$$
Likewise, the right-hand side must stay inside
$$R_{\min}=(cp)^2,\qquad R_{\max}=(cp+p-1)^2.$$
A prefix can be extended only if two necessary conditions hold:
$$cp \lt (ap+p-1)+(bp+p-1),$$
$$L_{\max}\ge R_{\min},\qquad L_{\min}\le R_{\max}.$$
If either the triangle inequality range or the quadratic-form range fails, then no completion of that prefix can possibly work, so the entire branch is pruned immediately.
Once the search has reached the point where only two digits remain for each number, there are exactly six unused digits left. At that point the implementation simply tests all \(6!=720\) ordered assignments of those digits to the three 2-digit tails and checks the full equation exactly.
When three digits remain for each number, the implementation uses a stronger filter. Write the final numbers as
$$A=aB^3+a_t,\qquad B=bB^3+b_t,\qquad C=cB^3+c_t,$$
where \(a_t\), \(b_t\), and \(c_t\) are 3-digit tails built from the remaining digits. If
$$A^2+AB+B^2=C^2,$$
then reducing modulo \(B^3\) yields the necessary congruence
$$a_t^2+a_tb_t+b_t^2\equiv c_t^2\pmod{B^3}.$$
So the solver precomputes all ordered 3-digit tails with distinct digits, groups candidate \(c_t\) values by their square residue modulo \(B^3\), and only combines tails whose digit masks are disjoint and whose residues satisfy the congruence. The full identity and \(c\lt a+b\) are then checked on the completed integers.
Take \(B=9\). Then \(9=3\cdot3\), so the final lengths are \((3,3,3)\). Suppose a search node has one-digit prefixes
$$a=1,\qquad b=2,\qquad c=5,$$
with two more digits still to append to each number. Then \(p=9^2=81\), so
$$A\in[81,161],\qquad B\in[162,242],\qquad C\in[405,485].$$
Now
$$\max A+\max B=161+242=403,$$
but
$$\min C=405.$$
Therefore every completion of this prefix would satisfy \(C\ge A+B\), which contradicts \(c\lt a+b\). The whole subtree below \((1,2,5)\) is discarded without trying any of the remaining six digits.
The C++ and Java implementations follow the same search strategy. For each base they precompute powers of the base, generate the allowed initial prefix states for the relevant length pattern, and repeatedly append one digit to each number while keeping only the states that survive the interval test above.
If the search reaches the 2-digit finishing case, the implementation checks all \(720\) tail assignments directly. If it reaches the 3-digit finishing case, it precomputes all distinct 3-digit tails, buckets them by residue modulo \(B^3\), joins only mask-compatible residue matches, and then verifies the complete identity with exact integer arithmetic rather than floating point. The C++ implementation also parallelizes the independent bases \(9\) through \(18\) and includes an independent brute-force verification for base \(9\). The Python implementation is intentionally thin: it builds or reuses the compiled solver, runs it, and returns the parsed numeric result.
A naive search would be essentially factorial in \(B\), because it would have to examine permutations of the \(B\) digits together with ways to split them among three numbers. The implemented method still has exponential worst-case behavior, but its practical cost is driven by the number of prefix states that survive pruning rather than by raw \(B!\).
For the finishing phase, the 2-digit case costs \(O(720)\) exact completions per live state. In the 3-digit case there are
$$P(B,3)=B(B-1)(B-2)$$
ordered tails to precompute, and the residue-based preprocessing is quadratic in that tail count up to the number of residue-compatible, mask-disjoint pairs and triples that survive. Memory usage is proportional to the live prefix states plus the stored tail tables. In the C++ version, distributing bases across worker threads improves wall-clock time but does not change the underlying search complexity.
Für jede Basis \(B\in[9,18]\) müssen die Ziffern \(0,1,\dots,B-1\) genau einmal auf drei positive ganze Zahlen \(a\), \(b\) und \(c\) verteilt werden, ohne führende Null. Gesucht sind alle Tripel mit
$$a^2+ab+b^2=c^2,\qquad c\lt a+b.$$
Die Gleichung ist symmetrisch in \(a\) und \(b\), und die linke Seite ist strikt größer als sowohl \(a^2\) als auch \(b^2\). Daher kann jede gültige Lösung eindeutig in geordneter Form \(a\lt b\lt c\) behandelt werden. Für jede Basis werden alle zulässigen \(c\)-Werte summiert; anschließend werden diese Summen über die Basen \(9\) bis \(18\) addiert.
Die Implementierung baut die drei Zahlen von links nach rechts auf. Ein Suchzustand enthält aktuelle Präfixe von \(a\), \(b\) und \(c\) sowie die Menge der bereits verwendeten Ziffern. Entscheidend ist, dass die Mathematik starke Schranken liefert, mit denen ganze Teilbäume der Suche verworfen werden können.
Schreibe
$$B=3k+r,\qquad r\in\{0,1,2\}.$$
Die Implementierung verwendet die Endlängen
$$ (\ell_a,\ell_b,\ell_c)= \begin{cases} (k,k,k), & r=0,\\ (k,k,k+1), & r=1,\\ (k,k+1,k+1), & r=2. \end{cases} $$
Das ist die ausgeglichene Verteilung der insgesamt \(B\) Ziffern und passt zur Größenordnung \(b\lt c\lt a+b\): \(c\) ist nur wenig größer als \(b\), darf aber nicht beliebig weit darüber liegen. Deshalb beginnt die Suche bei \(r=0\) mit je einer führenden Ziffer, bei \(r=1\) mit einer zusätzlichen führenden Ziffer in \(c\) und bei \(r=2\) mit je einer zusätzlichen führenden Ziffer in \(b\) und \(c\).
Seien die aktuellen Präfixe wieder \(a\), \(b\) und \(c\). Hängt man jeweils eine neue Basis-\(B\)-Ziffer an, so erhält man
$$a'=aB+d_a,\qquad b'=bB+d_b,\qquad c'=cB+d_c,$$
wobei \(d_a\), \(d_b\) und \(d_c\) verschieden und bislang unbenutzt sein müssen. Nur die führenden Ziffern dürfen nicht null sein; spätere angehängte Ziffern dürfen null sein.
Die anfangs festgelegte Ordnung bleibt automatisch erhalten. Gilt nämlich \(a\lt b\), dann folgt für beliebige \(d_a,d_b\in\{0,\dots,B-1\}\)
$$aB+d_a\le aB+(B-1) \lt (a+1)B\le bB\le bB+d_b.$$
Damit bleibt ein einmal sortierter Präfixzustand in jeder tieferen Ebene sortiert. So wird die Symmetrie zwischen \(a\) und \(b\) beseitigt, ohne Lösungen doppelt zu zählen.
Angenommen, es fehlen noch \(r\) Ziffern pro Zahl, und sei
$$p=B^r.$$
Dann müssen die endgültigen Zahlen in den Intervallen
$$A\in[ap,\ ap+p-1],\qquad B\in[bp,\ bp+p-1],\qquad C\in[cp,\ cp+p-1]$$
liegen.
Weil die quadratische Form \(x^2+xy+y^2\) für positive \(x\) und \(y\) monoton wächst, sind kleinst- und größtmögliche linke Seite
$$L_{\min}=(ap)^2+(bp)^2+(ap)(bp),$$
$$L_{\max}=(ap+p-1)^2+(bp+p-1)^2+(ap+p-1)(bp+p-1).$$
Die rechte Seite liegt entsprechend in
$$R_{\min}=(cp)^2,\qquad R_{\max}=(cp+p-1)^2.$$
Ein Präfix darf nur weiterverfolgt werden, wenn zwei notwendige Bedingungen erfüllt sind:
$$cp \lt (ap+p-1)+(bp+p-1),$$
$$L_{\max}\ge R_{\min},\qquad L_{\min}\le R_{\max}.$$
Verletzt ein Zustand die Dreiecksungleichung oder überlappen die Wertebereiche der quadratischen Gleichung nicht, dann kann keine Vervollständigung funktionieren. Der gesamte Ast wird sofort abgeschnitten.
Wenn pro Zahl nur noch zwei Ziffern fehlen, bleiben insgesamt genau sechs unbenutzte Ziffern übrig. Dann testet die Implementierung einfach alle \(6!=720\) geordneten Zuweisungen dieser Ziffern auf die drei 2-stelligen Endstücke und prüft die Gleichung exakt.
Wenn noch drei Ziffern pro Zahl fehlen, wird ein stärkerer Filter verwendet. Schreibe die vollständigen Zahlen als
$$A=aB^3+a_t,\qquad B=bB^3+b_t,\qquad C=cB^3+c_t,$$
wobei \(a_t\), \(b_t\) und \(c_t\) 3-stellige Endstücke aus den verbleibenden Ziffern sind. Aus
$$A^2+AB+B^2=C^2$$
folgt modulo \(B^3\) die notwendige Kongruenz
$$a_t^2+a_tb_t+b_t^2\equiv c_t^2\pmod{B^3}.$$
Daher werden alle geordneten 3-stelligen Endstücke mit paarweise verschiedenen Ziffern vorab erzeugt, mögliche \(c_t\)-Werte nach ihrem Quadratrest modulo \(B^3\) gruppiert und nur solche Dreierkombinationen betrachtet, deren Ziffernmengen disjunkt sind und deren Reste zusammenpassen. Erst danach wird die vollständige Gleichung auf den ganzen Zahlen geprüft.
Betrachte \(B=9\). Dann gilt \(9=3\cdot3\), also sind die Endlängen \((3,3,3)\). Nehme einen Suchzustand mit den einstelligen Präfixen
$$a=1,\qquad b=2,\qquad c=5,$$
wobei noch je zwei Ziffern fehlen. Dann ist \(p=9^2=81\), also
$$A\in[81,161],\qquad B\in[162,242],\qquad C\in[405,485].$$
Nun ist
$$\max A+\max B=161+242=403,$$
aber
$$\min C=405.$$
Damit würde jede Vervollständigung \(C\ge A+B\) erzwingen und somit \(c\lt a+b\) verletzen. Der gesamte Teilbaum unter \((1,2,5)\) kann verworfen werden, ohne eine der restlichen sechs Ziffern auszuprobieren.
Die C++- und Java-Implementierungen folgen derselben Suchidee. Für jede Basis werden Potenzen der Basis vorbereitet, die zulässigen Anfangszustände für das passende Längenmuster erzeugt und dann schichtweise je eine Ziffer an alle drei Zahlen angehängt. Nach jeder Erweiterung bleiben nur die Zustände erhalten, die den Intervalltest bestehen.
Im 2-stelligen Endfall werden alle \(720\) möglichen Restzuweisungen direkt geprüft. Im 3-stelligen Endfall werden zunächst alle unterschiedlichen 3-stelligen Endstücke vorab berechnet, nach Restklassen modulo \(B^3\) gruppiert und nur rest- sowie maskenkompatible Kombinationen zusammengeführt; anschließend erfolgt die exakte Ganzzahlprüfung ohne Fließkomma-Arithmetik. Die C++-Implementierung parallelisiert außerdem die voneinander unabhängigen Basen \(9\) bis \(18\) und enthält einen separaten Brute-Force-Abgleich für Basis \(9\). Die Python-Implementierung ist bewusst schlank: Sie baut oder verwendet den kompilierten Solver, führt ihn aus und gibt die gelesene Zahl zurück.
Eine naive Suche wäre im Wesentlichen faktoriell in \(B\), weil Permutationen der \(B\) Ziffern zusammen mit möglichen Aufteilungen auf drei Zahlen betrachtet werden müssten. Das implementierte Verfahren bleibt im Worst Case exponentiell, aber die praktische Laufzeit wird von den Zuständen bestimmt, die das Branch-and-Bound tatsächlich überleben, nicht von \(B!\).
Im 2-stelligen Endfall kostet jede noch lebende Teilaufgabe \(O(720)\) exakte Komplettierungen. Im 3-stelligen Endfall gibt es
$$P(B,3)=B(B-1)(B-2)$$
geordnete Endstücke; die Vorverarbeitung ist quadratisch in dieser Zahl bis auf die tatsächlich verbleibenden restklassen- und maskenverträglichen Paare und Tripel. Der Speicherbedarf ist proportional zur Zahl der lebenden Präfixzustände plus zu den gespeicherten Endstücktabellen. In C++ sinkt durch Parallelisierung über die Basen zwar die reale Laufzeit, nicht jedoch die asymptotische Suchkomplexität.
Her \(B\in[9,18]\) tabanı için \(0,1,\dots,B-1\) rakamları üç pozitif tam sayı \(a\), \(b\) ve \(c\) arasında tam bir kez dağıtılır; hiçbir sayının başında sıfır olamaz. Aranan üçlüler
$$a^2+ab+b^2=c^2,\qquad c\lt a+b$$
koşullarını sağlamalıdır. Denklem \(a\) ile \(b\) açısından simetriktir ve sol taraf hem \(a^2\)'den hem de \(b^2\)'den büyüktür; dolayısıyla her geçerli çözüm benzersiz biçimde \(a\lt b\lt c\) sıralamasında ele alınabilir. Her tabanda bulunan tüm \(c\) değerleri toplanır, sonra bu toplamlar \(9\) ile \(18\) arasındaki tüm tabanlar için yeniden toplanır.
Uygulama üç sayıyı soldan sağa inşa eder. Bir arama durumu, \(a\), \(b\) ve \(c\) için mevcut önekleri ve daha önce kullanılmış rakamlar kümesini tutar. Asıl hız kazancı, bu öneklerin hangi koşullarda kesinlikle başarısız olacağını matematiksel olarak erkenden anlayabilmemizden gelir.
Şunu yazalım:
$$B=3k+r,\qquad r\in\{0,1,2\}.$$
Çözücü son basamak uzunluklarını
$$ (\ell_a,\ell_b,\ell_c)= \begin{cases} (k,k,k), & r=0,\\ (k,k,k+1), & r=1,\\ (k,k+1,k+1), & r=2. \end{cases} $$
şeklinde düzenler. Bu, toplam \(B\) rakamı dengeli biçimde harcayan dağılımdır ve \(b\lt c\lt a+b\) büyüklük kısıtı ile uyumludur: \(c\), \(b\)'den biraz büyük olmalı ama çok fazla büyük olamaz. Bu yüzden \(r=0\) iken her sayıya birer öncü rakam yerleştirilir; \(r=1\) iken \(c\) için baştan bir fazla öncü rakam vardır; \(r=2\) iken de hem \(b\) hem \(c\) bir rakam önden başlar.
Mevcut önekler yine \(a\), \(b\) ve \(c\) olsun. Her birine yeni bir taban-\(B\) rakamı eklenince
$$a'=aB+d_a,\qquad b'=bB+d_b,\qquad c'=cB+d_c$$
elde edilir; burada \(d_a\), \(d_b\) ve \(d_c\) birbirinden farklı ve daha önce kullanılmamış olmalıdır. Yalnızca ilk rakamlar sıfır olamaz; sonraki eklemelerde sıfır kullanılabilir.
Başlangıçta kurulan sıralama otomatik olarak korunur. Gerçekten, \(a\lt b\) ise ve \(d_a,d_b\in\{0,\dots,B-1\}\) ise
$$aB+d_a\le aB+(B-1) \lt (a+1)B\le bB\le bB+d_b$$
olur. Böylece bir kez sıralı oluşturulan bir önek durumu aramanın daha derin katmanlarında da sıralı kalır. Bu, \(a\) ile \(b\) simetrisinden doğacak çift sayımı engeller.
Her sayıya eklenecek \(r\) rakam daha kaldığını varsayalım ve
$$p=B^r$$
olsun. O zaman tamamlanmış değerler şu aralıklarda olmak zorundadır:
$$A\in[ap,\ ap+p-1],\qquad B\in[bp,\ bp+p-1],\qquad C\in[cp,\ cp+p-1].$$
\(x^2+xy+y^2\) biçimi pozitif \(x\) ve \(y\) için artan olduğundan, sol tarafın bu durumda alabileceği en küçük ve en büyük değerler
$$L_{\min}=(ap)^2+(bp)^2+(ap)(bp),$$
$$L_{\max}=(ap+p-1)^2+(bp+p-1)^2+(ap+p-1)(bp+p-1)$$
olur. Sağ taraf ise
$$R_{\min}=(cp)^2,\qquad R_{\max}=(cp+p-1)^2$$
aralığında kalır.
Bir önek ancak şu iki zorunlu koşul sağlanıyorsa genişletilebilir:
$$cp \lt (ap+p-1)+(bp+p-1),$$
$$L_{\max}\ge R_{\min},\qquad L_{\min}\le R_{\max}.$$
Eşitsizlik aralığı veya karesel eşitlik aralığı başarısız olursa, o düğümden sonra gelen hiçbir tamamlama işe yaramaz. Bu nedenle bütün dal anında budanır.
Her sayı için yalnızca iki rakam kaldığında toplam altı kullanılmamış rakam vardır. Bu durumda uygulama, bu altı rakamın üç adet 2 basamaklı kuyruğa atanışının tüm \(6!=720\) sıralı olasılıklarını dener ve tam eşitliği doğrudan kontrol eder.
Her sayı için üç rakam kaldığında daha güçlü bir süzgeç kullanılır. Tam sayıları
$$A=aB^3+a_t,\qquad B=bB^3+b_t,\qquad C=cB^3+c_t$$
şeklinde yazalım; burada \(a_t\), \(b_t\) ve \(c_t\) kalan rakamlardan kurulan 3 basamaklı kuyruklardır. Eğer
$$A^2+AB+B^2=C^2$$
ise, \(B^3\) modunda indirgersek gerekli kongruans
$$a_t^2+a_tb_t+b_t^2\equiv c_t^2\pmod{B^3}$$
çıkar. Bu yüzden çözücü, farklı rakamlardan oluşan tüm sıralı 3 basamaklı kuyrukları önceden üretir; olası \(c_t\) değerlerini kare kalıntılarına göre gruplar; ardından yalnızca rakam maskeleri çakışmayan ve kalıntıları uyumlu olan kuyruk üçlülerini birleştirir. En son tam sayı eşitliği ve \(c\lt a+b\) koşulu gerçekten sağlanıyor mu diye kontrol edilir.
\(B=9\) alalım. \(9=3\cdot3\) olduğu için son uzunluklar \((3,3,3)\) olur. Şu tek basamaklı önekleri düşünelim:
$$a=1,\qquad b=2,\qquad c=5.$$
Her sayı için iki rakam daha kaldığından \(p=9^2=81\) ve
$$A\in[81,161],\qquad B\in[162,242],\qquad C\in[405,485]$$
elde edilir. Burada
$$\max A+\max B=161+242=403,$$
ama
$$\min C=405.$$
Dolayısıyla bu önekten gelen her tamamlama \(C\ge A+B\) verecektir; bu da \(c\lt a+b\) ile çelişir. Son altı rakamı hiç denemeden bütün alt ağaç elenir.
C++ ve Java uygulamaları aynı arama stratejisini izler. Her taban için taban kuvvetleri hazırlanır, uygun uzunluk desenine karşılık gelen başlangıç durumları üretilir ve sonra her turda üç sayıya birer rakam eklenir. Her genişlemeden sonra yalnızca aralık testini geçen durumlar tutulur.
Arama 2 basamaklı kapanış durumuna geldiğinde tüm \(720\) kuyruk ataması doğrudan sınanır. 3 basamaklı kapanışta ise önce farklı 3 basamaklı kuyruklar üretilir, bunlar \(B^3\) modundaki kalıntılara göre kovalanır, yalnızca maske ve kalıntı bakımından uyumlu eşleşmeler birleştirilir ve sonrasında tam sayı aritmetiğiyle kesin kontrol yapılır. C++ uygulaması ayrıca \(9\) ile \(18\) arasındaki tabanları iş parçacıklarına dağıtır ve \(B=9\) için bağımsız bir kaba kuvvet doğrulaması da içerir. Python uygulaması ise bilinçli olarak ince bir sarmalayıcıdır; derlenmiş çözücüyü üretir ya da yeniden kullanır, çalıştırır ve çıktıdaki sayıyı döndürür.
Naif yaklaşım, \(B\) rakamının permütasyonlarını ve bunların üç sayıya nasıl bölüneceğini incelemek zorunda kalacağı için özünde faktöriyel büyüklüktedir. Buradaki yöntem en kötü durumda yine üstel davranış gösterir; fakat pratik çalışma süresini belirleyen şey ham \(B!\) değil, budamadan sonra hayatta kalan önek durumlarının sayısıdır.
2 basamaklı kapanışta her canlı durum için maliyet \(O(720)\) tam kontroldür. 3 basamaklı kapanışta ise
$$P(B,3)=B(B-1)(B-2)$$
sıralı kuyruk vardır; ön işleme, gerçekten uyumlu kalan kalıntı ve maske eşleşmelerine kadar bu sayı üzerinde kuadratik davranır. Bellek kullanımı canlı önek durumları ile saklanan kuyruk tabloları ile orantılıdır. C++ tarafında tabanların paralel yürütülmesi gerçek süreyi düşürür ama asimptotik arama maliyetini değiştirmez.
Para cada base \(B\in[9,18]\), las cifras \(0,1,\dots,B-1\) deben repartirse exactamente una vez entre tres enteros positivos \(a\), \(b\) y \(c\), sin ceros iniciales. Buscamos todos los ternas que cumplen
$$a^2+ab+b^2=c^2,\qquad c\lt a+b.$$
La ecuación es simétrica en \(a\) y \(b\), y el lado izquierdo es estrictamente mayor que tanto \(a^2\) como \(b^2\), así que toda solución válida puede tratarse en orden \(a\lt b\lt c\). Para cada base se suman todos los valores válidos de \(c\), y luego esas sumas se agregan para las bases \(9\) a \(18\).
La implementación construye las tres cantidades de izquierda a derecha. Un estado de búsqueda contiene un prefijo actual para \(a\), otro para \(b\), otro para \(c\), y el conjunto de cifras ya usadas. La parte matemática es la que permite descartar subárboles enteros mucho antes de completar todos los dígitos.
Escribimos
$$B=3k+r,\qquad r\in\{0,1,2\}.$$
El solucionador organiza las longitudes finales como
$$ (\ell_a,\ell_b,\ell_c)= \begin{cases} (k,k,k), & r=0,\\ (k,k,k+1), & r=1,\\ (k,k+1,k+1), & r=2. \end{cases} $$
Esa es la manera equilibrada de gastar las \(B\) cifras totales y encaja con la restricción de magnitud \(b\lt c\lt a+b\): \(c\) debe ser un poco mayor que \(b\), pero no puede crecer muchísimo más. Por eso, cuando \(r=0\) la búsqueda empieza con una cifra líder en cada número; cuando \(r=1\), \(c\) arranca con una cifra líder extra; y cuando \(r=2\), esa cifra adicional inicial aparece en \(b\) y en \(c\).
Si los prefijos actuales siguen llamándose \(a\), \(b\) y \(c\), al añadir una nueva cifra en base \(B\) a cada uno obtenemos
$$a'=aB+d_a,\qquad b'=bB+d_b,\qquad c'=cB+d_c,$$
donde \(d_a\), \(d_b\) y \(d_c\) deben ser cifras distintas y todavía no usadas. Solo las cifras líderes están obligadas a ser no nulas; las cifras añadidas después sí pueden ser cero.
El orden inicial se conserva automáticamente. Si \(a\lt b\), entonces para cualquier \(d_a,d_b\in\{0,\dots,B-1\}\) se cumple
$$aB+d_a\le aB+(B-1) \lt (a+1)B\le bB\le bB+d_b.$$
Así, un estado que nace ordenado seguirá ordenado en todos los niveles siguientes. Eso evita contar dos veces la misma solución por la simetría entre \(a\) y \(b\).
Supongamos que faltan \(r\) cifras por añadir a cada número, y sea
$$p=B^r.$$
Entonces los valores finales completos deben estar en los intervalos
$$A\in[ap,\ ap+p-1],\qquad B\in[bp,\ bp+p-1],\qquad C\in[cp,\ cp+p-1].$$
Como la forma cuadrática \(x^2+xy+y^2\) es creciente para \(x,y>0\), el mínimo y el máximo posibles del lado izquierdo en ese estado son
$$L_{\min}=(ap)^2+(bp)^2+(ap)(bp),$$
$$L_{\max}=(ap+p-1)^2+(bp+p-1)^2+(ap+p-1)(bp+p-1).$$
El lado derecho, por su parte, queda dentro de
$$R_{\min}=(cp)^2,\qquad R_{\max}=(cp+p-1)^2.$$
Un prefijo solo se puede prolongar si se cumplen dos condiciones necesarias:
$$cp \lt (ap+p-1)+(bp+p-1),$$
$$L_{\max}\ge R_{\min},\qquad L_{\min}\le R_{\max}.$$
Si falla el rango de la desigualdad triangular o si los rangos de la ecuación cuadrática ni siquiera se cruzan, ninguna continuación de ese prefijo puede servir, así que toda la rama se poda de inmediato.
Cuando quedan solo dos cifras por número, sobran exactamente seis cifras sin usar. En ese momento la implementación prueba directamente las \(6!=720\) asignaciones ordenadas de esas cifras a las tres colas de 2 dígitos y verifica la igualdad completa.
Cuando quedan tres cifras por número, se usa un filtro más fino. Escribimos los valores finales como
$$A=aB^3+a_t,\qquad B=bB^3+b_t,\qquad C=cB^3+c_t,$$
donde \(a_t\), \(b_t\) y \(c_t\) son colas de 3 dígitos formadas con las cifras restantes. Si
$$A^2+AB+B^2=C^2,$$
entonces al reducir módulo \(B^3\) obtenemos la congruencia necesaria
$$a_t^2+a_tb_t+b_t^2\equiv c_t^2\pmod{B^3}.$$
Por eso el solucionador precalcula todas las colas ordenadas de 3 dígitos con cifras distintas, agrupa los posibles \(c_t\) por el residuo cuadrático módulo \(B^3\), y solo combina colas cuyas máscaras de cifras sean disjuntas y cuyos residuos encajen. Después se comprueba la identidad completa sobre enteros exactos.
Tomemos \(B=9\). Como \(9=3\cdot3\), las longitudes finales son \((3,3,3)\). Consideremos un nodo con prefijos de una cifra
$$a=1,\qquad b=2,\qquad c=5,$$
y todavía dos cifras pendientes por añadir a cada número. Entonces \(p=9^2=81\), y por tanto
$$A\in[81,161],\qquad B\in[162,242],\qquad C\in[405,485].$$
Ahora bien,
$$\max A+\max B=161+242=403,$$
mientras que
$$\min C=405.$$
Así, toda continuación satisfaría \(C\ge A+B\), lo que contradice \(c\lt a+b\). Toda la rama que cuelga de \((1,2,5)\) se elimina sin probar ninguna de las seis cifras restantes.
Las implementaciones en C++ y Java siguen la misma estrategia de búsqueda. Para cada base precalculan las potencias de la base, generan los estados iniciales permitidos para el patrón de longitudes correspondiente, y luego añaden una cifra a cada uno de los tres números en capas sucesivas. Después de cada extensión solo se conservan los estados que superan la prueba de intervalos.
Si la búsqueda llega al caso final de 2 dígitos, la implementación revisa directamente las \(720\) asignaciones posibles. Si llega al caso de 3 dígitos, primero precalcula todas las colas distintas de longitud 3, las agrupa por residuos módulo \(B^3\), une solo las combinaciones compatibles por máscara y por residuo, y al final verifica la identidad exacta con aritmética entera, sin usar coma flotante. La versión en C++ además paraleliza las bases independientes \(9\) a \(18\) e incluye una verificación bruta separada para la base \(9\). La implementación en Python es deliberadamente delgada: construye o reutiliza el solucionador compilado, lo ejecuta y devuelve el valor numérico extraído de su salida.
Una búsqueda ingenua sería esencialmente factorial en \(B\), porque tendría que revisar permutaciones de las \(B\) cifras junto con las posibles particiones entre tres números. El método implementado sigue teniendo comportamiento exponencial en el peor caso, pero el coste práctico depende del número de estados prefijo que sobreviven a la poda, no del \(B!\) bruto.
En el caso final de 2 dígitos, cada estado vivo cuesta \(O(720)\) completaciones exactas. En el caso de 3 dígitos hay
$$P(B,3)=B(B-1)(B-2)$$
colas ordenadas que precalcular; el preprocesamiento es cuadrático en esa cantidad hasta el número real de pares y ternas compatibles por residuo y por máscara. La memoria usada es proporcional a los estados prefijo vivos más las tablas de colas almacenadas. En C++, repartir las bases entre hilos reduce el tiempo de reloj, pero no cambia la complejidad asintótica de la búsqueda.
对每个进制 \(B\in[9,18]\)，数字 \(0,1,\dots,B-1\) 必须恰好一次分配到三个正整数 \(a\)、\(b\)、\(c\) 中，并且任何一个数都不能有前导零。我们要寻找满足
$$a^2+ab+b^2=c^2,\qquad c\lt a+b$$
的全部三元组。这个方程对 \(a\) 和 \(b\) 是对称的，而且左边严格大于 \(a^2\) 与 \(b^2\)，所以每个有效解都可以唯一地按 \(a\lt b\lt c\) 的顺序来处理。对每个进制，把所有合法的 \(c\) 相加；最后再把进制 \(9\) 到 \(18\) 的这些和累加起来。
实现方式是从高位到低位构造这三个数。一个搜索状态包含 \(a\)、\(b\)、\(c\) 的当前前缀，以及已经使用过的数字集合。真正让搜索可行的，不是暴力本身，而是下面这些可以提前剪掉整个子树的数学条件。
写成
$$B=3k+r,\qquad r\in\{0,1,2\}.$$
求解器把最终位数安排为
$$ (\ell_a,\ell_b,\ell_c)= \begin{cases} (k,k,k), & r=0,\\ (k,k,k+1), & r=1,\\ (k,k+1,k+1), & r=2. \end{cases} $$
这是把总共 \(B\) 个数字尽量均衡地分到三者中的方式，也符合 \(b\lt c\lt a+b\) 带来的量级要求：\(c\) 必须比 \(b\) 稍大，但又不可能远远大于 \(b\)。因此，当 \(r=0\) 时三者都先放入一个首位数字；当 \(r=1\) 时，\(c\) 先比另外两个多放一位；当 \(r=2\) 时，\(b\) 与 \(c\) 都先多放一位。
若当前前缀仍记作 \(a\)、\(b\)、\(c\)，则给每个前缀各追加一位后得到
$$a'=aB+d_a,\qquad b'=bB+d_b,\qquad c'=cB+d_c,$$
其中 \(d_a\)、\(d_b\)、\(d_c\) 必须彼此不同，且此前没有使用过。只有最高位数字禁止为零；后续追加的数字可以为零。
初始时建立的大小顺序会自动保持。如果 \(a\lt b\)，那么对任意 \(d_a,d_b\in\{0,\dots,B-1\}\)，都有
$$aB+d_a\le aB+(B-1) \lt (a+1)B\le bB\le bB+d_b.$$
这意味着一旦某个状态在生成时已经满足 \(a\lt b\lt c\)，之后无论再往后追加多少层数字，这个顺序都不会被破坏。这样就自然地消除了 \(a\) 与 \(b\) 的对称重复计数。
设每个数还剩 \(r\) 位没有补上，并记
$$p=B^r.$$
那么最终完成后的数一定落在下面的区间里：
$$A\in[ap,\ ap+p-1],\qquad B\in[bp,\ bp+p-1],\qquad C\in[cp,\ cp+p-1].$$
由于二次型 \(x^2+xy+y^2\) 对正整数 \(x,y\) 单调递增，所以在这个状态下，左边可能取得的最小值和最大值分别是
$$L_{\min}=(ap)^2+(bp)^2+(ap)(bp),$$
$$L_{\max}=(ap+p-1)^2+(bp+p-1)^2+(ap+p-1)(bp+p-1).$$
右边则必须落在
$$R_{\min}=(cp)^2,\qquad R_{\max}=(cp+p-1)^2$$
之间。
因此，一个前缀只有在以下两个必要条件都成立时才值得继续搜索：
$$cp \lt (ap+p-1)+(bp+p-1),$$
$$L_{\max}\ge R_{\min},\qquad L_{\min}\le R_{\max}.$$
如果三角不等式的区间已经不可能满足，或者二次方程左右两边的区间根本没有交集，那么这个前缀的任何补全都不可能成功，整棵子树可以立即剪掉。
当每个数只剩两位时，总共正好还有六个未使用数字。这时实现直接枚举这六个数字分配到三个 2 位尾部的全部 \(6!=720\) 种有序方式，并对完整等式做精确检查。
当每个数还剩三位时，会使用更强的预筛。把最终值写成
$$A=aB^3+a_t,\qquad B=bB^3+b_t,\qquad C=cB^3+c_t,$$
其中 \(a_t\)、\(b_t\)、\(c_t\) 是由剩余数字组成的 3 位尾部。若
$$A^2+AB+B^2=C^2,$$
则对 \(B^3\) 取模后必然得到
$$a_t^2+a_tb_t+b_t^2\equiv c_t^2\pmod{B^3}.$$
所以，求解器会先预计算所有由互异数字组成的有序 3 位尾部，再按平方剩余把候选 \(c_t\) 分桶，只组合那些数字掩码互不重叠、并且剩余类满足这个同余关系的尾部三元组。最后再在完整整数上验证精确等式和 \(c\lt a+b\)。
取 \(B=9\)。因为 \(9=3\cdot3\)，所以最终位数是 \((3,3,3)\)。设某个搜索节点的一位前缀为
$$a=1,\qquad b=2,\qquad c=5,$$
并且每个数都还要再补两位。这时 \(p=9^2=81\)，于是
$$A\in[81,161],\qquad B\in[162,242],\qquad C\in[405,485].$$
现在有
$$\max A+\max B=161+242=403,$$
而
$$\min C=405.$$
也就是说，无论剩下六个数字怎么填，最终都必然满足 \(C\ge A+B\)，这与 \(c\lt a+b\) 矛盾。所以以 \((1,2,5)\) 为根的整棵子树都可以不展开，直接丢弃。
C++ 与 Java 实现采用同一套搜索框架。对每个进制，它们先准备该进制的幂，生成与相应位数模式匹配的初始状态，然后一层一层地给三个数同时追加一位。每次扩展后，只保留通过区间可行性测试的状态。
如果搜索到 2 位收尾阶段，实现就直接检查全部 \(720\) 种尾部排列；如果搜索到 3 位收尾阶段，就先预计算所有不同的 3 位尾部，按 \(B^3\) 模下的剩余类分组，只拼接掩码和剩余类都兼容的组合，最后用精确整数运算验证完整恒等式，不依赖浮点数。C++ 实现还会把互相独立的进制 \(9\) 到 \(18\) 分发到多个工作线程，并额外用独立的暴力枚举对 \(9\) 进制做交叉校验。Python 实现则刻意保持精简：它负责构建或复用编译后的求解器、运行它，并返回解析出来的数值答案。
朴素做法本质上接近 \(B!\) 级别，因为它要检查 \(B\) 个数字的排列以及它们在三个数之间的切分方式。这里的算法在最坏情况下仍然是指数级，但实际成本主要由剪枝后仍然存活的前缀状态数决定，而不是原始的 \(B!\)。
在 2 位收尾时，每个存活状态的成本是 \(O(720)\) 次精确补全检查。在 3 位收尾时，需要先生成
$$P(B,3)=B(B-1)(B-2)$$
个有序尾部；随后预处理在这个尾部数量上呈二次增长，直到真正能够通过剩余类与数字掩码过滤的配对和三元组为止。内存用量与存活前缀状态以及尾部表的规模成正比。C++ 中按进制并行只会降低实际运行时间，不会改变搜索本身的渐近复杂度。
Для каждого основания \(B\in[9,18]\) цифры \(0,1,\dots,B-1\) нужно ровно один раз распределить между тремя положительными целыми числами \(a\), \(b\) и \(c\), не допуская ведущих нулей. Требуются все тройки, удовлетворяющие
$$a^2+ab+b^2=c^2,\qquad c\lt a+b.$$
Уравнение симметрично по \(a\) и \(b\), а левая часть строго больше и \(a^2\), и \(b^2\), поэтому каждое допустимое решение можно однозначно рассматривать в упорядоченном виде \(a\lt b\lt c\). Для каждого основания суммируются все подходящие значения \(c\), а затем эти суммы складываются по всем основаниям от \(9\) до \(18\).
Реализация строит три числа слева направо. Состояние поиска хранит текущий префикс каждого из чисел и множество уже использованных цифр. Вся эффективность возникает из того, что математические ограничения позволяют заранее отбрасывать целые поддеревья поиска.
Запишем
$$B=3k+r,\qquad r\in\{0,1,2\}.$$
Тогда решатель организует конечные длины так:
$$ (\ell_a,\ell_b,\ell_c)= \begin{cases} (k,k,k), & r=0,\\ (k,k,k+1), & r=1,\\ (k,k+1,k+1), & r=2. \end{cases} $$
Это сбалансированный способ израсходовать все \(B\) цифр, и он согласуется с оценкой \(b\lt c\lt a+b\): число \(c\) должно быть немного больше \(b\), но не может быть на порядки больше него. Поэтому при \(r=0\) поиск стартует с одной ведущей цифры у каждого числа; при \(r=1\) число \(c\) получает одну дополнительную ведущую цифру; при \(r=2\) такую дополнительную цифру с самого начала получают и \(b\), и \(c\).
Пусть текущие префиксы снова обозначены через \(a\), \(b\) и \(c\). После дописывания одной новой цифры в системе счисления по основанию \(B\) получаем
$$a'=aB+d_a,\qquad b'=bB+d_b,\qquad c'=cB+d_c,$$
где \(d_a\), \(d_b\) и \(d_c\) должны быть попарно различны и ранее не использованы. Только самые первые цифры обязаны быть ненулевыми; последующие дописываемые цифры могут быть нулем.
Начальный порядок сохраняется автоматически. Если \(a\lt b\), то для любых \(d_a,d_b\in\{0,\dots,B-1\}\)
$$aB+d_a\le aB+(B-1) \lt (a+1)B\le bB\le bB+d_b.$$
Значит, однажды упорядоченный префикс всегда останется упорядоченным и глубже по дереву поиска. Тем самым симметрия между \(a\) и \(b\) устраняется без двойного подсчета решений.
Предположим, что каждому числу осталось дописать еще \(r\) цифр, и обозначим
$$p=B^r.$$
Тогда окончательные значения обязательно лежат в интервалах
$$A\in[ap,\ ap+p-1],\qquad B\in[bp,\ bp+p-1],\qquad C\in[cp,\ cp+p-1].$$
Поскольку квадратичная форма \(x^2+xy+y^2\) монотонно возрастает при положительных \(x\) и \(y\), минимальное и максимальное возможные значения левой части равны
$$L_{\min}=(ap)^2+(bp)^2+(ap)(bp),$$
$$L_{\max}=(ap+p-1)^2+(bp+p-1)^2+(ap+p-1)(bp+p-1).$$
Правая часть, соответственно, обязана лежать в промежутке
$$R_{\min}=(cp)^2,\qquad R_{\max}=(cp+p-1)^2.$$
Префикс имеет смысл расширять только тогда, когда одновременно выполнены две необходимые проверки:
$$cp \lt (ap+p-1)+(bp+p-1),$$
$$L_{\max}\ge R_{\min},\qquad L_{\min}\le R_{\max}.$$
Если диапазон треугольного неравенства уже невозможен или диапазоны квадратичного равенства не пересекаются, никакое продолжение этого префикса не сможет дать ответ. Вся ветвь немедленно отсекается.
Когда каждому числу не хватает только двух цифр, остается ровно шесть неиспользованных цифр. Тогда реализация просто перебирает все \(6!=720\) упорядоченных способов раздать их трем двумерным хвостам и проверяет полное равенство точно.
Когда остаются три цифры на число, используется более сильный фильтр. Представим окончательные числа как
$$A=aB^3+a_t,\qquad B=bB^3+b_t,\qquad C=cB^3+c_t,$$
где \(a_t\), \(b_t\) и \(c_t\) — трехзначные хвосты, собранные из оставшихся цифр. Если
$$A^2+AB+B^2=C^2,$$
то после взятия по модулю \(B^3\) обязательно получаем
$$a_t^2+a_tb_t+b_t^2\equiv c_t^2\pmod{B^3}.$$
Поэтому решатель заранее строит все упорядоченные трехзначные хвосты с попарно различными цифрами, группирует возможные \(c_t\) по квадратному остатку по модулю \(B^3\) и соединяет только те тройки хвостов, чьи маски цифр не пересекаются и чьи остатки удовлетворяют этой конгруэнции. После этого уже на полных числах выполняется точная проверка равенства и условия \(c\lt a+b\).
Возьмем \(B=9\). Тогда \(9=3\cdot3\), значит конечные длины равны \((3,3,3)\). Рассмотрим узел поиска с однозначными префиксами
$$a=1,\qquad b=2,\qquad c=5,$$
когда каждому числу еще не хватает двух цифр. Тогда \(p=9^2=81\), и потому
$$A\in[81,161],\qquad B\in[162,242],\qquad C\in[405,485].$$
Теперь
$$\max A+\max B=161+242=403,$$
а
$$\min C=405.$$
Следовательно, любое продолжение этого префикса обязательно давало бы \(C\ge A+B\), что противоречит условию \(c\lt a+b\). Поддерево под \((1,2,5)\) полностью отбрасывается без перебора оставшихся шести цифр.
Реализации на C++ и Java используют одну и ту же структуру поиска. Для каждого основания заранее вычисляются степени основания, затем строятся начальные состояния для нужного шаблона длин, после чего на каждом шаге к каждому из трех чисел дописывается по одной цифре. После каждого расширения сохраняются только те состояния, которые проходят интервальную проверку.
Если поиск дошел до случая с двумя оставшимися цифрами, реализация напрямую проверяет все \(720\) возможных хвостовых назначений. Если дошло до случая с тремя цифрами, сначала предвычисляются все различные трехзначные хвосты, затем они группируются по остаткам по модулю \(B^3\), объединяются только совместимые по маске и остатку комбинации, и в конце полное равенство проверяется точной целочисленной арифметикой без плавающей точки. Версия на C++ также распараллеливает независимые основания от \(9\) до \(18\) и содержит отдельную грубую проверку для базы \(9\). Python-реализация намеренно тонкая: она строит или повторно использует скомпилированный решатель, запускает его и возвращает распознанный числовой ответ.
Наивный подход был бы по существу факториальным по \(B\), потому что пришлось бы перебирать перестановки всех \(B\) цифр и способы разрезать их на три числа. Реализованный метод в худшем случае все еще экспоненциален, но на практике стоимость определяется числом префиксных состояний, переживших отсечение, а не голым \(B!\).
В случае двухзначного завершения каждая живая вершина дает \(O(720)\) точных проверок. В случае трехзначного завершения сначала строятся
$$P(B,3)=B(B-1)(B-2)$$
упорядоченных хвоста; предобработка квадратична по этому количеству вплоть до реального числа совместимых по остатку и маске пар и троек. Память пропорциональна числу живых префиксных состояний и размеру таблиц хвостов. В C++ распараллеливание по основаниям уменьшает реальное время, но не меняет асимптотическую сложность поиска.
لكل أساس \(B\in[9,18]\)، يجب توزيع الأرقام \(0,1,\dots,B-1\) مرة واحدة بالضبط على ثلاثة أعداد صحيحة موجبة \(a\) و\(b\) و\(c\)، من دون أصفار بادئة. نبحث عن جميع الثلاثيات التي تحقق
$$a^2+ab+b^2=c^2,\qquad c\lt a+b.$$
المعادلة متناظرة في \(a\) و\(b\)، كما أن الطرف الأيسر أكبر قطعًا من كل من \(a^2\) و\(b^2\)، لذا يمكن التعامل مع كل حل صحيح على الصورة المرتبة \(a\lt b\lt c\). في كل أساس نجمع كل القيم الصحيحة لـ \(c\)، ثم نجمع هذه المجاميع عبر الأسس من \(9\) إلى \(18\).
يبني التنفيذ الأعداد الثلاثة من اليسار إلى اليمين. تحتوي حالة البحث على بادئة حالية لكل من \(a\) و\(b\) و\(c\)، وعلى مجموعة الأرقام التي استُخدمت بالفعل. السرعة العملية تأتي من الشروط الرياضية التي تسمح بحذف فروع كاملة من شجرة البحث قبل إكمال جميع الأرقام.
لنكتب
$$B=3k+r,\qquad r\in\{0,1,2\}.$$
يرتب الحل أطوال الأعداد النهائية على النحو
$$ (\ell_a,\ell_b,\ell_c)= \begin{cases} (k,k,k), & r=0,\\ (k,k,k+1), & r=1,\\ (k,k+1,k+1), & r=2. \end{cases} $$
وهذا هو التقسيم المتوازن لاستهلاك جميع الأرقام \(B\)، كما أنه ينسجم مع القيد الحجمي \(b\lt c\lt a+b\): فالعدد \(c\) يجب أن يكون أكبر قليلًا من \(b\)، لكنه لا يستطيع أن يكون أكبر منه بكثير. لذلك يبدأ البحث، عندما \(r=0\)، برقم قائد واحد لكل عدد؛ وعندما \(r=1\)، يكون لدى \(c\) رقم قائد إضافي منذ البداية؛ وعندما \(r=2\)، يحصل كل من \(b\) و\(c\) على هذه الزيادة الابتدائية.
إذا كانت البوادئ الحالية ما تزال تسمى \(a\) و\(b\) و\(c\)، فإن إضافة رقم واحد جديد في الأساس \(B\) إلى كل منها تعطي
$$a'=aB+d_a,\qquad b'=bB+d_b,\qquad c'=cB+d_c,$$
حيث يجب أن تكون \(d_a\) و\(d_b\) و\(d_c\) مختلفة فيما بينها وغير مستخدمة سابقًا. الأرقام القائدة وحدها ممنوعة من أن تكون صفرًا؛ أما الأرقام اللاحقة المضافة فيمكن أن تكون صفرًا.
الترتيب الأولي يبقى محفوظًا تلقائيًا. فإذا كان \(a\lt b\)، فإننا نحصل لأي \(d_a,d_b\in\{0,\dots,B-1\}\) على
$$aB+d_a\le aB+(B-1) \lt (a+1)B\le bB\le bB+d_b.$$
إذن الحالة التي تبدأ مرتبة ستظل مرتبة في جميع الأعماق التالية من البحث. وبهذا نتخلص من التماثل بين \(a\) و\(b\) من غير أن نعدّ الحلول أكثر من مرة.
لنفترض أن كل عدد ما يزال يحتاج إلى \(r\) أرقام إضافية، ولنضع
$$p=B^r.$$
عندئذٍ يجب أن تقع القيم النهائية المكتملة داخل المجالات
$$A\in[ap,\ ap+p-1],\qquad B\in[bp,\ bp+p-1],\qquad C\in[cp,\ cp+p-1].$$
وبما أن الصورة التربيعية \(x^2+xy+y^2\) تزداد مع \(x\) و\(y\) الموجبين، فإن أصغر وأكبر قيمة ممكنة للطرف الأيسر في هذه الحالة هما
$$L_{\min}=(ap)^2+(bp)^2+(ap)(bp),$$
$$L_{\max}=(ap+p-1)^2+(bp+p-1)^2+(ap+p-1)(bp+p-1).$$
أما الطرف الأيمن فيبقى ضمن
$$R_{\min}=(cp)^2,\qquad R_{\max}=(cp+p-1)^2.$$
ولا يجوز متابعة البادئة إلا إذا تحقق شرطان لازمان معًا:
$$cp \lt (ap+p-1)+(bp+p-1),$$
$$L_{\max}\ge R_{\min},\qquad L_{\min}\le R_{\max}.$$
إذا فشل مجال متباينة المثلث أو لم يعد هناك أي تداخل بين مجالي طرفي المعادلة التربيعية، فليس هناك أي إكمال ممكن لهذه البادئة. عندها يُقصّ الفرع كله فورًا.
عندما لا يبقى لكل عدد سوى رقمين، يكون لدينا ستة أرقام غير مستخدمة فقط. حينها يجرّب التنفيذ مباشرة جميع الترتيبات الممكنة وعددها \(6!=720\) لإسناد هذه الأرقام إلى الذيول الثلاثية ذات الطول 2، ثم يتحقق من المساواة الكاملة بدقة.
أما عندما يبقى لكل عدد ثلاثة أرقام، فيُستخدم ترشيح أقوى. نكتب القيم النهائية على الصورة
$$A=aB^3+a_t,\qquad B=bB^3+b_t,\qquad C=cB^3+c_t,$$
حيث تمثل \(a_t\) و\(b_t\) و\(c_t\) ذيولًا من ثلاث خانات مكوّنة من الأرقام المتبقية. إذا تحقق
$$A^2+AB+B^2=C^2,$$
فإن الاختزال بترديد \(B^3\) يعطي الشرط الضروري
$$a_t^2+a_tb_t+b_t^2\equiv c_t^2\pmod{B^3}.$$
لذلك يسبق الحلّ بحساب جميع الذيول المرتبة ذات الثلاث خانات والمكوّنة من أرقام متمايزة، ثم يجمع المرشحين لـ \(c_t\) بحسب بقايا مربعاتهم modulo \(B^3\)، ولا يركّب إلا الثلاثيات التي لا تتقاطع أقنعتها الرقمية والتي تحقق هذا التطابق في البواقي. بعد ذلك فقط يُفحَص التساوي الكامل والشرط \(c\lt a+b\) على الأعداد النهائية نفسها.
خذ \(B=9\). بما أن \(9=3\cdot3\)، فإن الأطوال النهائية هي \((3,3,3)\). لنفترض وجود عقدة بحث ببدايات أحادية الخانة
$$a=1,\qquad b=2,\qquad c=5,$$
وما يزال لكل عدد رقمـان إضافيان. عندئذٍ يكون \(p=9^2=81\)، ومن ثم
$$A\in[81,161],\qquad B\in[162,242],\qquad C\in[405,485].$$
الآن
$$\max A+\max B=161+242=403,$$
بينما
$$\min C=405.$$
إذًا أي إكمال ممكن سيجبرنا على \(C\ge A+B\)، وهذا يناقض \(c\lt a+b\). لذلك يُحذف كامل الفرع الواقع تحت \((1,2,5)\) من دون تجربة أي من الأرقام الستة المتبقية.
يتبع التنفيذان في C++ وJava الاستراتيجية نفسها. فلكل أساس تُحضَّر قوى ذلك الأساس، وتُولَّد الحالات الابتدائية المناسبة لنمط الأطوال المطلوب، ثم تُضاف خانة واحدة إلى كل من الأعداد الثلاثة طبقة بعد طبقة. وبعد كل توسيع لا تُحفَظ إلا الحالات التي تجتاز اختبار المجالات السابق.
إذا وصل البحث إلى حالة الإنهاء ذات الرقمين، يفحص التنفيذ مباشرة جميع التخصيصات الممكنة وعددها \(720\). وإذا وصل إلى حالة الثلاث خانات، فإنه يسبق بحساب جميع الذيول المختلفة ذات الثلاث خانات، ثم يجمّعها بحسب البواقي modulo \(B^3\)، ولا يجمع إلا التوافقات المنسجمة من حيث القناع والباقي، ثم يتحقق من الهوية الكاملة باستخدام حسابات صحيحة دقيقة من دون اللجوء إلى الفاصلة العائمة. كما أن تنفيذ C++ يوزّع الأسس المستقلة من \(9\) إلى \(18\) على خيوط عمل متعددة، ويتضمن أيضًا تحققًا مستقلًا بالقوة الغاشمة للأساس \(9\). أما تنفيذ Python فهو غلاف خفيف عمدًا: يبني أو يعيد استخدام المحلّل المترجم، يشغّله، ثم يعيد الجواب العددي المستخرج من خرجه.
البحث الساذج سيكون في جوهره من رتبة عاملية في \(B\)، لأنه يحتاج إلى فحص تبديلات الأرقام \(B\) مع طرق تقسيمها بين ثلاثة أعداد. الطريقة المنفذة هنا ما تزال أسية في أسوأ الأحوال، لكن التكلفة العملية يحددها عدد حالات البادئة التي تنجو من القصّ، لا القيمة الخام \(B!\).
في حالة الإنهاء ذات الرقمين، تكلف كل حالة حية \(O(720)\) من عمليات الإكمال الدقيقة. وفي حالة الإنهاء ذات الثلاث خانات، يوجد
$$P(B,3)=B(B-1)(B-2)$$
ذيلًا مرتبًا يجب توليدها مسبقًا؛ ثم يكون التمهيد تربيعيًا في هذا العدد حتى الوصول إلى العدد الفعلي من الأزواج والثلاثيات المتوافقة من حيث الباقي والقناع. ويكون استهلاك الذاكرة متناسبًا مع الحالات الحية ومع جداول الذيول المخزنة. أما توزيع الأسس على خيوط في C++ فيحسن الزمن الفعلي فقط، ولا يغير رتبة التعقيد الأساسية للبحث.