We count integer-sided triangles with one \(120^\circ\) angle opposite side \(c\), ordered so that \(a \le b \le c\), with the near-isosceles restriction \(b-a \le 100\) and the size bound \(c \le N\). The target value is \(T(10^{100})\), so a direct search over side lengths is hopeless. The solution must generate all valid families algebraically and then count only the distinct ordered triples.
Once the angle is fixed at \(120^\circ\), the geometry turns into a quadratic Diophantine equation. The standard parameterization for integer \(120^\circ\) triangles then converts the near-isosceles condition into a Pell-type equation with a very small right-hand side.
By the law of cosines, a triangle with angle \(120^\circ\) opposite \(c\) satisfies
$$c^2=a^2+b^2-2ab\cos 120^\circ=a^2+b^2+ab.$$
So every admissible triangle corresponds to a positive integer solution of
$$c^2=a^2+b^2+ab,\qquad a \le b \le c.$$
This quadratic form is the norm form associated with Eisenstein integers, which is why a clean two-parameter description exists.
For integers \(u>v>0\), define
$$a^\ast=u^2-v^2,\qquad b^\ast=2uv+v^2,\qquad c^\ast=u^2+uv+v^2.$$
A direct expansion shows that
$$\left(c^\ast\right)^2=\left(a^\ast\right)^2+\left(b^\ast\right)^2+a^\ast b^\ast.$$
Thus \((a^\ast,b^\ast,c^\ast)\) is a primitive integer \(120^\circ\) triangle, except that the two shorter sides are not automatically ordered. Every non-primitive solution is obtained by scaling:
$$ (a,b,c)=\lambda\bigl(\min(a^\ast,b^\ast),\max(a^\ast,b^\ast),c^\ast\bigr),\qquad \lambda \ge 1.$$
The counting problem is therefore reduced to generating primitive triangles and then determining how many scale factors \(\lambda\) remain legal.
Write
$$r=u-v>0,\qquad u=v+r.$$
Then the difference between the two shorter sides becomes
$$b^\ast-a^\ast=2uv+v^2-(u^2-v^2)=3v^2-r^2.$$
Equivalently,
$$r^2-3v^2=d,\qquad d=-(b^\ast-a^\ast).$$
After ordering the shorter sides, their gap is exactly
$$\bigl|\max(a^\ast,b^\ast)-\min(a^\ast,b^\ast)\bigr|=|d|.$$
Scaling by \(\lambda\) multiplies every side difference by \(\lambda\), so the condition \(b-a \le 100\) becomes
$$\lambda |d| \le 100.$$
Therefore only nonzero integers \(d\) with \(|d|\le 100\) matter, and every primitive triangle for that \(d\) can be scaled only up to
$$1 \le \lambda \le \left\lfloor\frac{100}{|d|}\right\rfloor.$$
The case \(d=0\) would require \(r^2=3v^2\), impossible for positive integers, so the search really is over \(d\in\{-100,\dots,-1,1,\dots,100\}\).
For fixed \(d\), we must solve
$$r^2-3v^2=d,\qquad r>0,\quad v>0.$$
This is a Pell-type equation. Its positive solutions break into finitely many orbits under multiplication by the fundamental unit \(2+\sqrt{3}\). In coordinates, one forward step is
$$r' = 2r+3v,\qquad v' = r+2v.$$
If \((r,v)\) solves \(r^2-3v^2=d\), then so does \((r',v')\). The reverse unit \(2-\sqrt{3}\) gives
$$r_- = 2r-3v,\qquad v_- = -r+2v,$$
which preserves the same equation whenever both values stay positive. Repeating this reverse step until positivity would fail produces a reduced representative of the orbit. Starting from one reduced representative for each orbit and iterating forward generates every positive solution in that orbit.
Once a solution \((r,v)\) is known, we recover
$$u=v+r,$$
$$a^\ast=u^2-v^2,\qquad b^\ast=2uv+v^2,\qquad c^\ast=u^2+uv+v^2.$$
The primitive triangle contributes all scaled copies with
$$1 \le \lambda \le \min\left(\left\lfloor\frac{100}{|d|}\right\rfloor,\left\lfloor\frac{N}{c^\ast}\right\rfloor\right).$$
Every such \(\lambda\) gives one admissible triangle after sorting the two shorter sides. Because repeated generation can occur, the implementation stores the final ordered triples in a set and counts each distinct triangle only once.
Take \(d=1\). Then
$$r^2-3v^2=1$$
has the positive solution \((r,v)=(2,1)\). Hence \(u=v+r=3\), so
$$a^\ast=3^2-1^2=8,\qquad b^\ast=2\cdot 3\cdot 1+1^2=7,\qquad c^\ast=3^2+3\cdot 1+1^2=13.$$
After ordering the shorter sides we obtain \((7,8,13)\), whose gap is indeed \(1\). For any bound \(N\ge 13\), the allowed scales are
$$1 \le \lambda \le \min\left(100,\left\lfloor\frac{N}{13}\right\rfloor\right).$$
Applying the forward recurrence once gives
$$ (r',v')=(2\cdot 2+3\cdot 1,\;2+2\cdot 1)=(7,4).$$
Now \(u=11\), which yields the primitive triangle \((104,105,181)\) after ordering. It again has short-side difference \(1\). This shows how one small value of \(d\) creates an infinite family, while the bound \(c\le N\) truncates the family to finitely many members.
The C++, Python, and Java implementations all follow the same structure. They iterate through every signed difference parameter \(d\) with \(-100 \le d \le 100\) and \(d \ne 0\). For each \(d\), the maximum scale allowed by the near-isosceles restriction is precomputed as \(\lfloor 100/|d| \rfloor\).
Next, the implementation finds reduced positive solutions of the Pell-type equation \(r^2-3v^2=d\). Those reduced representatives are cached so that each orbit is discovered once. From every representative, the forward recurrence generated by \(2+\sqrt{3}\) is applied repeatedly. Each new pair \((r,v)\) produces one primitive triangle, and the orbit stops as soon as the corresponding \(c^\ast\) already exceeds \(N\).
For every primitive triangle, the two shorter sides are sorted, and every admissible scale factor
$$1 \le \lambda \le \min\left(\left\lfloor\frac{100}{|d|}\right\rfloor,\left\lfloor\frac{N}{c^\ast}\right\rfloor\right)$$
is tested. The resulting ordered triple is inserted into a set, which guarantees exact deduplication. Two useful checkpoints for this method are \(T(1000)=235\) and \(T(10^8)=1245\), after which the same machinery is applied to \(N=10^{100}\).
The outer loop over \(d\) has constant size, since only \(200\) nonzero values are relevant. Along any fixed Pell orbit, the quantities \(r\), \(v\), and \(c^\ast\) grow roughly by the factor \(2+\sqrt{3}\), so the number of primitive triangles with \(c^\ast \le N\) is \(O(\log N)\) on that orbit. The number of scale factors per primitive triangle is at most \(100\), which is also a constant.
If \(M\) denotes the number of candidate triangles produced before deduplication, then generation is essentially linear in \(M\). Deduplication costs \(O(M\log M)\) in a tree-based set model, or near-linear expected time with hash-based sets. Memory usage is \(O(M)\). In practice this is tiny compared with any direct search over side lengths.
Gesucht ist die Anzahl ganzzahliger Dreiecke mit einem \(120^\circ\)-Winkel gegenüber der Seite \(c\), geordnet durch \(a \le b \le c\), mit der Fast-Gleichschenkligkeit \(b-a \le 100\) und der Schranke \(c \le N\). Für \(N=10^{100}\) ist eine direkte Suche über Seitenlängen unmöglich. Deshalb erzeugt die Lösung alle zulässigen Familien algebraisch und zählt anschließend nur die verschiedenen geordneten Tripel.
Sobald der Winkel \(120^\circ\) feststeht, wird das Geometrieproblem zu einer quadratischen diophantischen Gleichung. Die Standardparametrisierung ganzzahliger \(120^\circ\)-Dreiecke verwandelt die Bedingung „nahezu gleichschenklig“ dann in eine Pell-artige Gleichung mit sehr kleiner rechter Seite.
Nach dem Kosinussatz gilt für einen \(120^\circ\)-Winkel gegenüber \(c\)
$$c^2=a^2+b^2-2ab\cos 120^\circ=a^2+b^2+ab.$$
Jedes zulässige Dreieck entspricht also einer positiven ganzzahligen Lösung von
$$c^2=a^2+b^2+ab,\qquad a \le b \le c.$$
Diese quadratische Form ist die Normform der Eisenstein-Zahlen; daher existiert eine saubere Parametrisierung mit zwei Parametern.
Für ganze Zahlen \(u>v>0\) setze
$$a^\ast=u^2-v^2,\qquad b^\ast=2uv+v^2,\qquad c^\ast=u^2+uv+v^2.$$
Direktes Ausmultiplizieren zeigt
$$\left(c^\ast\right)^2=\left(a^\ast\right)^2+\left(b^\ast\right)^2+a^\ast b^\ast.$$
Damit ist \((a^\ast,b^\ast,c^\ast)\) ein primitives ganzzahliges \(120^\circ\)-Dreieck, wobei die beiden kürzeren Seiten noch nicht notwendigerweise sortiert sind. Jede nichtprimitive Lösung entsteht dann durch Skalierung:
$$ (a,b,c)=\lambda\bigl(\min(a^\ast,b^\ast),\max(a^\ast,b^\ast),c^\ast\bigr),\qquad \lambda \ge 1.$$
Das Zählproblem reduziert sich somit darauf, primitive Dreiecke zu erzeugen und anschließend zu bestimmen, wie viele Skalierungsfaktoren \(\lambda\) erlaubt bleiben.
Schreibe
$$r=u-v>0,\qquad u=v+r.$$
Dann wird die Differenz der beiden kürzeren Seiten zu
$$b^\ast-a^\ast=2uv+v^2-(u^2-v^2)=3v^2-r^2.$$
Äquivalent dazu ist
$$r^2-3v^2=d,\qquad d=-(b^\ast-a^\ast).$$
Nach dem Sortieren der kürzeren Seiten ist ihr Abstand genau
$$\bigl|\max(a^\ast,b^\ast)-\min(a^\ast,b^\ast)\bigr|=|d|.$$
Eine Skalierung mit \(\lambda\) multipliziert auch diese Differenz mit \(\lambda\), also wird aus \(b-a \le 100\) die Bedingung
$$\lambda |d| \le 100.$$
Daher sind nur von Null verschiedene ganze Zahlen \(d\) mit \(|d|\le 100\) relevant, und für jedes primitive Dreieck gilt
$$1 \le \lambda \le \left\lfloor\frac{100}{|d|}\right\rfloor.$$
Der Fall \(d=0\) würde \(r^2=3v^2\) verlangen und ist für positive ganze Zahlen unmöglich. Deshalb läuft die Suche tatsächlich über \(d\in\{-100,\dots,-1,1,\dots,100\}\).
Für festes \(d\) müssen wir
$$r^2-3v^2=d,\qquad r>0,\quad v>0$$
lösen. Das ist eine Pell-artige Gleichung. Ihre positiven Lösungen zerfallen in endlich viele Orbits unter Multiplikation mit der Grundeinheit \(2+\sqrt{3}\). In Koordinaten lautet ein Vorwärtsschritt
$$r' = 2r+3v,\qquad v' = r+2v.$$
Löst \((r,v)\) die Gleichung, so löst auch \((r',v')\) dieselbe Gleichung. Die inverse Einheit \(2-\sqrt{3}\) liefert
$$r_- = 2r-3v,\qquad v_- = -r+2v,$$
und erhält ebenfalls die rechte Seite, solange beide Werte positiv bleiben. Wiederholt man diesen Rückwärtsschritt, bis Positivität gerade verloren ginge, erhält man einen reduzierten Repräsentanten des Orbits. Von je einem solchen Repräsentanten pro Orbit aus erzeugt das Vorwärtsiterieren alle positiven Lösungen dieses Orbits.
Ist eine Lösung \((r,v)\) bekannt, dann folgt
$$u=v+r,$$
$$a^\ast=u^2-v^2,\qquad b^\ast=2uv+v^2,\qquad c^\ast=u^2+uv+v^2.$$
Das primitive Dreieck liefert alle skalierten Kopien mit
$$1 \le \lambda \le \min\left(\left\lfloor\frac{100}{|d|}\right\rfloor,\left\lfloor\frac{N}{c^\ast}\right\rfloor\right).$$
Jeder solche Faktor \(\lambda\) ergibt nach dem Sortieren der beiden kürzeren Seiten ein zulässiges Dreieck. Da es Mehrfacherzeugungen geben kann, speichert die Implementierung die endgültigen geordneten Tripel in einer Menge und zählt jedes verschiedene Dreieck nur einmal.
Nehmen wir \(d=1\). Dann besitzt
$$r^2-3v^2=1$$
die positive Lösung \((r,v)=(2,1)\). Also ist \(u=v+r=3\), und damit
$$a^\ast=3^2-1^2=8,\qquad b^\ast=2\cdot 3\cdot 1+1^2=7,\qquad c^\ast=3^2+3\cdot 1+1^2=13.$$
Nach dem Sortieren erhalten wir \((7,8,13)\); der Abstand der beiden kürzeren Seiten ist tatsächlich \(1\). Für jede Schranke \(N\ge 13\) sind die erlaubten Skalierungen
$$1 \le \lambda \le \min\left(100,\left\lfloor\frac{N}{13}\right\rfloor\right).$$
Ein weiterer Vorwärtsschritt liefert
$$ (r',v')=(2\cdot 2+3\cdot 1,\;2+2\cdot 1)=(7,4).$$
Dann ist \(u=11\), und nach dem Sortieren entsteht das primitive Dreieck \((104,105,181)\). Wieder beträgt die Differenz der beiden kürzeren Seiten \(1\). Genau so erzeugt ein kleines \(d\) eine unendliche Familie, die durch \(c\le N\) auf endlich viele Mitglieder abgeschnitten wird.
Die C++-, Python- und Java-Implementierungen folgen demselben Aufbau. Sie durchlaufen alle vorzeichenbehafteten Differenzparameter \(d\) mit \(-100 \le d \le 100\) und \(d \ne 0\). Für jedes \(d\) wird zunächst die größte durch \(b-a \le 100\) erlaubte Skalierung \(\lfloor 100/|d| \rfloor\) berechnet.
Anschließend bestimmt die Implementierung reduzierte positive Lösungen der Pell-artigen Gleichung \(r^2-3v^2=d\). Diese reduzierten Repräsentanten werden zwischengespeichert, damit jeder Orbit nur einmal entdeckt wird. Von jedem Repräsentanten aus wird die Vorwärtsrekursion von \(2+\sqrt{3}\) wiederholt angewendet. Jedes neue Paar \((r,v)\) liefert genau ein primitives Dreieck, und der Orbit endet, sobald das zugehörige \(c^\ast\) bereits größer als \(N\) ist.
Für jedes primitive Dreieck werden die beiden kürzeren Seiten sortiert, und jeder zulässige Skalierungsfaktor
$$1 \le \lambda \le \min\left(\left\lfloor\frac{100}{|d|}\right\rfloor,\left\lfloor\frac{N}{c^\ast}\right\rfloor\right)$$
wird ausprobiert. Das entstehende geordnete Tripel wird in eine Menge eingefügt, was exakte Duplikatentfernung garantiert. Zwei nützliche Kontrollwerte dieses Verfahrens sind \(T(1000)=235\) und \(T(10^8)=1245\); danach wird dieselbe Methode auf \(N=10^{100}\) angewandt.
Die äußere Schleife über \(d\) hat konstante Größe, denn relevant sind nur \(200\) von Null verschiedene Werte. Entlang eines festen Pell-Orbits wachsen \(r\), \(v\) und damit auch \(c^\ast\) ungefähr mit dem Faktor \(2+\sqrt{3}\), sodass die Anzahl primitiver Dreiecke mit \(c^\ast \le N\) auf diesem Orbit \(O(\log N)\) beträgt. Pro primitivem Dreieck gibt es höchstens \(100\) mögliche Skalierungen, also ebenfalls nur einen konstanten Faktor.
Bezeichnet \(M\) die Anzahl der vor der Duplikatentfernung erzeugten Kandidaten, dann ist die Erzeugung im Wesentlichen linear in \(M\). Die Mengenverwaltung kostet \(O(M\log M)\) im Modell einer baumbasierten Menge oder erwartete nahezu lineare Zeit bei hashbasierten Mengen. Der Speicherbedarf ist \(O(M)\). Praktisch ist das Verfahren damit winzig gegenüber jeder direkten Suche über Seitenlängen.
Bir açısı \(120^\circ\) olan ve bu açıya karşılık gelen kenarı \(c\) olan tam sayı kenarlı üçgenler sayılıyor. Kenarlar \(a \le b \le c\) olacak şekilde sıralanıyor, ayrıca \(b-a \le 100\) ve \(c \le N\) şartları var. Hedef \(T(10^{100})\) olduğundan, kenarları doğrudan taramak imkansız; çözüm geçerli üçgen ailelerini cebirsel olarak üretip sadece farklı sıralı üçlüleri saymak zorunda.
Açı \(120^\circ\) olarak sabitlenince geometri problemi ikinci dereceden bir Diofant denklemi haline gelir. Tam sayı kenarlı \(120^\circ\) üçgenlerin standart parametreleştirmesi de “neredeyse ikizkenar” koşulunu küçük sağ taraflı bir Pell tipi denkleme indirger.
Kosinüs teoremine göre, \(120^\circ\) açı \(c\) kenarının karşısındaysa
$$c^2=a^2+b^2-2ab\cos 120^\circ=a^2+b^2+ab.$$
Dolayısıyla her uygun üçgen şu denklemin pozitif tam sayı çözümüdür:
$$c^2=a^2+b^2+ab,\qquad a \le b \le c.$$
Bu ikinci dereceden form Eisenstein tamsayılarının norm formudur; bu yüzden iki parametreli temiz bir açıklama vardır.
\(u>v>0\) tam sayıları için
$$a^\ast=u^2-v^2,\qquad b^\ast=2uv+v^2,\qquad c^\ast=u^2+uv+v^2$$
tanımlarını yapalım. Doğrudan açılım
$$\left(c^\ast\right)^2=\left(a^\ast\right)^2+\left(b^\ast\right)^2+a^\ast b^\ast$$
eşitliğini verir. Böylece \((a^\ast,b^\ast,c^\ast)\) ilkel bir tam sayı \(120^\circ\) üçgenidir; yalnız iki kısa kenar otomatik olarak sıralı değildir. İlkel olmayan her çözüm ise ölçekleme ile elde edilir:
$$ (a,b,c)=\lambda\bigl(\min(a^\ast,b^\ast),\max(a^\ast,b^\ast),c^\ast\bigr),\qquad \lambda \ge 1.$$
Böylece problem, ilkel üçgenleri üretip her biri için hangi \(\lambda\) değerlerinin geçerli kaldığını belirlemeye indirgenir.
Şunu yazalım:
$$r=u-v>0,\qquad u=v+r.$$
O zaman iki kısa kenarın farkı
$$b^\ast-a^\ast=2uv+v^2-(u^2-v^2)=3v^2-r^2$$
olur. Eşdeğer biçimde
$$r^2-3v^2=d,\qquad d=-(b^\ast-a^\ast).$$
Kısa kenarlar sıralandıktan sonra aralarındaki gerçek fark tam olarak
$$\bigl|\max(a^\ast,b^\ast)-\min(a^\ast,b^\ast)\bigr|=|d|$$
olur. \(\lambda\) ile ölçekleme bu farkı da \(\lambda\) katına çıkarır, dolayısıyla \(b-a \le 100\) koşulu
$$\lambda |d| \le 100$$
şekline dönüşür. Demek ki yalnızca \(|d|\le 100\) olan ve sıfırdan farklı tam sayılar önemlidir; her ilkel üçgen için de
$$1 \le \lambda \le \left\lfloor\frac{100}{|d|}\right\rfloor$$
olmalıdır. \(d=0\) durumu \(r^2=3v^2\) gerektirir ve pozitif tam sayılarda imkansızdır; bu yüzden arama gerçekten \(d\in\{-100,\dots,-1,1,\dots,100\}\) aralığındadır.
Sabit bir \(d\) için çözmemiz gereken denklem
$$r^2-3v^2=d,\qquad r>0,\quad v>0$$
olur. Bu bir Pell tipi denklemdir. Pozitif çözümler, temel birim \(2+\sqrt{3}\) ile çarpım altında sonlu sayıda yörüngeye ayrılır. Koordinatlarda bir ileri adım
$$r' = 2r+3v,\qquad v' = r+2v$$
şeklindedir. \((r,v)\) denklemi sağlıyorsa \((r',v')\) de sağlar. Ters birim \(2-\sqrt{3}\) ise
$$r_- = 2r-3v,\qquad v_- = -r+2v$$
formülünü verir ve her iki değer de pozitif kaldığı sürece aynı sağ tarafı korur. Bu geri adımı, pozitiflik bozulacak noktaya kadar tekrarlarsak yörüngenin indirgenmiş bir temsilcisini elde ederiz. Her yörüngeden bir indirgenmiş temsilci seçip ileri yönde yürümek, o yörüngedeki tüm pozitif çözümleri üretir.
Bir \((r,v)\) çözümü verildiğinde
$$u=v+r,$$
$$a^\ast=u^2-v^2,\qquad b^\ast=2uv+v^2,\qquad c^\ast=u^2+uv+v^2$$
elde edilir. Bu ilkel üçgenin katkısı,
$$1 \le \lambda \le \min\left(\left\lfloor\frac{100}{|d|}\right\rfloor,\left\lfloor\frac{N}{c^\ast}\right\rfloor\right)$$
koşulunu sağlayan tüm ölçeklenmiş kopyalardır. Kısa kenarlar sıralandıktan sonra her böyle \(\lambda\) bir geçerli üçgen verir. Aynı üçgen birden fazla biçimde yeniden üretilebildiği için, uygulama son sıralı üçlüleri bir kümede tutar ve her farklı üçgeni yalnızca bir kez sayar.
\(d=1\) alalım. O zaman
$$r^2-3v^2=1$$
denkleminin pozitif çözümü \((r,v)=(2,1)\)'dir. Buradan \(u=v+r=3\) olur ve
$$a^\ast=3^2-1^2=8,\qquad b^\ast=2\cdot 3\cdot 1+1^2=7,\qquad c^\ast=3^2+3\cdot 1+1^2=13$$
elde edilir. Kısa kenarları sıralayınca \((7,8,13)\) üçgeni çıkar; fark gerçekten \(1\)'dir. \(N\ge 13\) olduğu sürece geçerli ölçekler
$$1 \le \lambda \le \min\left(100,\left\lfloor\frac{N}{13}\right\rfloor\right)$$
şeklindedir. İleri özyinelemeyi bir kez uygularsak
$$ (r',v')=(2\cdot 2+3\cdot 1,\;2+2\cdot 1)=(7,4)$$
olur. Bu kez \(u=11\) gelir ve sıralandıktan sonra ilkel üçgen \((104,105,181)\) elde edilir. Burada da kısa kenar farkı yine \(1\)'dir. Bu örnek, sabit küçük bir \(d\) değerinin sonsuz bir aile ürettiğini, ancak \(c\le N\) sınırının bu aileyi sonlu hale getirdiğini gösterir.
C++, Python ve Java uygulamaları aynı iskeleti izler. Önce \(-100 \le d \le 100\) ve \(d \ne 0\) olan tüm işaretli fark parametreleri dolaşılır. Her \(d\) için, neredeyse ikizkenar koşulundan gelen en büyük ölçek sınırı \(\lfloor 100/|d| \rfloor\) önceden hesaplanır.
Ardından uygulama, \(r^2-3v^2=d\) Pell tipi denkleminin indirgenmiş pozitif çözümlerini bulur. Bu indirgenmiş temsilciler önbelleğe alınır; böylece her yörünge yalnızca bir kez keşfedilir. Her temsilciden başlayarak \(2+\sqrt{3}\) ile gelen ileri özyineleme tekrar tekrar uygulanır. Her yeni \((r,v)\) çifti bir ilkel üçgen üretir ve karşılık gelen \(c^\ast\) değeri \(N\)'yi aşar aşmaz o yörünge durdurulur.
Her ilkel üçgen için iki kısa kenar sıralanır ve
$$1 \le \lambda \le \min\left(\left\lfloor\frac{100}{|d|}\right\rfloor,\left\lfloor\frac{N}{c^\ast}\right\rfloor\right)$$
aralığındaki tüm geçerli ölçekler denenir. Ortaya çıkan sıralı üçlü kümeye eklenir; bu da tekrarları tam olarak siler. Bu yöntemin iki faydalı ara kontrolü \(T(1000)=235\) ve \(T(10^8)=1245\) değerleridir; sonra aynı mekanizma \(N=10^{100}\) için uygulanır.
\(d\) üzerindeki dış döngü sabit büyüklüktedir; yalnızca sıfır olmayan \(200\) değer önemlidir. Her sabit Pell yörüngesinde \(r\), \(v\) ve dolayısıyla \(c^\ast\) yaklaşık \(2+\sqrt{3}\) katsayısıyla büyür; bu yüzden \(c^\ast \le N\) şartını sağlayan ilkel üçgen sayısı yörünge başına \(O(\log N)\)'dir. Bir ilkel üçgen için denenebilecek ölçek sayısı da en fazla \(100\) olduğundan sabittir.
\(M\), tekrar silinmeden önce üretilen aday üçgen sayısı olsun. Aday üretimi esasen \(M\) ile lineerdir. Tekrar silme işlemi ağaç tabanlı küme modelinde \(O(M\log M)\), hash tabanlı kümelerde ise beklenen olarak lineere yakındır. Bellek kullanımı \(O(M)\)'dir. Pratikte bu maliyet, kenarlar üzerinde yapılacak herhangi bir doğrudan aramaya göre çok küçüktür.
Debemos contar los triángulos de lados enteros con un ángulo de \(120^\circ\) opuesto a \(c\), ordenados de modo que \(a \le b \le c\), con la restricción de casi isósceles \(b-a \le 100\) y el límite \(c \le N\). Como se busca \(T(10^{100})\), una búsqueda directa sobre longitudes es completamente inviable. La solución tiene que generar las familias válidas de forma algebraica y luego contar solo los triples ordenados distintos.
Una vez fijado el ángulo en \(120^\circ\), la geometría se convierte en una ecuación diofántica cuadrática. La parametrización estándar de los triángulos enteros de \(120^\circ\) transforma después la condición de “casi isósceles” en una ecuación de tipo Pell con segundo miembro muy pequeño.
Por la ley de cosenos, si el ángulo de \(120^\circ\) está opuesto a \(c\), entonces
$$c^2=a^2+b^2-2ab\cos 120^\circ=a^2+b^2+ab.$$
Así, todo triángulo válido corresponde a una solución entera positiva de
$$c^2=a^2+b^2+ab,\qquad a \le b \le c.$$
Esta forma cuadrática es la forma norma asociada a los enteros de Eisenstein, lo que explica por qué existe una descripción limpia con dos parámetros.
Para enteros \(u>v>0\), definimos
$$a^\ast=u^2-v^2,\qquad b^\ast=2uv+v^2,\qquad c^\ast=u^2+uv+v^2.$$
Al desarrollar directamente se obtiene
$$\left(c^\ast\right)^2=\left(a^\ast\right)^2+\left(b^\ast\right)^2+a^\ast b^\ast.$$
Por tanto, \((a^\ast,b^\ast,c^\ast)\) es un triángulo entero primitivo de \(120^\circ\), salvo que los dos lados cortos no quedan automáticamente ordenados. Toda solución no primitiva aparece por escalado:
$$ (a,b,c)=\lambda\bigl(\min(a^\ast,b^\ast),\max(a^\ast,b^\ast),c^\ast\bigr),\qquad \lambda \ge 1.$$
El problema de conteo queda reducido a generar triángulos primitivos y, después, decidir cuántos factores de escala \(\lambda\) siguen siendo válidos.
Escribimos
$$r=u-v>0,\qquad u=v+r.$$
Entonces la diferencia entre los dos lados cortos vale
$$b^\ast-a^\ast=2uv+v^2-(u^2-v^2)=3v^2-r^2.$$
Equivalente a eso es
$$r^2-3v^2=d,\qquad d=-(b^\ast-a^\ast).$$
Después de ordenar los lados cortos, su separación es exactamente
$$\bigl|\max(a^\ast,b^\ast)-\min(a^\ast,b^\ast)\bigr|=|d|.$$
Escalar por \(\lambda\) multiplica también esa diferencia por \(\lambda\), de modo que la restricción \(b-a \le 100\) se convierte en
$$\lambda |d| \le 100.$$
Por eso solo interesan enteros no nulos \(d\) con \(|d|\le 100\), y para cada triángulo primitivo se exige
$$1 \le \lambda \le \left\lfloor\frac{100}{|d|}\right\rfloor.$$
El caso \(d=0\) requeriría \(r^2=3v^2\), imposible en enteros positivos; en consecuencia, la búsqueda real recorre \(d\in\{-100,\dots,-1,1,\dots,100\}\).
Fijado \(d\), debemos resolver
$$r^2-3v^2=d,\qquad r>0,\quad v>0.$$
Esta es una ecuación de tipo Pell. Sus soluciones positivas se descomponen en un número finito de órbitas bajo multiplicación por la unidad fundamental \(2+\sqrt{3}\). En coordenadas, un paso hacia delante es
$$r' = 2r+3v,\qquad v' = r+2v.$$
Si \((r,v)\) resuelve la ecuación, también lo hace \((r',v')\). La unidad inversa \(2-\sqrt{3}\) da
$$r_- = 2r-3v,\qquad v_- = -r+2v,$$
y conserva el mismo segundo miembro siempre que ambos valores sigan siendo positivos. Repetir este paso inverso hasta que la positividad vaya a fallar produce un representante reducido de la órbita. Partiendo de un representante reducido por órbita e iterando hacia delante se generan todas las soluciones positivas de esa órbita.
Una vez conocida una solución \((r,v)\), recuperamos
$$u=v+r,$$
$$a^\ast=u^2-v^2,\qquad b^\ast=2uv+v^2,\qquad c^\ast=u^2+uv+v^2.$$
El triángulo primitivo aporta todas sus copias escaladas con
$$1 \le \lambda \le \min\left(\left\lfloor\frac{100}{|d|}\right\rfloor,\left\lfloor\frac{N}{c^\ast}\right\rfloor\right).$$
Cada uno de esos valores de \(\lambda\) da un triángulo admisible tras ordenar los lados cortos. Como puede haber generación repetida, la implementación guarda los triples ordenados finales en un conjunto y cuenta cada triángulo distinto solo una vez.
Tomemos \(d=1\). Entonces
$$r^2-3v^2=1$$
tiene la solución positiva \((r,v)=(2,1)\). De ahí sale \(u=v+r=3\), y por tanto
$$a^\ast=3^2-1^2=8,\qquad b^\ast=2\cdot 3\cdot 1+1^2=7,\qquad c^\ast=3^2+3\cdot 1+1^2=13.$$
Al ordenar los lados cortos obtenemos \((7,8,13)\), cuya diferencia corta es exactamente \(1\). Para cualquier cota \(N\ge 13\), las escalas válidas son
$$1 \le \lambda \le \min\left(100,\left\lfloor\frac{N}{13}\right\rfloor\right).$$
Aplicando una vez la recurrencia hacia delante, se obtiene
$$ (r',v')=(2\cdot 2+3\cdot 1,\;2+2\cdot 1)=(7,4).$$
Ahora \(u=11\), y el triángulo primitivo correspondiente, una vez ordenado, es \((104,105,181)\). De nuevo la diferencia entre los lados cortos es \(1\). Esto muestra cómo un valor pequeño fijo de \(d\) produce una familia infinita, truncada en la práctica por la condición \(c\le N\).
Las implementaciones en C++, Python y Java siguen la misma estrategia. Recorren todos los parámetros de diferencia con signo \(d\) tales que \(-100 \le d \le 100\) y \(d \ne 0\). Para cada \(d\), se precalcula la escala máxima permitida por la restricción de casi isósceles, \(\lfloor 100/|d| \rfloor\).
Después, la implementación encuentra soluciones positivas reducidas de la ecuación de tipo Pell \(r^2-3v^2=d\). Esos representantes reducidos se almacenan en caché para descubrir cada órbita una sola vez. Desde cada representante, se aplica repetidamente la recurrencia hacia delante asociada a \(2+\sqrt{3}\). Cada nuevo par \((r,v)\) produce un triángulo primitivo, y la exploración de esa órbita se detiene en cuanto el correspondiente \(c^\ast\) ya supera \(N\).
Para cada triángulo primitivo, se ordenan los dos lados cortos y se prueban todas las escalas admisibles
$$1 \le \lambda \le \min\left(\left\lfloor\frac{100}{|d|}\right\rfloor,\left\lfloor\frac{N}{c^\ast}\right\rfloor\right).$$
El triple ordenado resultante se inserta en un conjunto, garantizando una eliminación exacta de duplicados. Dos puntos de control útiles de este método son \(T(1000)=235\) y \(T(10^8)=1245\); después se aplica exactamente el mismo mecanismo a \(N=10^{100}\).
El bucle exterior sobre \(d\) tiene tamaño constante, ya que solo importan \(200\) valores no nulos. A lo largo de una órbita de Pell fija, \(r\), \(v\) y por tanto \(c^\ast\) crecen aproximadamente por el factor \(2+\sqrt{3}\), así que el número de triángulos primitivos con \(c^\ast \le N\) es \(O(\log N)\) en esa órbita. El número de factores de escala por triángulo primitivo es como máximo \(100\), otra constante.
Si \(M\) es el número de triángulos candidatos generados antes de eliminar duplicados, la generación es esencialmente lineal en \(M\). La deduplicación cuesta \(O(M\log M)\) en un modelo de conjunto basado en árboles, o tiempo esperado casi lineal con conjuntos hash. La memoria utilizada es \(O(M)\). En la práctica, esto es diminuto comparado con cualquier búsqueda directa sobre lados.
我们要统计这样一类整数边三角形：其中一个角为 \(120^\circ\)，它所对的边记为 \(c\)，并且边长按 \(a \le b \le c\) 排序，同时满足“近似等腰”条件 \(b-a \le 100\) 以及上界 \(c \le N\)。目标是求 \(T(10^{100})\)。由于这个 \(N\) 大得惊人，绝不可能直接枚举边长，所以解法必须从数论结构出发，先生成全部合法家族，再精确去重计数。
一旦把角固定为 \(120^\circ\)，几何条件就会变成一个二次丢番图方程。而整数 \(120^\circ\) 三角形的标准参数化，又会把“近似等腰”的限制继续转化成右端很小的 Pell 型方程。整个算法正是围绕这个转化展开的。
由余弦定理可知，如果 \(120^\circ\) 的角对着边 \(c\)，那么
$$c^2=a^2+b^2-2ab\cos 120^\circ=a^2+b^2+ab.$$
因此，所有满足题意的三角形都对应于正整数解
$$c^2=a^2+b^2+ab,\qquad a \le b \le c.$$
这个二次型正好是 Eisenstein 整数中常见的范数形式，所以它拥有非常整洁的双参数描述。
取整数 \(u>v>0\)，定义
$$a^\ast=u^2-v^2,\qquad b^\ast=2uv+v^2,\qquad c^\ast=u^2+uv+v^2.$$
直接展开就能验证
$$\left(c^\ast\right)^2=\left(a^\ast\right)^2+\left(b^\ast\right)^2+a^\ast b^\ast.$$
所以 \((a^\ast,b^\ast,c^\ast)\) 给出了一个原始的整数 \(120^\circ\) 三角形，只是两个较短边不一定已经排好序。所有非原始解都可以通过整体缩放得到：
$$ (a,b,c)=\lambda\bigl(\min(a^\ast,b^\ast),\max(a^\ast,b^\ast),c^\ast\bigr),\qquad \lambda \ge 1.$$
因此，原问题就转化成两步：先生成原始三角形，再判断每个原始三角形允许多少个缩放因子 \(\lambda\)。
记
$$r=u-v>0,\qquad u=v+r.$$
那么两个较短边的差为
$$b^\ast-a^\ast=2uv+v^2-(u^2-v^2)=3v^2-r^2.$$
把它改写一下，就得到
$$r^2-3v^2=d,\qquad d=-(b^\ast-a^\ast).$$
当我们把两个较短边重新排序以后，它们的真实差值正好是
$$\bigl|\max(a^\ast,b^\ast)-\min(a^\ast,b^\ast)\bigr|=|d|.$$
如果再整体缩放 \(\lambda\) 倍，这个差值也会被放大为 \(\lambda |d|\)。于是题目的限制 \(b-a \le 100\) 等价于
$$\lambda |d| \le 100.$$
这说明只有满足 \(|d|\le 100\) 的非零整数才可能产生贡献，而且对固定原始三角形来说，缩放因子必须满足
$$1 \le \lambda \le \left\lfloor\frac{100}{|d|}\right\rfloor.$$
特别地，\(d=0\) 会要求 \(r^2=3v^2\)，这在正整数中不可能发生，所以搜索范围确实就是 \(d\in\{-100,\dots,-1,1,\dots,100\}\)。
固定一个 \(d\) 后，我们需要求解
$$r^2-3v^2=d,\qquad r>0,\quad v>0.$$
这是标准的 Pell 型方程。它的正整数解会分成有限多个轨道，每个轨道都由基本单位 \(2+\sqrt{3}\) 的反复作用生成。写成坐标递推，向前一步是
$$r' = 2r+3v,\qquad v' = r+2v.$$
如果 \((r,v)\) 满足 \(r^2-3v^2=d\)，那么 \((r',v')\) 也满足同一个方程。反过来，单位 \(2-\sqrt{3}\) 给出回退变换
$$r_- = 2r-3v,\qquad v_- = -r+2v,$$
只要这两个新值仍然为正，它就保持同一个右端值。不断做这个回退，直到再退一步就会失去正性，就能得到该轨道的一个“最小”代表。然后从每个轨道代表出发一直向前推，就能完整生成这一轨道上的全部正解。
一旦得到某个解 \((r,v)\)，就能恢复
$$u=v+r,$$
$$a^\ast=u^2-v^2,\qquad b^\ast=2uv+v^2,\qquad c^\ast=u^2+uv+v^2.$$
对应的原始三角形会贡献所有满足
$$1 \le \lambda \le \min\left(\left\lfloor\frac{100}{|d|}\right\rfloor,\left\lfloor\frac{N}{c^\ast}\right\rfloor\right)$$
的缩放副本。把两条较短边排序以后，每一个这样的 \(\lambda\) 都对应一个合法三角形。由于同一个三角形有可能被重复生成，程序最终把排序后的整组三边放入集合中，只保留不同的三元组。
取 \(d=1\)。此时方程
$$r^2-3v^2=1$$
有正解 \((r,v)=(2,1)\)。因此 \(u=v+r=3\)，于是
$$a^\ast=3^2-1^2=8,\qquad b^\ast=2\cdot 3\cdot 1+1^2=7,\qquad c^\ast=3^2+3\cdot 1+1^2=13.$$
把较短边排序之后得到三角形 \((7,8,13)\)，它们的差确实是 \(1\)。如果 \(N\ge 13\)，那么可行的缩放因子就是
$$1 \le \lambda \le \min\left(100,\left\lfloor\frac{N}{13}\right\rfloor\right).$$
再向前做一次 Pell 递推：
$$ (r',v')=(2\cdot 2+3\cdot 1,\;2+2\cdot 1)=(7,4).$$
这时 \(u=11\)，对应的原始三角形排序后为 \((104,105,181)\)，两个短边的差仍然是 \(1\)。这个例子非常直观地说明：一个固定的小 \(d\) 会产生一整条无限轨道，而 \(c\le N\) 只是把这条无限轨道截成有限段。
C++、Python 和 Java 版本都遵循同一套流程。它们先枚举所有满足 \(-100 \le d \le 100\) 且 \(d \ne 0\) 的带符号差值参数。对每个 \(d\)，先计算由“近似等腰”限制带来的最大缩放因子 \(\lfloor 100/|d| \rfloor\)。
接着，程序寻找 Pell 型方程 \(r^2-3v^2=d\) 的约化正解，并把这些约化轨道代表缓存起来，保证每条轨道只被发现一次。随后从每个代表出发，不断应用由 \(2+\sqrt{3}\) 诱导的向前递推。每个新的 \((r,v)\) 都产生一个原始三角形，一旦相应的 \(c^\ast\) 已经超过 \(N\)，这一轨道就停止继续扩展。
对于每个原始三角形，程序都会先把两条较短边排序，再尝试所有满足
$$1 \le \lambda \le \min\left(\left\lfloor\frac{100}{|d|}\right\rfloor,\left\lfloor\frac{N}{c^\ast}\right\rfloor\right)$$
的缩放因子。得到的有序三元组会放入集合中，从而完成精确去重。这个方法的两个实用校验点是 \(T(1000)=235\) 和 \(T(10^8)=1245\)，确认无误后再用同样的机制处理最终的 \(N=10^{100}\)。
外层枚举 \(d\) 的循环大小是常数，因为真正相关的只有 \(200\) 个非零值。对任意固定的 Pell 轨道来说，\(r\)、\(v\) 以及 \(c^\ast\) 大致都会按 \(2+\sqrt{3}\) 的倍率增长，所以满足 \(c^\ast \le N\) 的原始三角形数量沿该轨道只有 \(O(\log N)\)。每个原始三角形最多尝试 \(100\) 个缩放因子，这同样只是常数倍。
如果记去重之前生成的候选三角形总数为 \(M\)，那么候选生成基本上是关于 \(M\) 的线性过程。集合去重在树结构模型下需要 \(O(M\log M)\)，在哈希集合下则是期望近线性的时间。空间复杂度为 \(O(M)\)。与任何直接枚举边长的办法相比，这个代价都小得多。
Нужно посчитать целочисленные треугольники с углом \(120^\circ\), лежащим напротив стороны \(c\), где стороны упорядочены как \(a \le b \le c\), выполнено условие почти равнобедренности \(b-a \le 100\), а также ограничение \(c \le N\). Требуется значение \(T(10^{100})\). Прямой перебор длин сторон здесь невозможен, поэтому решение должно порождать все допустимые семейства алгебраически и затем точно удалять дубликаты.
После фиксации угла \(120^\circ\) геометрическая задача превращается в квадратичное диофантово уравнение. Стандартная параметризация целочисленных \(120^\circ\)-треугольников затем переводит условие «почти равнобедренности» в уравнение типа Пелля с очень малой правой частью.
По теореме косинусов, если угол \(120^\circ\) лежит напротив стороны \(c\), то
$$c^2=a^2+b^2-2ab\cos 120^\circ=a^2+b^2+ab.$$
Следовательно, каждый допустимый треугольник соответствует положительному целочисленному решению
$$c^2=a^2+b^2+ab,\qquad a \le b \le c.$$
Эта квадратичная форма является нормой в кольце эйзенштейновых целых, поэтому для нее существует естественная двухпараметрическая запись.
Для целых чисел \(u>v>0\) положим
$$a^\ast=u^2-v^2,\qquad b^\ast=2uv+v^2,\qquad c^\ast=u^2+uv+v^2.$$
Непосредственная проверка дает
$$\left(c^\ast\right)^2=\left(a^\ast\right)^2+\left(b^\ast\right)^2+a^\ast b^\ast.$$
Значит, \((a^\ast,b^\ast,c^\ast)\) задает примитивный целочисленный \(120^\circ\)-треугольник, хотя две короткие стороны еще не обязательно упорядочены. Любое непримитивное решение получается масштабированием:
$$ (a,b,c)=\lambda\bigl(\min(a^\ast,b^\ast),\max(a^\ast,b^\ast),c^\ast\bigr),\qquad \lambda \ge 1.$$
Тем самым задача сводится к генерации примитивных треугольников и к подсчету допустимых множителей \(\lambda\) для каждого из них.
Введем
$$r=u-v>0,\qquad u=v+r.$$
Тогда разность двух коротких сторон равна
$$b^\ast-a^\ast=2uv+v^2-(u^2-v^2)=3v^2-r^2.$$
То же самое можно записать как
$$r^2-3v^2=d,\qquad d=-(b^\ast-a^\ast).$$
После упорядочивания коротких сторон их зазор точно равен
$$\bigl|\max(a^\ast,b^\ast)-\min(a^\ast,b^\ast)\bigr|=|d|.$$
Масштабирование на \(\lambda\) умножает и этот зазор на \(\lambda\), поэтому условие \(b-a \le 100\) становится
$$\lambda |d| \le 100.$$
Следовательно, интерес представляют только ненулевые целые \(d\) с \(|d|\le 100\), а для каждого примитивного треугольника возможны лишь масштабы
$$1 \le \lambda \le \left\lfloor\frac{100}{|d|}\right\rfloor.$$
Случай \(d=0\) потребовал бы \(r^2=3v^2\), что невозможно в положительных целых числах. Поэтому реальный перебор идет по \(d\in\{-100,\dots,-1,1,\dots,100\}\).
Для фиксированного \(d\) требуется решить
$$r^2-3v^2=d,\qquad r>0,\quad v>0.$$
Это уравнение типа Пелля. Его положительные решения разбиваются на конечное число орбит относительно умножения на фундаментальную единицу \(2+\sqrt{3}\). В координатной форме один шаг вперед задается так:
$$r' = 2r+3v,\qquad v' = r+2v.$$
Если \((r,v)\) удовлетворяет уравнению, то и \((r',v')\) удовлетворяет ему. Обратная единица \(2-\sqrt{3}\) дает преобразование
$$r_- = 2r-3v,\qquad v_- = -r+2v,$$
которое сохраняет ту же правую часть, пока оба новых значения положительны. Если повторять этот обратный шаг до тех пор, пока следующий шаг уже нарушил бы положительность, мы получим приведенного представителя орбиты. А начиная с одного приведенного представителя на орбиту и итерируя вперед, можно восстановить все положительные решения этой орбиты.
Когда найдено решение \((r,v)\), мы восстанавливаем
$$u=v+r,$$
$$a^\ast=u^2-v^2,\qquad b^\ast=2uv+v^2,\qquad c^\ast=u^2+uv+v^2.$$
Такой примитивный треугольник дает все масштабированные копии, для которых
$$1 \le \lambda \le \min\left(\left\lfloor\frac{100}{|d|}\right\rfloor,\left\lfloor\frac{N}{c^\ast}\right\rfloor\right).$$
После сортировки двух коротких сторон каждый такой \(\lambda\) дает один допустимый треугольник. Поскольку одни и те же тройки могут возникать повторно, реализация помещает итоговые упорядоченные тройки в множество и считает каждый различный треугольник только один раз.
Возьмем \(d=1\). Тогда уравнение
$$r^2-3v^2=1$$
имеет положительное решение \((r,v)=(2,1)\). Значит, \(u=v+r=3\), и потому
$$a^\ast=3^2-1^2=8,\qquad b^\ast=2\cdot 3\cdot 1+1^2=7,\qquad c^\ast=3^2+3\cdot 1+1^2=13.$$
После сортировки коротких сторон получаем \((7,8,13)\); разность действительно равна \(1\). Для любого \(N\ge 13\) допустимые масштабы задаются неравенством
$$1 \le \lambda \le \min\left(100,\left\lfloor\frac{N}{13}\right\rfloor\right).$$
Если применить прямую рекурсию один раз, получится
$$ (r',v')=(2\cdot 2+3\cdot 1,\;2+2\cdot 1)=(7,4).$$
Теперь \(u=11\), и соответствующий примитивный треугольник после сортировки равен \((104,105,181)\). Разность коротких сторон снова равна \(1\). Это наглядно показывает, как одно маленькое значение \(d\) порождает бесконечное семейство, а условие \(c\le N\) лишь обрезает его до конечного числа элементов.
Реализации на C++, Python и Java используют один и тот же план. Сначала перебираются все знаковые параметры разности \(d\), где \(-100 \le d \le 100\) и \(d \ne 0\). Для каждого \(d\) заранее вычисляется максимальный масштаб, разрешенный условием почти равнобедренности, то есть \(\lfloor 100/|d| \rfloor\).
Затем реализация находит приведенные положительные решения уравнения типа Пелля \(r^2-3v^2=d\). Эти приведенные представители кэшируются, чтобы каждая орбита обнаруживалась только один раз. От каждого представителя многократно применяется прямая рекурсия, соответствующая умножению на \(2+\sqrt{3}\). Каждая новая пара \((r,v)\) задает один примитивный треугольник, и обход орбиты прекращается, как только соответствующее \(c^\ast\) становится больше \(N\).
Для каждого примитивного треугольника две короткие стороны сортируются, после чего перебираются все допустимые масштабы
$$1 \le \lambda \le \min\left(\left\lfloor\frac{100}{|d|}\right\rfloor,\left\lfloor\frac{N}{c^\ast}\right\rfloor\right).$$
Полученная упорядоченная тройка добавляется в множество, что обеспечивает точное удаление повторов. Два полезных контрольных значения для этого метода: \(T(1000)=235\) и \(T(10^8)=1245\); после их совпадения та же схема применяется к \(N=10^{100}\).
Внешний цикл по \(d\) имеет постоянный размер, поскольку релевантны только \(200\) ненулевых значений. Вдоль любой фиксированной орбиты Пелля величины \(r\), \(v\) и, следовательно, \(c^\ast\) растут примерно с коэффициентом \(2+\sqrt{3}\), поэтому число примитивных треугольников с \(c^\ast \le N\) на одной орбите равно \(O(\log N)\). Число масштабов на один примитивный треугольник не превосходит \(100\), то есть тоже является константой.
Если через \(M\) обозначить число кандидатных треугольников до удаления повторов, то их генерация по существу линейна по \(M\). Удаление повторов требует \(O(M\log M)\) в модели древовидного множества или ожидаемого почти линейного времени в хеш-множествах. Память составляет \(O(M)\). На практике этот метод несравнимо меньше любой прямой проверки сторон.
نريد عدّ المثلثات ذات الأضلاع الصحيحة التي تحتوي على زاوية مقدارها \(120^\circ\) وتقابلها الضلع \(c\)، مع ترتيب الأضلاع بحيث \(a \le b \le c\)، وفرض الشرط القريب من التساوي \(b-a \le 100\)، وكذلك القيد \(c \le N\). المطلوب هو حساب \(T(10^{100})\). وبما أن هذا الحدّ هائل جدًا، فلا يمكن فحص الأطوال مباشرة، ولذلك يجب توليد جميع العائلات الصحيحة جبريًا ثم إزالة التكرارات بدقة.
عند تثبيت الزاوية على \(120^\circ\)، يتحول الوصف الهندسي إلى معادلة ديوفانتية تربيعية. ثم إن البارامتَرة القياسية للمثلثات الصحيحة ذات زاوية \(120^\circ\) تحوّل شرط «قريب من متساوي الساقين» إلى معادلة من نمط بيل ذات طرف أيمن صغير جدًا.
من قانون جيب التمام، إذا كانت الزاوية \(120^\circ\) تقابل الضلع \(c\)، فإن
$$c^2=a^2+b^2-2ab\cos 120^\circ=a^2+b^2+ab.$$
إذن كل مثلث صالح يقابل حلاً صحيحًا موجبًا للمعادلة
$$c^2=a^2+b^2+ab,\qquad a \le b \le c.$$
وهذه الصورة التربيعية هي صورة معيار مرتبطة بأعداد أيزنشتاين، ولهذا تظهر بارامتَرة نظيفة تعتمد على متغيرين.
لأعداد صحيحة \(u>v>0\)، نعرّف
$$a^\ast=u^2-v^2,\qquad b^\ast=2uv+v^2,\qquad c^\ast=u^2+uv+v^2.$$
وبالتوسيع المباشر نجد أن
$$\left(c^\ast\right)^2=\left(a^\ast\right)^2+\left(b^\ast\right)^2+a^\ast b^\ast.$$
إذن الثلاثية \((a^\ast,b^\ast,c^\ast)\) تعطي مثلثًا صحيحًا بدائيًا بزاوية \(120^\circ\)، مع ملاحظة أن الضلعين الأقصرين قد لا يكونان مرتبين بعد. وكل حل غير بدائي ينتج عن التوسيع بعامل قياس:
$$ (a,b,c)=\lambda\bigl(\min(a^\ast,b^\ast),\max(a^\ast,b^\ast),c^\ast\bigr),\qquad \lambda \ge 1.$$
وبهذا تنحصر المسألة في توليد المثلثات البدائية، ثم تحديد عدد عوامل القياس \(\lambda\) المسموح بها لكل واحد منها.
لنكتب
$$r=u-v>0,\qquad u=v+r.$$
عندها يصبح فرق الضلعين الأقصرين
$$b^\ast-a^\ast=2uv+v^2-(u^2-v^2)=3v^2-r^2.$$
وبصورة مكافئة نحصل على
$$r^2-3v^2=d,\qquad d=-(b^\ast-a^\ast).$$
بعد ترتيب الضلعين الأقصرين، يكون الفرق الحقيقي بينهما مساويًا تمامًا لـ
$$\bigl|\max(a^\ast,b^\ast)-\min(a^\ast,b^\ast)\bigr|=|d|.$$
وعند التوسيع بالعامل \(\lambda\) يتضاعف هذا الفرق إلى \(\lambda|d|\)، لذلك يتحول الشرط \(b-a \le 100\) إلى
$$\lambda |d| \le 100.$$
ومن ثم لا تهم إلا القيم الصحيحة غير الصفرية \(d\) التي تحقق \(|d|\le 100\)، ولكل مثلث بدائي يجب أن يكون
$$1 \le \lambda \le \left\lfloor\frac{100}{|d|}\right\rfloor.$$
أما الحالة \(d=0\) فكانت ستتطلب \(r^2=3v^2\)، وهذا مستحيل في الأعداد الصحيحة الموجبة، لذلك يكون نطاق البحث الفعلي هو \(d\in\{-100,\dots,-1,1,\dots,100\}\).
بعد تثبيت \(d\)، نحتاج إلى حل
$$r^2-3v^2=d,\qquad r>0,\quad v>0.$$
هذه معادلة من نمط بيل. حلولها الموجبة تنقسم إلى عدد منتهٍ من المدارات تحت تأثير الوحدة الأساسية \(2+\sqrt{3}\). وبصيغة إحداثية يكون الانتقال الأمامي
$$r' = 2r+3v,\qquad v' = r+2v.$$
إذا كانت \((r,v)\) تحقق المعادلة، فإن \((r',v')\) يحققها أيضًا. أما الوحدة العكسية \(2-\sqrt{3}\) فتعطي التحويل
$$r_- = 2r-3v,\qquad v_- = -r+2v,$$
وهو يحافظ على الطرف الأيمن نفسه ما دام القيمان الجديدتان موجبتين. وإذا كررنا هذه الخطوة الخلفية حتى تصبح الخطوة التالية غير موجبة، نحصل على ممثل مختزل لذلك المدار. ثم إن الانطلاق من ممثل مختزل واحد لكل مدار، والسير للأمام، يولّد جميع الحلول الموجبة في ذلك المدار.
عندما نعرف حلًا \((r,v)\)، نسترجع
$$u=v+r,$$
$$a^\ast=u^2-v^2,\qquad b^\ast=2uv+v^2,\qquad c^\ast=u^2+uv+v^2.$$
ويساهم هذا المثلث البدائي بجميع نسخه الموسعة التي تحقق
$$1 \le \lambda \le \min\left(\left\lfloor\frac{100}{|d|}\right\rfloor,\left\lfloor\frac{N}{c^\ast}\right\rfloor\right).$$
بعد ترتيب الضلعين الأقصرين، يعطي كل \(\lambda\) من هذه القيم مثلثًا صالحًا. ولأن التوليد قد يكرر المثلث نفسه أكثر من مرة، تحتفظ الخوارزمية بالثلاثيات المرتبة النهائية داخل مجموعة، ثم تعدّ كل مثلث مختلف مرة واحدة فقط.
خذ \(d=1\). عندها تملك المعادلة
$$r^2-3v^2=1$$
الحل الموجب \((r,v)=(2,1)\). ومن ثم يكون \(u=v+r=3\)، فنحصل على
$$a^\ast=3^2-1^2=8,\qquad b^\ast=2\cdot 3\cdot 1+1^2=7,\qquad c^\ast=3^2+3\cdot 1+1^2=13.$$
بعد ترتيب الضلعين الأقصرين نحصل على المثلث \((7,8,13)\)، وفرق الضلعين الأقصرين فيه يساوي فعلًا \(1\). إذا كان \(N\ge 13\)، فإن عوامل القياس المسموح بها هي
$$1 \le \lambda \le \min\left(100,\left\lfloor\frac{N}{13}\right\rfloor\right).$$
وبتطبيق علاقة التكرار الأمامية مرة واحدة نحصل على
$$ (r',v')=(2\cdot 2+3\cdot 1,\;2+2\cdot 1)=(7,4).$$
وعندئذ يصبح \(u=11\)، ويكون المثلث البدائي الموافق بعد الترتيب هو \((104,105,181)\). ويظل فرق الضلعين الأقصرين مساويًا لـ \(1\). يوضح هذا المثال أن قيمة صغيرة ثابتة من \(d\) تولّد عائلة لا نهائية، لكن الشرط \(c\le N\) يقتطع منها جزءًا منتهيًا فقط.
تتبع تطبيقات C++ وPython وJava الخطة نفسها. فهي تمر على جميع قيم فرق الإشارة \(d\) بحيث \(-100 \le d \le 100\) و\(d \ne 0\). ولكل قيمة \(d\) تُحسب مسبقًا أكبر قيمة مسموحة لعامل القياس من شرط القرب من التساوي، أي \(\lfloor 100/|d| \rfloor\).
بعد ذلك تبحث الشيفرة عن الحلول الموجبة المختزلة للمعادلة من نمط بيل \(r^2-3v^2=d\). وتُخزَّن هذه الممثلّات المختزلة حتى لا يُكتشف المدار نفسه إلا مرة واحدة. ومن كل ممثل يُطبَّق التكرار الأمامي المرتبط بـ \(2+\sqrt{3}\) مرارًا. كل زوج جديد \((r,v)\) ينتج مثلثًا بدائيًا واحدًا، ويتوقف السير في المدار عندما تصبح القيمة الموافقة لـ \(c^\ast\) أكبر من \(N\).
وبالنسبة إلى كل مثلث بدائي، تُرتَّب أولًا الضلعان الأقصران، ثم تُجرَّب جميع عوامل القياس التي تحقق
$$1 \le \lambda \le \min\left(\left\lfloor\frac{100}{|d|}\right\rfloor,\left\lfloor\frac{N}{c^\ast}\right\rfloor\right).$$
تُدرج الثلاثية المرتبة الناتجة في مجموعة، وبذلك تتم إزالة التكرارات بدقة. ومن نقاط التحقق المفيدة لهذه الطريقة أن القيمتين \(T(1000)=235\) و\(T(10^8)=1245\) تظهران بشكل صحيح قبل الانتقال إلى الحساب النهائي عند \(N=10^{100}\).
الحلقة الخارجية على \(d\) ذات حجم ثابت، لأن القيم المهمة ليست إلا \(200\) قيمة غير صفرية. وعلى أي مدار ثابت من مدارات بيل تنمو \(r\) و\(v\) وبالتالي \(c^\ast\) تقريبًا بعامل \(2+\sqrt{3}\)، لذا فإن عدد المثلثات البدائية التي تحقق \(c^\ast \le N\) على ذلك المدار هو \(O(\log N)\). كما أن عدد عوامل القياس لكل مثلث بدائي لا يتجاوز \(100\)، وهو ثابت أيضًا.
إذا رمزنا بعدد المثلثات المرشحة قبل إزالة التكرار بالرمز \(M\)، فإن توليدها يكون عمليًا خطيًا في \(M\). أما إزالة التكرار فتكلّف \(O(M\log M)\) في نموذج المجموعة الشجرية، أو زمنًا متوقعًا شبه خطي عند استخدام مجموعات التجزئة. واستهلاك الذاكرة هو \(O(M)\). عمليًا، تظل هذه الكلفة صغيرة جدًا مقارنة بأي بحث مباشر في فضاء أطوال الأضلاع.