The repository solutions work with the triangle family whose side lengths are
$$\sqrt{b^2+1},\qquad \sqrt{c^2+1},\qquad \sqrt{b^2+c^2},$$
where \(b\) and \(c\) are positive integers and the brute-force validator counts only unordered pairs \(b \le c\). If \(A\) denotes the area, the goal is
$$S(L)=\sum A,$$
summed over all triangles in this family whose area is an integer and satisfies \(A \le L\).
Let
$$x=\sqrt{b^2+1},\qquad y=\sqrt{c^2+1},\qquad z=\sqrt{b^2+c^2}.$$
Applying Heron's identity in the form
$$16A^2=2x^2y^2+2y^2z^2+2z^2x^2-x^4-y^4-z^4$$
and substituting \(x^2=b^2+1\), \(y^2=c^2+1\), \(z^2=b^2+c^2\) gives
$$16A^2=4\left(b^2c^2+b^2+c^2\right).$$
Therefore
$$A=\frac{1}{2}\sqrt{b^2c^2+b^2+c^2}.$$
This is exactly the relation used by the C++ brute-force checkpoint. Writing
$$m^2=b^2c^2+b^2+c^2,$$
we have \(A=m/2\). So the area is integral precisely when \(m\) is an even integer square root of that expression.
Because \(A\) is an integer, \(m=2A\) is even, so \(m^2 \equiv 0 \pmod 4\). But a square is only \(0\) or \(1\) modulo \(4\). If either \(b\) or \(c\) were odd, then
$$b^2c^2+b^2+c^2 \equiv 1 \text{ or } 3 \pmod 4,$$
which is impossible. Hence every valid solution has even \(b\) and even \(c\). We may therefore write
$$b=2p,\qquad c=2q,$$
with integers \(p,q \ge 1\). Substituting into the area formula gives
$$A^2=4p^2q^2+p^2+q^2.$$
This is the equation actually encoded by the fast state generator.
For a fixed seed \(p\), move the \(q\)-term to the left:
$$A^2-(4p^2+1)q^2=p^2.$$
If we define
$$D_p=4p^2+1,$$
then every admissible state satisfies the Pell-type norm equation
$$A^2-D_p q^2=p^2.$$
The trivial solution is \(q=0\), \(A=p\). The fast solver starts from this trivial point and moves to the next positive one on the same Pell branch.
The fundamental unit for \(x^2-D_p y^2=1\) used by the implementation is
$$u_p=(8p^2+1)+4p\sqrt{D_p},$$
because
$$\left(8p^2+1\right)^2-D_p(4p)^2=1.$$
Multiplying one solution \(A+q\sqrt{D_p}\) by \(u_p\) produces the next solution on the same branch:
$$A'+q'\sqrt{D_p}=u_p\left(A+q\sqrt{D_p}\right).$$
Comparing coefficients yields
$$q'=(8p^2+1)q+4pA,$$
$$A'=4p(4p^2+1)q+(8p^2+1)A.$$
This is exactly the transition implemented in all three solution files with
$$a=8p^2+1,\qquad b=4p,\qquad c=4p(4p^2+1),$$
$$q'=a q+b A,\qquad A'=c q+a A.$$
Starting from the trivial state \((p,0,p)\), one recurrence step gives
$$q_1=4p^2,\qquad A_1=(8p^2+1)p=8p^3+p.$$
So the first actual triangle for seed \(p\) is
$$b=2p,\qquad c=2q_1=8p^2,\qquad A=8p^3+p.$$
This explains the helper function seed_first_area(p) and the binary search in max_seed(limit): once \(8p^3+p>L\), that seed cannot contribute any valid area \(\le L\).
For \(p=1\), the first solution is
$$q_1=4,\qquad A_1=9,$$
so \((b,c)=(2,8)\). The checkpoint in the C++ file confirms
$$2^2\cdot 8^2+2^2+8^2=324=18^2,\qquad A=18/2=9.$$
The equation
$$A^2=4p^2q^2+p^2+q^2$$
is symmetric in \(p\) and \(q\), and it only involves their squares. Therefore whenever the recurrence produces \((p,q',A')\), the states
$$(q',p,A')\qquad \text{and} \qquad (q',-p,A')$$
represent valid orientations of the same quadratic surface. The implementation therefore pushes three states:
$$(p,q',A'),\qquad (q',p,A'),\qquad (q',-p,A').$$
The first one continues the same Pell branch with fixed \(p\). The two swapped states let the new value \(q'\) become the fixed coordinate of later Pell branches. The negative-sign branch is essential: for example, from area \(9\) the state \((4,-1,9)\) leads to the next solution \((4,15,121)\), which corresponds to \((b,c)=(8,30)\).
The repository does not store a separate formal proof of uniqueness for this tree, but it does verify the construction exhaustively against brute force for a small limit and against the statement checkpoint \(S(10^6)=18018206\).
The C++ file contains both a slow validator and the optimized recurrence solver. The validator iterates over unordered pairs \(b \le c\), uses
$$m^2=b^2c^2+b^2+c^2$$
and checks whether \(m\) is an even square root. The bounds
$$bc \le 2A \le 2L$$
justify the scan limit \(b \le 2L\) and the inner bound \(c \lesssim 2L/b\).
The fast solver works in half-coordinates \((p,q)\). Function sum_for_seed performs an explicit depth-first traversal with a stack of states \((p,q,A)\). Function next_state applies the Pell step above, discards branches with \(A' \le 0\) or \(A' > L\), and creates the three follow-up states. The C++ version uses 128-bit intermediates and distributes seeds across threads with an atomic counter; Python relies on arbitrary-precision integers, and Java uses BigInteger for the recurrence arithmetic.
The brute-force validator is roughly
$$\sum_{b \le 2L} O\!\left(\frac{L}{b}\right)=O(L\log L),$$
which is already too slow for the real limit. The optimized solver is output-sensitive: if \(T(L)\) is the number of generated states whose next area stays within the bound, then the runtime is \(O(T(L))\) arithmetic transitions. Memory is proportional to the active DFS stack size per worker, not to a full \((b,c)\) grid. The important practical improvement is that the search follows only Pell-generated solutions instead of testing almost all integer pairs.
Die Repository-Lösungen arbeiten mit Dreiecken der Seitenlängen
$$\sqrt{b^2+1},\qquad \sqrt{c^2+1},\qquad \sqrt{b^2+c^2},$$
wobei \(b\) und \(c\) positive ganze Zahlen sind und die Brute-Force-Prüfung nur ungeordnete Paare \(b \le c\) betrachtet. Ist \(A\) die Fläche, dann ist gesucht
$$S(L)=\sum A,$$
wobei über alle Dreiecke dieser Form summiert wird, deren Fläche ganzzahlig ist und \(A \le L\) erfüllt.
Setze
$$x=\sqrt{b^2+1},\qquad y=\sqrt{c^2+1},\qquad z=\sqrt{b^2+c^2}.$$
Mit der Heron-Identität
$$16A^2=2x^2y^2+2y^2z^2+2z^2x^2-x^4-y^4-z^4$$
und den Einsetzungen \(x^2=b^2+1\), \(y^2=c^2+1\), \(z^2=b^2+c^2\) erhält man
$$16A^2=4\left(b^2c^2+b^2+c^2\right).$$
Also gilt
$$A=\frac{1}{2}\sqrt{b^2c^2+b^2+c^2}.$$
Genau diese Beziehung verwendet die C++-Brute-Force-Prüfung. Schreibt man
$$m^2=b^2c^2+b^2+c^2,$$
so ist \(A=m/2\). Ganzzahlige Fläche bedeutet daher genau, dass dieser Ausdruck eine gerade Quadratzahl ist.
Weil \(A\) ganzzahlig ist, ist \(m=2A\) gerade und damit \(m^2 \equiv 0 \pmod 4\). Quadrate sind modulo \(4\) aber nur \(0\) oder \(1\). Wäre einer von \(b,c\) ungerade, dann wäre
$$b^2c^2+b^2+c^2 \equiv 1 \text{ oder } 3 \pmod 4,$$
also unmöglich. Folglich sind in jeder gültigen Lösung sowohl \(b\) als auch \(c\) gerade. Wir schreiben deshalb
$$b=2p,\qquad c=2q,$$
mit ganzen Zahlen \(p,q \ge 1\). Dann wird die Flächenbedingung zu
$$A^2=4p^2q^2+p^2+q^2.$$
Diese Gleichung ist die eigentliche Grundlage des schnellen Zustandsgraphen.
Für festes \(p\) formt man um zu
$$A^2-(4p^2+1)q^2=p^2.$$
Mit
$$D_p=4p^2+1$$
liegt also die Pell-artige Normgleichung
$$A^2-D_p q^2=p^2$$
vor. Die triviale Lösung ist \(q=0\), \(A=p\). Der schnelle Solver startet an diesem trivialen Punkt und springt dann zur ersten positiven Lösung auf demselben Ast.
Die im Programm benutzte fundamentale Einheit von \(x^2-D_p y^2=1\) ist
$$u_p=(8p^2+1)+4p\sqrt{D_p},$$
denn
$$\left(8p^2+1\right)^2-D_p(4p)^2=1.$$
Multipliziert man eine Lösung \(A+q\sqrt{D_p}\) mit \(u_p\), erhält man die nächste Lösung desselben Astes:
$$A'+q'\sqrt{D_p}=u_p\left(A+q\sqrt{D_p}\right).$$
Durch Koeffizientenvergleich folgt
$$q'=(8p^2+1)q+4pA,$$
$$A'=4p(4p^2+1)q+(8p^2+1)A.$$
Das ist exakt die Rekurrenz in allen drei Implementierungen mit
$$a=8p^2+1,\qquad b=4p,\qquad c=4p(4p^2+1),$$
$$q'=a q+b A,\qquad A'=c q+a A.$$
Vom trivialen Zustand \((p,0,p)\) aus liefert ein Rekurrenzschritt
$$q_1=4p^2,\qquad A_1=(8p^2+1)p=8p^3+p.$$
Damit ist das erste echte Dreieck zum Seed \(p\)
$$b=2p,\qquad c=2q_1=8p^2,\qquad A=8p^3+p.$$
Genau daraus stammen die Funktion seed_first_area(p) und die binäre Suche in max_seed(limit): Sobald \(8p^3+p>L\) gilt, kann dieser Seed keinen Beitrag mehr zu \(S(L)\) liefern.
Für \(p=1\) ergibt sich
$$q_1=4,\qquad A_1=9,$$
also \((b,c)=(2,8)\). Die C++-Prüfung bestätigt
$$2^2\cdot 8^2+2^2+8^2=324=18^2,\qquad A=18/2=9.$$
Die Gleichung
$$A^2=4p^2q^2+p^2+q^2$$
ist symmetrisch in \(p\) und \(q\) und enthält nur Quadrate. Erzeugt die Rekurrenz also \((p,q',A')\), dann sind auch
$$(q',p,A')\qquad \text{und} \qquad (q',-p,A')$$
gültige Orientierungen derselben quadratischen Fläche. Darum legt die Implementierung drei Zustände auf den Stack:
$$(p,q',A'),\qquad (q',p,A'),\qquad (q',-p,A').$$
Der erste Zweig setzt den Pell-Ast mit festem \(p\) fort. Die beiden vertauschten Zweige erlauben, dass der neue Wert \(q'\) später selbst die feste Koordinate wird. Der Vorzeichen-Zweig ist nicht optional: Aus der Fläche \(9\) führt der Zustand \((4,-1,9)\) weiter zur Lösung \((4,15,121)\), also zum Paar \((b,c)=(8,30)\).
Eine gesonderte Eindeutigkeitsbeweisskizze liegt im Repository nicht vor; stattdessen wird die Baumkonstruktion durch exakten Vergleich mit Brute Force für kleine Grenzen und durch den Kontrollwert \(S(10^6)=18018206\) abgesichert.
Die C++-Datei enthält sowohl einen langsamen Validator als auch den optimierten Rekurrenz-Solver. Der Validator durchläuft ungeordnete Paare \(b \le c\), testet
$$m^2=b^2c^2+b^2+c^2$$
und prüft, ob \(m\) eine gerade Ganzzahlwurzel ist. Aus
$$bc \le 2A \le 2L$$
folgen die Schleifengrenzen \(b \le 2L\) und \(c \lesssim 2L/b\).
Der schnelle Teil arbeitet in Halbkoordinaten \((p,q)\). sum_for_seed führt eine iterative Tiefensuche mit Zuständen \((p,q,A)\) aus. next_state wendet die obige Pell-Rekurrenz an, verwirft Zweige mit \(A' \le 0\) oder \(A' > L\) und erzeugt die drei Nachfolgezustände. C++ verwendet 128-Bit-Zwischenwerte und verteilt die Seeds per atomarem Zähler auf Threads; Python nutzt beliebig große Integer, und Java verwendet BigInteger in der Rekurrenzarithmetik.
Der Brute-Force-Validator hat ungefähr Aufwand
$$\sum_{b \le 2L} O\!\left(\frac{L}{b}\right)=O(L\log L),$$
was für die echte Grenze nicht praktikabel ist. Der optimierte Solver ist ausgabesensitiv: Ist \(T(L)\) die Anzahl der erzeugten Zustände, deren nächste Fläche innerhalb der Schranke bleibt, dann kostet die Laufzeit \(O(T(L))\) arithmetische Übergänge. Der Speicherbedarf ist proportional zur aktiven Stackgröße pro Worker, nicht zu einem vollständigen \((b,c)\)-Gitter. Praktisch ist die Methode viel schneller, weil sie nur Pell-erzeugte Lösungen verfolgt statt fast alle Integerpaare zu testen.
Repository'deki çözümler, kenar uzunlukları
$$\sqrt{b^2+1},\qquad \sqrt{c^2+1},\qquad \sqrt{b^2+c^2}$$
olan üçgen ailesi üzerinde çalışır. Burada \(b\) ve \(c\) pozitif tamsayılardır; brute-force doğrulayıcı simetriden dolayı yalnızca \(b \le c\) olan sırasız çiftleri sayar. Alan \(A\) ise amaç
$$S(L)=\sum A$$
değerini, alanı tam sayı olan ve \(A \le L\) koşulunu sağlayan bütün bu üçgenler üzerinden hesaplamaktır.
Şöyle tanımlayalım:
$$x=\sqrt{b^2+1},\qquad y=\sqrt{c^2+1},\qquad z=\sqrt{b^2+c^2}.$$
Heron özdeşliği
$$16A^2=2x^2y^2+2y^2z^2+2z^2x^2-x^4-y^4-z^4$$
içine \(x^2=b^2+1\), \(y^2=c^2+1\), \(z^2=b^2+c^2\) yazılırsa
$$16A^2=4\left(b^2c^2+b^2+c^2\right)$$
elde edilir. Dolayısıyla
$$A=\frac{1}{2}\sqrt{b^2c^2+b^2+c^2}.$$
C++ brute-force kontrolünün kullandığı denklem tam olarak budur. Eğer
$$m^2=b^2c^2+b^2+c^2$$
yazarsak \(A=m/2\) olur. O halde alanın tam sayı olması, bu ifadenin çift bir karekök vermesiyle eşdeğerdir.
\(A\) tam sayı ise \(m=2A\) çifttir; dolayısıyla \(m^2 \equiv 0 \pmod 4\). Kareler mod \(4\)'te yalnızca \(0\) veya \(1\) olabilir. Eğer \(b\) ya da \(c\) tek olsaydı
$$b^2c^2+b^2+c^2 \equiv 1 \text{ veya } 3 \pmod 4$$
olurdu ve bu imkansızdır. Demek ki her geçerli çözümde \(b\) ve \(c\) çifttir. Bu yüzden
$$b=2p,\qquad c=2q$$
yazabiliriz. Yerine koyunca alan denklemi
$$A^2=4p^2q^2+p^2+q^2$$
haline gelir. Hızlı durum üreticisinin temel aldığı denklem budur.
\(p\) sabit tutulursa denklem
$$A^2-(4p^2+1)q^2=p^2$$
şeklinde yazılır. Şimdi
$$D_p=4p^2+1$$
tanımını yaparsak elimizde
$$A^2-D_p q^2=p^2$$
biçiminde Pell tipi bir norm denklemi vardır. Trivial çözüm \(q=0\), \(A=p\)'dir. Hızlı çözüm, her seed için bu trivial noktadan başlayıp aynı dal üzerindeki ilk pozitif çözüme sıçrar.
İmplementasyonun kullandığı temel birim
$$u_p=(8p^2+1)+4p\sqrt{D_p}$$
ifadesidir; çünkü
$$\left(8p^2+1\right)^2-D_p(4p)^2=1.$$
Bir çözüm \(A+q\sqrt{D_p}\) ile bunu çarparsak aynı dal üzerindeki sonraki çözümü elde ederiz:
$$A'+q'\sqrt{D_p}=u_p\left(A+q\sqrt{D_p}\right).$$
Katsayıları eşitleyince
$$q'=(8p^2+1)q+4pA,$$
$$A'=4p(4p^2+1)q+(8p^2+1)A$$
çıkar. Üç çözüm dosyasının hepsindeki geçiş tam olarak budur:
$$a=8p^2+1,\qquad b=4p,\qquad c=4p(4p^2+1),$$
$$q'=a q+b A,\qquad A'=c q+a A.$$
Trivial durum \((p,0,p)\) üzerinden bir adım gidince
$$q_1=4p^2,\qquad A_1=(8p^2+1)p=8p^3+p$$
elde edilir. Böylece seed \(p\) için ilk gerçek üçgen
$$b=2p,\qquad c=2q_1=8p^2,\qquad A=8p^3+p$$
şeklindedir. seed_first_area(p) yardımcı fonksiyonu ve max_seed(limit) içindeki ikili arama bundan gelir: Eğer \(8p^3+p>L\) ise o seed artık hiçbir katkı yapamaz.
\(p=1\) için
$$q_1=4,\qquad A_1=9$$
olur; yani \((b,c)=(2,8)\). C++ kontrolü şunu doğrular:
$$2^2\cdot 8^2+2^2+8^2=324=18^2,\qquad A=18/2=9.$$
Denklem
$$A^2=4p^2q^2+p^2+q^2$$
hem \(p\) ile \(q\) arasında simetriktir hem de yalnızca kareler içerir. Bu yüzden yineleme \((p,q',A')\) ürettiğinde
$$(q',p,A')\qquad \text{ve} \qquad (q',-p,A')$$
durumları da aynı yüzey üzerindeki geçerli yönelimlerdir. Kod bu nedenle şu üç durumu stack'e ekler:
$$(p,q',A'),\qquad (q',p,A'),\qquad (q',-p,A').$$
Birinci dal sabit \(p\) ile aynı Pell zincirini sürdürür. Yer değiştiren iki dal ise yeni \(q'\) değerinin ileride sabit koordinat rolüne geçmesine izin verir. Negatif işaret dalı zorunludur: Alan \(9\) sonrası \((4,-1,9)\) durumundan \((4,15,121)\) çözümü gelir; bu da \((b,c)=(8,30)\) çiftidir.
Repository içinde bu ağacın tekillik ispatı ayrı bir belge olarak tutulmuyor; bunun yerine yapı, küçük limitlerde brute-force ile birebir karşılaştırılarak ve \(S(10^6)=18018206\) kontrol değeriyle doğrulanıyor.
C++ dosyasında hem yavaş doğrulayıcı hem de hızlı yinelemeli çözücü vardır. Doğrulayıcı, \(b \le c\) sırasız çiftlerini dolaşır,
$$m^2=b^2c^2+b^2+c^2$$
ifadesini test eder ve \(m\)'nin çift bir tam karekök olup olmadığına bakar. Ayrıca
$$bc \le 2A \le 2L$$
eşitsizliğinden \(b \le 2L\) ve yaklaşık \(c \le 2L/b\) sınırları türetilir.
Hızlı çözüm yarı-koordinatlar \((p,q)\) üzerinde çalışır. sum_for_seed, \((p,q,A)\) durumlarını açık bir yığınla derinlik öncelikli gezer. next_state Pell adımını uygular, \(A' \le 0\) veya \(A' > L\) olan kolları budar ve üç yeni durum üretir. C++ sürümü taşmayı önlemek için 128 bit ara değerler kullanır ve seed'leri atomik sayaçla iş parçacıklarına dağıtır; Python büyük tamsayılardan yararlanır, Java ise yineleme aritmetiğinde BigInteger kullanır.
Brute-force doğrulayıcı yaklaşık olarak
$$\sum_{b \le 2L} O\!\left(\frac{L}{b}\right)=O(L\log L)$$
aday çifti inceler; bu da gerçek limit için fazla büyüktür. Hızlı çözüm ise çıktı-duyarlıdır: Eğer sınır içinde kalan geçerli durum sayısı \(T(L)\) ise çalışma süresi \(O(T(L))\) aritmetik geçiştir. Bellek kullanımı tam bir \((b,c)\) ızgarısına değil, her işçi için etkin DFS yığınına bağlıdır. Pratikte esas kazanç, neredeyse bütün tamsayı çiftlerini test etmek yerine yalnızca Pell yinelemesinin ürettiği seyrek çözümleri gezmesidir.
Las soluciones del repositorio trabajan con la familia de triángulos cuyas longitudes son
$$\sqrt{b^2+1},\qquad \sqrt{c^2+1},\qquad \sqrt{b^2+c^2},$$
donde \(b\) y \(c\) son enteros positivos. El verificador brute-force cuenta solo pares no ordenados con \(b \le c\). Si \(A\) es el área, debemos calcular
$$S(L)=\sum A,$$
sumando sobre todos los triángulos de esta familia cuya área es entera y satisface \(A \le L\).
Definimos
$$x=\sqrt{b^2+1},\qquad y=\sqrt{c^2+1},\qquad z=\sqrt{b^2+c^2}.$$
Usando la identidad de Herón
$$16A^2=2x^2y^2+2y^2z^2+2z^2x^2-x^4-y^4-z^4$$
y sustituyendo \(x^2=b^2+1\), \(y^2=c^2+1\), \(z^2=b^2+c^2\), obtenemos
$$16A^2=4\left(b^2c^2+b^2+c^2\right).$$
Por lo tanto
$$A=\frac{1}{2}\sqrt{b^2c^2+b^2+c^2}.$$
Esta es exactamente la relación usada por la comprobación brute-force en C++. Si escribimos
$$m^2=b^2c^2+b^2+c^2,$$
entonces \(A=m/2\). Así, el área es entera si y solo si esta expresión tiene una raíz cuadrada entera y además par.
Si \(A\) es entera, entonces \(m=2A\) es par, luego \(m^2 \equiv 0 \pmod 4\). Pero un cuadrado modulo \(4\) solo puede valer \(0\) o \(1\). Si \(b\) o \(c\) fueran impares, tendríamos
$$b^2c^2+b^2+c^2 \equiv 1 \text{ o } 3 \pmod 4,$$
lo cual es imposible. Por eso toda solución válida tiene \(b\) y \(c\) pares. Escribimos entonces
$$b=2p,\qquad c=2q,$$
con \(p,q \ge 1\). La condición del área pasa a ser
$$A^2=4p^2q^2+p^2+q^2.$$
Esta es la ecuación que realmente explota el generador rápido de estados.
Si fijamos \(p\), podemos reescribirla como
$$A^2-(4p^2+1)q^2=p^2.$$
Definiendo
$$D_p=4p^2+1,$$
obtenemos la ecuación de norma de tipo Pell
$$A^2-D_p q^2=p^2.$$
La solución trivial es \(q=0\), \(A=p\). El algoritmo rápido parte de ese punto trivial y salta a la primera solución positiva de la misma rama.
La unidad fundamental usada por la implementación para \(x^2-D_p y^2=1\) es
$$u_p=(8p^2+1)+4p\sqrt{D_p},$$
porque
$$\left(8p^2+1\right)^2-D_p(4p)^2=1.$$
Si multiplicamos una solución \(A+q\sqrt{D_p}\) por \(u_p\), obtenemos la siguiente solución de la misma rama:
$$A'+q'\sqrt{D_p}=u_p\left(A+q\sqrt{D_p}\right).$$
Al comparar coeficientes se obtiene
$$q'=(8p^2+1)q+4pA,$$
$$A'=4p(4p^2+1)q+(8p^2+1)A.$$
Esto coincide exactamente con el código en C++, Python y Java:
$$a=8p^2+1,\qquad b=4p,\qquad c=4p(4p^2+1),$$
$$q'=a q+b A,\qquad A'=c q+a A.$$
Desde el estado trivial \((p,0,p)\), un paso de la recurrencia produce
$$q_1=4p^2,\qquad A_1=(8p^2+1)p=8p^3+p.$$
Así, el primer triángulo real asociado a la semilla \(p\) es
$$b=2p,\qquad c=2q_1=8p^2,\qquad A=8p^3+p.$$
De aquí salen directamente seed_first_area(p) y la búsqueda binaria de max_seed(limit): cuando \(8p^3+p>L\), esa semilla ya no puede contribuir.
Para \(p=1\) tenemos
$$q_1=4,\qquad A_1=9,$$
es decir, \((b,c)=(2,8)\). El checkpoint de C++ comprueba que
$$2^2\cdot 8^2+2^2+8^2=324=18^2,\qquad A=18/2=9.$$
La ecuación
$$A^2=4p^2q^2+p^2+q^2$$
es simétrica en \(p\) y \(q\), y además solo contiene sus cuadrados. Por eso, cuando la recurrencia genera \((p,q',A')\), los estados
$$(q',p,A')\qquad \text{y} \qquad (q',-p,A')$$
también son orientaciones válidas de la misma superficie cuadrática. Por eso la implementación apila
$$(p,q',A'),\qquad (q',p,A'),\qquad (q',-p,A').$$
La primera rama continúa la misma cadena de Pell con \(p\) fijo. Las otras dos permiten que el nuevo valor \(q'\) se convierta después en la coordenada fija. La rama con signo negativo es necesaria: a partir del área \(9\), el estado \((4,-1,9)\) conduce a \((4,15,121)\), que corresponde al par \((b,c)=(8,30)\).
El repositorio no guarda una demostración formal separada de unicidad para este árbol; en cambio, valida la construcción comparándola exactamente con brute force para un límite pequeño y verificando además el control \(S(10^6)=18018206\).
El archivo C++ contiene tanto el validador lento como el solver optimizado. El validador recorre pares no ordenados \(b \le c\), calcula
$$m^2=b^2c^2+b^2+c^2$$
y comprueba si \(m\) es una raíz cuadrada entera y par. La desigualdad
$$bc \le 2A \le 2L$$
explica las cotas \(b \le 2L\) y \(c \lesssim 2L/b\).
El solver rápido trabaja con medias coordenadas \((p,q)\). La función sum_for_seed realiza una búsqueda en profundidad iterativa con una pila de estados \((p,q,A)\). La función next_state aplica el paso de Pell, descarta ramas con \(A' \le 0\) o \(A' > L\) y genera los tres sucesores. En C++ se usan intermedios de 128 bits y las semillas se reparten entre hilos mediante un contador atómico; Python aprovecha enteros arbitrariamente grandes y Java usa BigInteger en la aritmética de la recurrencia.
El validador brute-force inspecciona aproximadamente
$$\sum_{b \le 2L} O\!\left(\frac{L}{b}\right)=O(L\log L)$$
pares candidatos, lo cual es demasiado grande para el límite real. El solver optimizado es sensible a la salida: si \(T(L)\) es el número de estados generados cuya siguiente área aún está dentro del límite, entonces el tiempo es \(O(T(L))\) transiciones aritméticas. La memoria es proporcional al tamaño máximo de la pila DFS por trabajador, no a una rejilla completa \((b,c)\). La mejora práctica proviene de seguir solo soluciones generadas por la recurrencia de Pell, en lugar de probar casi todos los pares enteros.
仓库中的解法处理的是边长为
$$\sqrt{b^2+1},\qquad \sqrt{c^2+1},\qquad \sqrt{b^2+c^2}$$
的一族三角形，其中 \(b,c\) 是正整数。C++ 的暴力校验只统计无序对 \(b \le c\)，以避免对称重复。若面积记为 \(A\)，目标就是计算
$$S(L)=\sum A,$$
求和范围是所有面积为整数且满足 \(A \le L\) 的这类三角形。
记
$$x=\sqrt{b^2+1},\qquad y=\sqrt{c^2+1},\qquad z=\sqrt{b^2+c^2}.$$
应用 Heron 恒等式
$$16A^2=2x^2y^2+2y^2z^2+2z^2x^2-x^4-y^4-z^4$$
并代入 \(x^2=b^2+1\)、\(y^2=c^2+1\)、\(z^2=b^2+c^2\)，可得
$$16A^2=4\left(b^2c^2+b^2+c^2\right).$$
因此
$$A=\frac{1}{2}\sqrt{b^2c^2+b^2+c^2}.$$
这正是 C++ 暴力校验中使用的核心关系。若写成
$$m^2=b^2c^2+b^2+c^2,$$
那么 \(A=m/2\)。所以面积为整数，当且仅当该表达式的平方根 \(m\) 是偶整数。
既然 \(A\) 是整数，则 \(m=2A\) 必为偶数，从而 \(m^2 \equiv 0 \pmod 4\)。但平方数模 \(4\) 只能是 \(0\) 或 \(1\)。如果 \(b\) 或 \(c\) 中有一个是奇数，那么
$$b^2c^2+b^2+c^2 \equiv 1 \text{ 或 } 3 \pmod 4,$$
矛盾。因此所有有效解都满足 \(b,c\) 为偶数。于是可写
$$b=2p,\qquad c=2q,$$
其中 \(p,q \ge 1\)。代回去得到
$$A^2=4p^2q^2+p^2+q^2.$$
快速状态生成器真正处理的就是这个方程。
把 \(p\) 固定后，方程可改写为
$$A^2-(4p^2+1)q^2=p^2.$$
定义
$$D_p=4p^2+1,$$
就得到 Pell 型范数方程
$$A^2-D_p q^2=p^2.$$
它的平凡解是 \(q=0,\ A=p\)。快速算法正是从这个平凡点出发，再跳到同一分支上的第一个正解。
实现所使用的单位元是
$$u_p=(8p^2+1)+4p\sqrt{D_p},$$
因为
$$\left(8p^2+1\right)^2-D_p(4p)^2=1.$$
若 \(A+q\sqrt{D_p}\) 是一组解，则与 \(u_p\) 相乘后得到同一分支上的下一组解：
$$A'+q'\sqrt{D_p}=u_p\left(A+q\sqrt{D_p}\right).$$
比较系数即可得到
$$q'=(8p^2+1)q+4pA,$$
$$A'=4p(4p^2+1)q+(8p^2+1)A.$$
这与三份本地实现完全一致：
$$a=8p^2+1,\qquad b=4p,\qquad c=4p(4p^2+1),$$
$$q'=a q+b A,\qquad A'=c q+a A.$$
从平凡状态 \((p,0,p)\) 出发做一步递推，得到
$$q_1=4p^2,\qquad A_1=(8p^2+1)p=8p^3+p.$$
因此，种子 \(p\) 的第一个真实三角形满足
$$b=2p,\qquad c=2q_1=8p^2,\qquad A=8p^3+p.$$
这正解释了 seed_first_area(p) 和 max_seed(limit) 中的二分搜索：一旦 \(8p^3+p>L\)，该种子就不可能再贡献任何合法面积。
当 \(p=1\) 时，
$$q_1=4,\qquad A_1=9,$$
对应 \((b,c)=(2,8)\)。C++ 检查点验证了
$$2^2\cdot 8^2+2^2+8^2=324=18^2,\qquad A=18/2=9.$$
方程
$$A^2=4p^2q^2+p^2+q^2$$
对 \(p,q\) 是对称的，而且只出现平方项。因此一旦递推得到 \((p,q',A')\)，那么
$$(q',p,A')\qquad \text{和} \qquad (q',-p,A')$$
也都是同一二次曲面上的合法定向状态。代码因此把以下三个状态全部压栈：
$$(p,q',A'),\qquad (q',p,A'),\qquad (q',-p,A').$$
第一条分支沿着固定 \(p\) 的同一 Pell 链继续前进；另外两条交换分支则允许新得到的 \(q'\) 在后续步骤中变成固定坐标。负号分支不是装饰，而是必要的。例如面积 \(9\) 对应的状态 \((4,-1,9)\) 再递推一次，就会得到 \((4,15,121)\)，也就是 \((b,c)=(8,30)\)。
仓库中没有单独保存该树结构“每个解只出现一次”的形式化证明，但实现确实用小范围暴力枚举和题目校验值 \(S(10^6)=18018206\) 做了严格比对。
C++ 文件同时包含慢速校验器和快速递推求解器。校验器遍历无序对 \(b \le c\)，检查
$$m^2=b^2c^2+b^2+c^2$$
是否有偶整数平方根。由
$$bc \le 2A \le 2L$$
可推出循环上界 \(b \le 2L\) 以及近似的 \(c \le 2L/b\)。
快速求解器在半坐标 \((p,q)\) 上工作。sum_for_seed 用显式栈执行深度优先遍历，状态为 \((p,q,A)\)。next_state 应用上面的 Pell 递推，剪掉 \(A' \le 0\) 或 \(A' > L\) 的分支，并生成三个后继状态。C++ 版本使用 128 位中间值并通过原子计数器把不同种子分发到多个线程；Python 依靠任意精度整数，Java 则用 BigInteger 处理递推中的大数乘加。
暴力校验器大约需要检查
$$\sum_{b \le 2L} O\!\left(\frac{L}{b}\right)=O(L\log L)$$
个候选对，这对真实上界来说显然过慢。优化后的求解器是输出敏感的：如果边界内实际生成的状态数为 \(T(L)\)，那么总时间就是 \(O(T(L))\) 次算术转移。内存只与每个工作线程的 DFS 栈规模有关，而不是与完整的 \((b,c)\) 网格成正比。真正的提速来自这一点：程序只沿 Pell 递推产生的稀疏整数解前进，而不再对几乎全部整数对做试探。
Решения в репозитории рассматривают семейство треугольников со сторонами
$$\sqrt{b^2+1},\qquad \sqrt{c^2+1},\qquad \sqrt{b^2+c^2},$$
где \(b\) и \(c\) являются положительными целыми числами. Brute-force проверка в C++ перебирает только неупорядоченные пары \(b \le c\), чтобы не считать симметричные случаи дважды. Если площадь равна \(A\), нужно вычислить
$$S(L)=\sum A,$$
суммируя по всем таким треугольникам, для которых площадь целая и удовлетворяет \(A \le L\).
Обозначим
$$x=\sqrt{b^2+1},\qquad y=\sqrt{c^2+1},\qquad z=\sqrt{b^2+c^2}.$$
По формуле Герона в виде
$$16A^2=2x^2y^2+2y^2z^2+2z^2x^2-x^4-y^4-z^4$$
после подстановки \(x^2=b^2+1\), \(y^2=c^2+1\), \(z^2=b^2+c^2\) получаем
$$16A^2=4\left(b^2c^2+b^2+c^2\right).$$
Следовательно,
$$A=\frac{1}{2}\sqrt{b^2c^2+b^2+c^2}.$$
Именно это равенство использует C++-валидатор. Если записать
$$m^2=b^2c^2+b^2+c^2,$$
то \(A=m/2\). Значит, целая площадь возникает тогда и только тогда, когда указанный радикал является чётным целым числом.
Если \(A\) целое, то \(m=2A\) чётно, следовательно \(m^2 \equiv 0 \pmod 4\). Но квадрат по модулю \(4\) может быть только \(0\) или \(1\). Если хотя бы одно из чисел \(b,c\) нечётно, то
$$b^2c^2+b^2+c^2 \equiv 1 \text{ или } 3 \pmod 4,$$
что невозможно. Поэтому в любом допустимом решении оба параметра чётные. Пишем
$$b=2p,\qquad c=2q,$$
где \(p,q \ge 1\). Тогда условие на площадь становится
$$A^2=4p^2q^2+p^2+q^2.$$
Именно это уравнение быстрое решение и перечисляет.
При фиксированном \(p\) имеем
$$A^2-(4p^2+1)q^2=p^2.$$
Обозначим
$$D_p=4p^2+1.$$
Тогда получаем Pell-подобное уравнение нормы
$$A^2-D_p q^2=p^2.$$
Тривиальное решение равно \(q=0,\ A=p\). Быстрый алгоритм стартует именно из этой точки и затем переходит к первой положительной точке той же ветви.
Фундаментальная единица, используемая в реализации для \(x^2-D_p y^2=1\), равна
$$u_p=(8p^2+1)+4p\sqrt{D_p},$$
поскольку
$$\left(8p^2+1\right)^2-D_p(4p)^2=1.$$
Если \(A+q\sqrt{D_p}\) является решением, то произведение с \(u_p\) даёт следующее решение на той же ветви:
$$A'+q'\sqrt{D_p}=u_p\left(A+q\sqrt{D_p}\right).$$
Сравнивая коэффициенты, получаем
$$q'=(8p^2+1)q+4pA,$$
$$A'=4p(4p^2+1)q+(8p^2+1)A.$$
Это в точности совпадает с переходом в локальных реализациях:
$$a=8p^2+1,\qquad b=4p,\qquad c=4p(4p^2+1),$$
$$q'=a q+b A,\qquad A'=c q+a A.$$
Из тривиального состояния \((p,0,p)\) один шаг рекурсии даёт
$$q_1=4p^2,\qquad A_1=(8p^2+1)p=8p^3+p.$$
Значит, первый реальный треугольник для seed \(p\) имеет параметры
$$b=2p,\qquad c=2q_1=8p^2,\qquad A=8p^3+p.$$
Отсюда напрямую следуют функция seed_first_area(p) и бинарный поиск в max_seed(limit): если уже \(8p^3+p>L\), то данный seed не может внести вклад в ответ.
При \(p=1\) имеем
$$q_1=4,\qquad A_1=9,$$
то есть \((b,c)=(2,8)\). Проверка в C++ подтверждает, что
$$2^2\cdot 8^2+2^2+8^2=324=18^2,\qquad A=18/2=9.$$
Уравнение
$$A^2=4p^2q^2+p^2+q^2$$
симметрично по \(p\) и \(q\), и в нём фигурируют только квадраты этих величин. Поэтому, если рекурсия породила состояние \((p,q',A')\), то состояния
$$(q',p,A')\qquad \text{и} \qquad (q',-p,A')$$
тоже являются допустимыми ориентациями той же квадратической поверхности. Поэтому программа кладёт в стек три состояния:
$$(p,q',A'),\qquad (q',p,A'),\qquad (q',-p,A').$$
Первая ветвь продолжает ту же Pell-цепочку при фиксированном \(p\). Две переставленные ветви позволяют новому значению \(q'\) позже стать фиксированной координатой. Ветвь с отрицательным знаком действительно нужна: из площади \(9\) состояние \((4,-1,9)\) приводит к \((4,15,121)\), то есть к паре \((b,c)=(8,30)\).
В репозитории нет отдельного формального доказательства того, что дерево перечисляет каждое решение ровно один раз; вместо этого корректность проверяется точным сравнением с brute force на малом пределе и контрольным значением \(S(10^6)=18018206\).
Файл на C++ содержит и медленный валидатор, и оптимизированный рекуррентный решатель. Валидатор перебирает неупорядоченные пары \(b \le c\), вычисляет
$$m^2=b^2c^2+b^2+c^2$$
и проверяет, является ли \(m\) чётным целым корнем. Неравенство
$$bc \le 2A \le 2L$$
объясняет границы \(b \le 2L\) и \(c \lesssim 2L/b\).
Быстрое решение работает в половинных координатах \((p,q)\). Функция sum_for_seed выполняет итеративный DFS со стеком состояний \((p,q,A)\). Функция next_state применяет описанный Pell-переход, отбрасывает ветви с \(A' \le 0\) или \(A' > L\) и создаёт три следующих состояния. Версия на C++ использует 128-битные промежуточные значения и распределяет seed по потокам через атомарный счётчик; Python полагается на длинную арифметику, а Java использует BigInteger для рекуррентных вычислений.
Brute-force валидатор просматривает примерно
$$\sum_{b \le 2L} O\!\left(\frac{L}{b}\right)=O(L\log L)$$
кандидатных пар, что слишком дорого для реального ограничения. Оптимизированный алгоритм чувствителен к выходу: если \(T(L)\) обозначает число сгенерированных состояний, у которых следующая площадь остаётся в пределах границы, то время работы равно \(O(T(L))\) арифметических переходов. Память пропорциональна максимальному размеру активного DFS-стека на поток, а не размеру полной сетки \((b,c)\). Практическое ускорение появляется потому, что перебираются только редкие решения, порождённые Pell-рекурсией, а не почти все пары целых чисел.
الحلول الموجودة في المستودع تتعامل مع عائلة من المثلثات أطوال أضلاعها
$$\sqrt{b^2+1},\qquad \sqrt{c^2+1},\qquad \sqrt{b^2+c^2}$$
حيث إن \(b\) و\(c\) عددان صحيحان موجبان. أداة التحقق brute-force في C++ تعد فقط الأزواج غير المرتبة ذات الشرط \(b \le c\) حتى لا تُحسب الحالات المتناظرة مرتين. إذا كانت المساحة \(A\)، فالمطلوب هو حساب
$$S(L)=\sum A,$$
حيث يؤخذ المجموع على كل هذه المثلثات التي تكون مساحتها عددًا صحيحًا وتحقق \(A \le L\).
لنكتب
$$x=\sqrt{b^2+1},\qquad y=\sqrt{c^2+1},\qquad z=\sqrt{b^2+c^2}.$$
وباستخدام صيغة هيرون على الصورة
$$16A^2=2x^2y^2+2y^2z^2+2z^2x^2-x^4-y^4-z^4$$
ثم التعويض بـ \(x^2=b^2+1\)، و\(y^2=c^2+1\)، و\(z^2=b^2+c^2\)، نحصل على
$$16A^2=4\left(b^2c^2+b^2+c^2\right).$$
ومن ثم
$$A=\frac{1}{2}\sqrt{b^2c^2+b^2+c^2}.$$
وهذه هي العلاقة نفسها التي يستخدمها فحص brute-force في C++. وإذا كتبنا
$$m^2=b^2c^2+b^2+c^2,$$
فإن \(A=m/2\). لذلك تكون المساحة صحيحة تمامًا عندما يكون هذا الجذر التربيعي عددًا صحيحًا زوجيًا.
بما أن \(A\) عدد صحيح، فإن \(m=2A\) زوجي، وبالتالي \(m^2 \equiv 0 \pmod 4\). لكن أي مربع modulo \(4\) لا يكون إلا \(0\) أو \(1\). فإذا كان أحد العددين \(b\) أو \(c\) فرديًا، لكان
$$b^2c^2+b^2+c^2 \equiv 1 \text{ or } 3 \pmod 4,$$
وهذا مستحيل. إذن كل حل صالح يحقق أن \(b\) و\(c\) زوجيان. لذلك نكتب
$$b=2p,\qquad c=2q,$$
حيث \(p,q \ge 1\). وعند التعويض تصبح معادلة المساحة
$$A^2=4p^2q^2+p^2+q^2.$$
وهذه هي المعادلة التي يبني عليها مولد الحالات السريع.
عند تثبيت \(p\) يمكن إعادة كتابة المعادلة على الصورة
$$A^2-(4p^2+1)q^2=p^2.$$
إذا عرّفنا
$$D_p=4p^2+1,$$
فإننا نحصل على معادلة معيار من نوع Pell:
$$A^2-D_p q^2=p^2.$$
الحل التافه هو \(q=0\) و\(A=p\). الخوارزمية السريعة تبدأ من هذه النقطة التافهة ثم تنتقل إلى أول حل موجب على الفرع نفسه.
الوحدة الأساسية التي تستعملها الشيفرة في المعادلة \(x^2-D_p y^2=1\) هي
$$u_p=(8p^2+1)+4p\sqrt{D_p},$$
لأن
$$\left(8p^2+1\right)^2-D_p(4p)^2=1.$$
إذا كانت \(A+q\sqrt{D_p}\) حلًا، فإن ضربها في \(u_p\) يعطي الحل التالي على الفرع نفسه:
$$A'+q'\sqrt{D_p}=u_p\left(A+q\sqrt{D_p}\right).$$
وبمقارنة المعاملات نحصل على
$$q'=(8p^2+1)q+4pA,$$
$$A'=4p(4p^2+1)q+(8p^2+1)A.$$
وهذا يطابق تمامًا الانتقال الموجود في ملفات C++ وPython وJava:
$$a=8p^2+1,\qquad b=4p,\qquad c=4p(4p^2+1),$$
$$q'=a q+b A,\qquad A'=c q+a A.$$
إذا بدأنا من الحالة التافهة \((p,0,p)\)، فإن خطوة واحدة من التكرار تعطي
$$q_1=4p^2,\qquad A_1=(8p^2+1)p=8p^3+p.$$
إذن أول مثلث فعلي مرتبط بالبذرة \(p\) يحقق
$$b=2p,\qquad c=2q_1=8p^2,\qquad A=8p^3+p.$$
ومن هنا تأتي الدالة seed_first_area(p) والبحث الثنائي داخل max_seed(limit): إذا كان \(8p^3+p>L\)، فلن تتمكن تلك البذرة من إنتاج أي مساهمة ضمن الحد.
عند \(p=1\) نحصل على
$$q_1=4,\qquad A_1=9,$$
أي على الزوج \((b,c)=(2,8)\). ويفحص C++ أن
$$2^2\cdot 8^2+2^2+8^2=324=18^2,\qquad A=18/2=9.$$
المعادلة
$$A^2=4p^2q^2+p^2+q^2$$
متماثلة في \(p\) و\(q\)، كما أنها تحتوي فقط على مربعاتهما. لذلك عندما ينتج التكرار الحالة \((p,q',A')\)، فإن
$$(q',p,A')\qquad \text{and} \qquad (q',-p,A')$$
يمثلان أيضًا اتجاهين صالحين للسطح التربيعي نفسه. ولهذا تدفع الشيفرة ثلاث حالات إلى المكدس:
$$(p,q',A'),\qquad (q',p,A'),\qquad (q',-p,A').$$
الفرع الأول يواصل سلسلة Pell نفسها عند تثبيت \(p\). أما الفرعان المتبادلان فيسمحان للقيمة الجديدة \(q'\) بأن تصبح لاحقًا الإحداثي المثبت. وفرع الإشارة السالبة ضروري فعلًا: فبعد المساحة \(9\)، تقود الحالة \((4,-1,9)\) إلى الحل \((4,15,121)\)، أي إلى الزوج \((b,c)=(8,30)\).
المستودع لا يحتوي على برهان منفصل ورسمي على أن هذه الشجرة تعد كل حل مرة واحدة فقط، لكنه يتحقق من صحة البنية بمقارنة دقيقة مع brute-force عند حد صغير، ثم بالتحقق من القيمة المرجعية \(S(10^6)=18018206\).
ملف C++ يحتوي على مُحقِّق بطيء وحل سريع مبني على التكرار. المُحقِّق يمر على الأزواج غير المرتبة \(b \le c\)، ويختبر
$$m^2=b^2c^2+b^2+c^2$$
ثم يفحص ما إذا كان \(m\) جذرًا صحيحًا زوجيًا. كما أن المتباينة
$$bc \le 2A \le 2L$$
تفسر الحد \(b \le 2L\) والحد الداخلي التقريبي \(c \le 2L/b\).
الحل السريع يعمل في الإحداثيات النصفية \((p,q)\). الدالة sum_for_seed تنفذ DFS تكراريًا باستخدام مكدس من الحالات \((p,q,A)\). الدالة next_state تطبق خطوة Pell المذكورة، وتحذف الفروع التي تحقق \(A' \le 0\) أو \(A' > L\)، ثم تولد الحالات الثلاث اللاحقة. نسخة C++ تستخدم قيمًا وسيطة من 128 بت وتوزع البذور على الخيوط عبر عداد ذري؛ أما Python فتستفيد من الأعداد الصحيحة ذات الدقة غير المحدودة، بينما تستخدم Java النوع BigInteger في حسابات التكرار.
مُحقِّق brute-force يفحص تقريبًا
$$\sum_{b \le 2L} O\!\left(\frac{L}{b}\right)=O(L\log L)$$
من الأزواج المرشحة، وهذا بطيء جدًا عند الحد الحقيقي للمسألة. أما الحل المحسن فهو حساس للمخرجات: إذا كان \(T(L)\) هو عدد الحالات المولدة التي تبقى مساحتها التالية ضمن الحد، فإن زمن التنفيذ يساوي \(O(T(L))\) انتقالات حسابية. الذاكرة تتناسب مع الحجم الأعظمي لمكدس DFS لكل عامل، لا مع شبكة كاملة من الأزواج \((b,c)\). والتحسن العملي الأساسي يأتي من تتبع الحلول النادرة التي تولدها علاقة Pell فقط، بدل اختبار معظم الأزواج الصحيحة الممكنة.