For a positive integer \(k\), the admissible numbers are the reduced proper fractions
$$S_k=\left\{\frac{a}{b}:0<a<b\le k,\ \gcd(a,b)=1\right\}.$$
Problem 180 fixes \(k=35\) and asks for all triples \((x,y,z)\in S_k^3\) for which the problem's function \(f_n(x,y,z)\) vanishes for at least one integer \(n\). For every such triple we form \(s=x+y+z\), keep only distinct rational values of \(s\), add them all together, reduce the total to lowest terms \(u/v\), and report \(u+v\).
The direct interpretation suggests searching all triples and all integers \(n\). The implementations do something much sharper: they factor the defining expression, prove that only four exponents can matter, and then scan pairs \((x,y)\) instead of triples \((x,y,z)\).
The whole solution rests on one algebraic simplification. Once the original zero-condition is rewritten correctly, the search space collapses from an open-ended three-variable problem to four explicit formulas for \(z\).
Every element of \(S_k\) is a positive rational smaller than 1, already stored in lowest terms. For each denominator \(b\), exactly \(\varphi(b)\) numerators are coprime to \(b\), so
$$|S_k|=\sum_{b=2}^{k}\varphi(b).$$
At the target order \(k=35\), this gives \(383\) admissible fractions. A naive triple search would therefore examine \(383^3\) candidates before even considering different exponents, so the algebraic reduction is the decisive step.
The implementations encode the original function as
$$\begin{aligned} f_n(x,y,z)={}&x^{n+1}+y^{n+1}-z^{n+1}\\ &+(xy+yz+zx)(x^{n-1}+y^{n-1}-z^{n-1})\\ &-xyz(x^{n-2}+y^{n-2}-z^{n-2}). \end{aligned}$$
If the second and third lines are expanded, the mixed terms \(yz\,x^{n-1}\), \(xz\,y^{n-1}\), and \(xy\,z^{n-1}\) cancel, and everything that remains factors cleanly:
$$f_n(x,y,z)=(x+y+z)(x^n+y^n-z^n).$$
Because \(x\), \(y\), and \(z\) are positive rationals, we always have \(x+y+z>0\). Therefore
$$f_n(x,y,z)=0 \quad\Longleftrightarrow\quad x^n+y^n=z^n.$$
This is the key invariant behind all three implementations.
If \(n=0\), the reduced equation becomes \(1+1=1\), which is impossible. If \(n>2\), any positive rational solution of \(x^n+y^n=z^n\) can be cleared of denominators to produce a positive integer solution, contradicting Fermat's Last Theorem. If \(n<-2\), write \(m=-n>2\); then
$$x^n+y^n=z^n \quad\Longleftrightarrow\quad \frac{1}{x^m}+\frac{1}{y^m}=\frac{1}{z^m},$$
which is the same kind of forbidden equation after replacing \(x,y,z\) by their reciprocals.
So the only exponents that can possibly contribute are
$$n\in\{-2,-1,1,2\}.$$
The infinite search over all integers has collapsed to four explicit cases.
Once \(x\) and \(y\) are fixed, each admissible exponent gives a concrete formula:
$$n=1:\quad z=x+y,$$
$$n=-1:\quad z=\frac{xy}{x+y},$$
$$n=2:\quad z=\sqrt{x^2+y^2},$$
$$n=-2:\quad z=\frac{1}{\sqrt{1/x^2+1/y^2}}=\frac{xy}{\sqrt{x^2+y^2}}.$$
This is why the optimized solver loops over ordered pairs \((x,y)\) rather than triples. For the square-root branches, the implementations compute the reduced fraction for \(z^2\) and accept it only when both numerator and denominator are perfect squares. After reduction, a membership test against \(S_k\) simultaneously checks that \(0<z<1\) and that the reduced denominator is at most \(k\).
The arithmetic is easiest to see on small examples. In the \(n=-1\) branch, taking \(x=\tfrac12\) and \(y=\tfrac13\) gives
$$z=\frac{xy}{x+y}=\frac{\tfrac12\cdot\tfrac13}{\tfrac12+\tfrac13}=\frac{1/6}{5/6}=\frac15,$$
so \(s=\tfrac12+\tfrac13+\tfrac15=\tfrac{31}{30}\). In the \(n=2\) branch,
$$\left(\frac{3}{10}\right)^2+\left(\frac{2}{5}\right)^2=\frac{9}{100}+\frac{16}{100}=\frac{25}{100}=\left(\frac12\right)^2,$$
so \((x,y,z)=\left(\tfrac{3}{10},\tfrac25,\tfrac12\right)\) is valid. For \(n=-2\), choosing \(x=\tfrac13\) and \(y=\tfrac14\) gives
$$\frac{1}{x^2}+\frac{1}{y^2}=9+16=25=\frac{1}{(1/5)^2},$$
hence \(z=\tfrac15\).
Different triples, and even different exponents, can lead to the same final value \(s=x+y+z\). The set of sums is therefore deduplicated at the rational-number level, not at the triple level.
The C++, Python, and Java implementations first generate every reduced fraction in \(S_{35}\). These fractions are also inserted into a hash-based membership structure so that a candidate \(z\) can be accepted or rejected in constant expected time.
The main loop runs through every ordered pair \((x,y)\in S_k^2\). For each pair, the implementation constructs the four candidates listed above. All arithmetic is exact: the Python version relies on built-in rational arithmetic, while the C++ and Java versions keep reduced numerator-denominator pairs and normalize after each addition, multiplication, division, or reciprocal. The \(n=\pm2\) branches use integer square-root tests on the reduced numerator and denominator to detect whether the square root stays rational.
If a candidate \(z\) belongs to \(S_k\), the implementation forms \(s=x+y+z\) and inserts that reduced fraction into a set of distinct sums. The scan does not try to avoid the symmetry between \((x,y)\) and \((y,x)\); it simply allows duplicates to arise and lets the set remove them automatically.
After the pair scan finishes, the distinct \(s\)-values are added exactly and reduced to a single fraction \(u/v\). The required output is then \(u+v\). The C++ implementation additionally contains small-order validation checkpoints: it compares the factored equation with the original definition, checks the optimized pair scan against brute-force triple enumeration on small \(k\), and verifies consistency between single-threaded and multithreaded execution.
Let
$$M=|S_k|=\sum_{b=2}^{k}\varphi(b).$$
Building the admissible fraction list and the membership set costs \(O(M)\). The main solver then examines every ordered pair \((x,y)\), so the dominant work is \(O(M^2)\). Each pair performs four candidate constructions, a constant number of gcd reductions, a few hash lookups, and at most two perfect-square checks.
The memory usage is \(O(M+U)\), where \(U\) is the number of distinct sums retained. For the target \(k=35\), \(M=383\), so the optimized search examines only \(383^2=146{,}689\) ordered pairs instead of \(383^3\) triples. The brute-force \(O(M^3)\) method appears only in the C++ validation checkpoints for tiny orders.
Für eine positive ganze Zahl \(k\) besteht die zulässige Menge aus den vollständig gekürzten echten Brüchen
$$S_k=\left\{\frac{a}{b}:0<a<b\le k,\ \gcd(a,b)=1\right\}.$$
In Problem 180 ist \(k=35\). Gesucht sind alle Tripel \((x,y,z)\in S_k^3\), für die die im Problem definierte Funktion \(f_n(x,y,z)\) für mindestens ein ganzzahliges \(n\) verschwindet. Zu jedem gültigen Tripel bildet man \(s=x+y+z\), behält nur verschiedene rationale Werte von \(s\), summiert sie exakt, kürzt das Ergebnis zu \(u/v\) und gibt schließlich \(u+v\) aus.
Eine direkte Suche über alle Tripel und alle möglichen Exponenten wäre unnötig groß. Die Implementierungen nutzen stattdessen eine Faktorisierung von \(f_n\), mit der sich die Zahl der relevanten Exponenten auf vier reduziert und die Suche auf Paare \((x,y)\) zurückführen lässt.
Der entscheidende Schritt ist rein algebraisch: Die scheinbar komplizierte Nullbedingung zerfällt in einen positiven Faktor und eine Gleichung vom Fermat-Typ. Danach muss man nicht mehr über alle \(z\) und alle \(n\) suchen.
Jedes Element von \(S_k\) ist ein positives rationales Zahl kleiner als 1 und bereits gekürzt. Für einen festen Nenner \(b\) gibt es genau \(\varphi(b)\) zu \(b\) teilerfremde Zähler, also
$$|S_k|=\sum_{b=2}^{k}\varphi(b).$$
Für den Zielwert \(k=35\) erhält man \(383\) zulässige Brüche. Eine naive Suche über alle Tripel müsste also schon vor der Behandlung verschiedener Exponenten \(383^3\) Kandidaten betrachten.
Die Implementierungen verwenden die ursprüngliche Funktion in der Form
$$\begin{aligned} f_n(x,y,z)={}&x^{n+1}+y^{n+1}-z^{n+1}\\ &+(xy+yz+zx)(x^{n-1}+y^{n-1}-z^{n-1})\\ &-xyz(x^{n-2}+y^{n-2}-z^{n-2}). \end{aligned}$$
Beim Ausmultiplizieren heben sich die gemischten Terme \(yz\,x^{n-1}\), \(xz\,y^{n-1}\) und \(xy\,z^{n-1}\) weg. Übrig bleibt die saubere Faktorisierung
$$f_n(x,y,z)=(x+y+z)(x^n+y^n-z^n).$$
Da \(x\), \(y\) und \(z\) positive rationale Zahlen sind, gilt immer \(x+y+z>0\). Deshalb ist
$$f_n(x,y,z)=0 \quad\Longleftrightarrow\quad x^n+y^n=z^n.$$
Genau diese Äquivalenz ist die mathematische Grundlage der Programme.
Für \(n=0\) wird die Gleichung zu \(1+1=1\), also zu einem Widerspruch. Für \(n>2\) würde jede positive rationale Lösung von \(x^n+y^n=z^n\) nach Beseitigung der Nenner eine positive ganzzahlige Lösung liefern und damit Fermats letzten Satz verletzen. Für \(n<-2\) setzt man \(m=-n>2\) und erhält
$$x^n+y^n=z^n \quad\Longleftrightarrow\quad \frac{1}{x^m}+\frac{1}{y^m}=\frac{1}{z^m},$$
also dieselbe verbotene Gleichungsform für die Kehrwerte.
Damit kommen nur
$$n\in\{-2,-1,1,2\}$$
überhaupt in Frage.
Ist \((x,y)\) fest, dann liefern die vier möglichen Exponenten unmittelbar
$$n=1:\quad z=x+y,$$
$$n=-1:\quad z=\frac{xy}{x+y},$$
$$n=2:\quad z=\sqrt{x^2+y^2},$$
$$n=-2:\quad z=\frac{1}{\sqrt{1/x^2+1/y^2}}=\frac{xy}{\sqrt{x^2+y^2}}.$$
Darum genügt ein Durchlauf über Paare statt über Tripel. In den Wurzel-Fällen wird zunächst \(z^2\) als gekürzter Bruch bestimmt; nur wenn Zähler und Nenner perfekte Quadrate sind, ist \(z\) rational. Der anschließende Mitgliedschaftstest in \(S_k\) prüft gleichzeitig, ob \(0<z<1\) und ob der gekürzte Nenner höchstens \(k\) ist.
Im Fall \(n=-1\) liefern \(x=\tfrac12\) und \(y=\tfrac13\)
$$z=\frac{xy}{x+y}=\frac{\tfrac12\cdot\tfrac13}{\tfrac12+\tfrac13}=\frac15,$$
also \(s=\tfrac12+\tfrac13+\tfrac15=\tfrac{31}{30}\). Im quadratischen Fall gilt
$$\left(\frac{3}{10}\right)^2+\left(\frac{2}{5}\right)^2=\frac{25}{100}=\left(\frac12\right)^2,$$
also ist \(\left(\tfrac{3}{10},\tfrac25,\tfrac12\right)\) ein gültiges Tripel. Für \(n=-2\) erhält man mit \(x=\tfrac13\) und \(y=\tfrac14\)
$$\frac{1}{x^2}+\frac{1}{y^2}=9+16=25=\frac{1}{(1/5)^2},$$
woraus \(z=\tfrac15\) folgt.
Wichtig ist, dass unterschiedliche Tripel oder unterschiedliche Exponenten denselben Summenwert \(s=x+y+z\) erzeugen können. Deshalb wird nicht nach Tripeln dedupliziert, sondern nach dem rationalen Wert von \(s\).
Die C++-, Python- und Java-Implementierungen erzeugen zuerst alle gekürzten Brüche aus \(S_{35}\). Dieselben Brüche werden in einer Hash-Struktur gespeichert, damit später schnell getestet werden kann, ob ein Kandidat \(z\) zulässig ist.
Danach läuft der Hauptteil über alle geordneten Paare \((x,y)\in S_k^2\). Für jedes Paar werden die vier Formeln für \(z\) exakt ausgewertet. Python verwendet eingebaute rationale Arithmetik; C++ und Java arbeiten mit gekürzten Zähler-Nenner-Paaren und normalisieren nach jeder Operation. In den Fällen \(n=\pm2\) entscheiden Ganzzahl-Quadratwurzeltests auf Zähler und Nenner, ob die Wurzel rational bleibt.
Liegt ein Kandidat \(z\) in \(S_k\), dann bildet die Implementierung \(s=x+y+z\) und fügt den gekürzten Bruch in eine Menge verschiedener Summen ein. Die Programme vermeiden die Symmetrie zwischen \((x,y)\) und \((y,x)\) nicht ausdrücklich; stattdessen werden eventuelle Wiederholungen einfach durch die Mengenstruktur entfernt.
Nach dem Paar-Durchlauf werden alle unterschiedlichen \(s\)-Werte exakt zu einem einzigen Bruch \(u/v\) addiert. Gesucht ist dann \(u+v\). Die C++-Variante enthält zusätzlich kleine Validierungsläufe: Sie vergleicht die faktorisierte Gleichung mit der ursprünglichen Definition, prüft den schnellen Paar-Scan gegen brute-force-Tripelsuche für kleine \(k\) und testet Konsistenz zwischen ein- und mehrfädiger Ausführung.
Mit
$$M=|S_k|=\sum_{b=2}^{k}\varphi(b)$$
kostet der Aufbau der Bruchliste und der Mitgliedschaftsmenge \(O(M)\). Der eigentliche Solver betrachtet alle geordneten Paare \((x,y)\) und benötigt daher \(O(M^2)\) Zeit. Pro Paar entstehen nur vier Kandidaten, einige ggT-Kürzungen, wenige Hash-Abfragen und höchstens zwei Perfekt-Quadrat-Tests.
Der Speicherbedarf ist \(O(M+U)\), wobei \(U\) die Zahl der verschiedenen Summen ist. Für \(k=35\) gilt \(M=383\), also werden nur \(146{,}689\) geordnete Paare geprüft statt \(383^3\) Tripeln. Die \(O(M^3)\)-Brute-Force-Suche taucht nur in den C++-Kontrolltests für sehr kleine Ordnungen auf.
Pozitif bir \(k\) tamsayısı için izin verilen sayılar kümesi, sadeleştirilmiş gerçek kesirlerden oluşur:
$$S_k=\left\{\frac{a}{b}:0<a<b\le k,\ \gcd(a,b)=1\right\}.$$
Problem 180'de \(k=35\) alınır. Amaç, bu küme içinden \((x,y,z)\in S_k^3\) üçlüleri arasında, problemde tanımlanan \(f_n(x,y,z)\) ifadesini en az bir tam sayı \(n\) için sıfır yapanları bulmaktır. Her geçerli üçlü için \(s=x+y+z\) yazılır; aynı rasyonel toplam yalnızca bir kez sayılır; bütün farklı toplamlar tam olarak toplanır, sonuç en sade hâliyle \(u/v\) olur ve istenen çıktı \(u+v\)'dir.
İlk bakışta tüm üçlüleri ve tüm üsleri denemek gerekiyormuş gibi görünür. Fakat çözümler, \(f_n\)'yi çarpanlarına ayırarak bu aramayı dört üs durumuna ve her \((x,y)\) çifti için en fazla dört aday \(z\)'ye indirir.
Çözümün özü tek bir cebirsel sadeleştirmedir. Orijinal sıfır koşulu doğru biçimde açıldığında, problem belirsiz bir üç değişkenli arama olmaktan çıkar ve dört açık formüle dönüşür.
\(S_k\)'deki her eleman 1'den küçük, pozitif ve zaten sadeleştirilmiş bir rasyonel sayıdır. Sabit bir \(b\) paydası için \(\varphi(b)\) tane uygun pay vardır; dolayısıyla
$$|S_k|=\sum_{b=2}^{k}\varphi(b).$$
Hedef örnekte \(k=35\) olduğundan izin verilen kesir sayısı \(383\)'tür. Bu da naif bir üçlü taramasının, üsleri düşünmeden bile, \(383^3\) aday inceleyeceği anlamına gelir.
Uygulamalarda kullanılan özgün ifade şudur:
$$\begin{aligned} f_n(x,y,z)={}&x^{n+1}+y^{n+1}-z^{n+1}\\ &+(xy+yz+zx)(x^{n-1}+y^{n-1}-z^{n-1})\\ &-xyz(x^{n-2}+y^{n-2}-z^{n-2}). \end{aligned}$$
İkinci ve üçüncü satırlar açıldığında \(yz\,x^{n-1}\), \(xz\,y^{n-1}\) ve \(xy\,z^{n-1}\) karışık terimleri birbirini götürür. Geriye
$$f_n(x,y,z)=(x+y+z)(x^n+y^n-z^n)$$
kalır. \(x\), \(y\) ve \(z\) pozitif olduğundan \(x+y+z\) hiçbir zaman sıfır değildir. Bu yüzden
$$f_n(x,y,z)=0 \quad\Longleftrightarrow\quad x^n+y^n=z^n.$$
Programların dayandığı temel matematiksel eşdeğerlik budur.
\(n=0\) için denklem \(1+1=1\) olur ve imkansızdır. \(n>2\) olduğunda \(x^n+y^n=z^n\) biçimindeki pozitif rasyonel bir çözüm, paydalar temizlenince pozitif tam sayılı bir çözüme dönüşür; bu ise Fermat'nın Son Teoremi ile çelişir. \(n<-2\) için \(m=-n>2\) yazılırsa
$$x^n+y^n=z^n \quad\Longleftrightarrow\quad \frac{1}{x^m}+\frac{1}{y^m}=\frac{1}{z^m},$$
yani aynı yasak denklem bu kez tersler üzerinde ortaya çıkar.
Dolayısıyla gerçekten denenmesi gereken üsler yalnızca
$$n\in\{-2,-1,1,2\}$$
kümesidir.
\(x\) ve \(y\) sabitlenince dört geçerli üs, \(z\) için dört kapalı form verir:
$$n=1:\quad z=x+y,$$
$$n=-1:\quad z=\frac{xy}{x+y},$$
$$n=2:\quad z=\sqrt{x^2+y^2},$$
$$n=-2:\quad z=\frac{1}{\sqrt{1/x^2+1/y^2}}=\frac{xy}{\sqrt{x^2+y^2}}.$$
Bu nedenle optimize edilmiş çözüm üçlüler yerine sıralı çiftler üzerinde dolaşır. Karekök içeren iki dalda önce \(z^2\) sadeleştirilmiş kesir olarak hesaplanır; pay ve payda tam kare değilse \(z\) rasyonel değildir. Sonrasında yapılan \(S_k\) üyelik testi, aynı anda hem \(0<z<1\) koşulunu hem de sadeleştirilmiş paydanın \(k\)'yi aşmamasını denetler.
\(n=-1\) dalında \(x=\tfrac12\) ve \(y=\tfrac13\) için
$$z=\frac{xy}{x+y}=\frac{\tfrac12\cdot\tfrac13}{\tfrac12+\tfrac13}=\frac15$$
olur; dolayısıyla \(s=\tfrac12+\tfrac13+\tfrac15=\tfrac{31}{30}\). \(n=2\) dalında ise
$$\left(\frac{3}{10}\right)^2+\left(\frac{2}{5}\right)^2=\frac{25}{100}=\left(\frac12\right)^2,$$
yani \(\left(\tfrac{3}{10},\tfrac25,\tfrac12\right)\) geçerli bir üçlüdür. \(n=-2\) için \(x=\tfrac13\), \(y=\tfrac14\) seçilirse
$$\frac{1}{x^2}+\frac{1}{y^2}=9+16=25=\frac{1}{(1/5)^2},$$
buradan da \(z=\tfrac15\) çıkar.
Önemli nokta şudur: farklı üçlüler veya farklı üsler aynı \(s=x+y+z\) değerini üretebilir. Bu nedenle kod, üçlüleri değil son toplamları tekilleştirir.
C++, Python ve Java uygulamaları önce \(S_{35}\)'teki bütün sadeleştirilmiş kesirleri üretir. Aynı kesirler hızlı üyelik testi için hash tabanlı bir yapıya da yerleştirilir.
Ana döngü bütün sıralı \((x,y)\in S_k^2\) çiftleri üzerinden geçer. Her çift için yukarıdaki dört \(z\) adayı tam rasyonel aritmetik ile hesaplanır. Python sürümü yerleşik kesir tipini kullanır; C++ ve Java sürümleri ise sadeleştirilmiş pay-payda çiftleriyle çalışır ve her işlemden sonra normalize eder. \(n=\pm2\) dallarında, pay ve payda üzerinde yapılan tamsayı karekök testleri sayesinde kökün gerçekten rasyonel olup olmadığı kesin biçimde anlaşılır.
Eğer aday \(z\), \(S_k\) içinde yer alıyorsa uygulama \(s=x+y+z\) toplamını oluşturur ve bu sadeleştirilmiş kesri farklı toplamlar kümesine ekler. \((x,y)\) ile \((y,x)\) simetrisi özellikle elenmez; tekrarlar çıkarsa küme yapısı onları zaten otomatik olarak siler.
Çift taraması bittikten sonra bütün farklı \(s\) değerleri tam doğrulukla toplanır ve tek bir \(u/v\) kesrine indirgenir. Nihai çıktı \(u+v\)'dir. C++ uygulaması ayrıca küçük mertebelerde doğrulama kontrolleri de içerir: faktörize denklem ile özgün tanımı karşılaştırır, hızlı çift taramasını küçük \(k\) için kaba kuvvet üçlü taramasıyla sınar ve tek iş parçacıklı sonuçla çok iş parçacıklı sonucu karşılaştırır.
$$M=|S_k|=\sum_{b=2}^{k}\varphi(b)$$
olsun. Kesir listesini ve üyelik kümesini kurmak \(O(M)\) zaman alır. Ana çözüm, bütün sıralı \((x,y)\) çiftlerini gezdiği için baskın maliyet \(O(M^2)\)'dir. Her çiftte sadece dört aday üretilir; birkaç gcd sadeleştirmesi, az sayıda hash sorgusu ve en fazla iki tam-kare kontrolü yapılır.
Bellek kullanımı \(O(M+U)\)'dir; burada \(U\), saklanan farklı toplam sayısıdır. Hedef durumda \(k=35\) için \(M=383\) olduğundan çözüm yalnızca \(146{,}689\) sıralı çift inceler. Naif \(O(M^3)\) üçlü taraması ise yalnızca C++ doğrulama aşamasında ve çok küçük mertebelerde kullanılır.
Para un entero positivo \(k\), el conjunto admisible está formado por las fracciones propias reducidas
$$S_k=\left\{\frac{a}{b}:0<a<b\le k,\ \gcd(a,b)=1\right\}.$$
En el problema 180 se toma \(k=35\). Hay que encontrar todos los ternas \((x,y,z)\in S_k^3\) para los que la función \(f_n(x,y,z)\) del enunciado vale cero para al menos un entero \(n\). Para cada terna válida se define \(s=x+y+z\), se conservan solo los valores racionales distintos de \(s\), se suman exactamente, se reduce el total a \(u/v\) y la respuesta pedida es \(u+v\).
Una lectura ingenua sugiere recorrer todas las ternas y todos los exponentes enteros. La solución real no hace eso: primero factoriza \(f_n\), luego demuestra que solo cuatro exponentes pueden contribuir y finalmente convierte la búsqueda en un barrido por pares \((x,y)\).
La simplificación decisiva es algebraica. La condición de anulación parece complicada, pero en realidad se separa en un factor siempre positivo y una ecuación del tipo de Fermat.
Cada elemento de \(S_k\) es un racional positivo menor que 1 y ya está en forma irreducible. Para un denominador fijo \(b\), existen exactamente \(\varphi(b)\) numeradores coprimos con \(b\), así que
$$|S_k|=\sum_{b=2}^{k}\varphi(b).$$
Cuando \(k=35\), esto da \(383\) fracciones admisibles. Un recorrido ingenuo por ternas tendría que inspeccionar \(383^3\) combinaciones incluso antes de tratar con los distintos valores de \(n\).
Las implementaciones usan la función original en la forma
$$\begin{aligned} f_n(x,y,z)={}&x^{n+1}+y^{n+1}-z^{n+1}\\ &+(xy+yz+zx)(x^{n-1}+y^{n-1}-z^{n-1})\\ &-xyz(x^{n-2}+y^{n-2}-z^{n-2}). \end{aligned}$$
Al expandir, los términos mixtos \(yz\,x^{n-1}\), \(xz\,y^{n-1}\) y \(xy\,z^{n-1}\) se cancelan. Lo que queda factoriza exactamente como
$$f_n(x,y,z)=(x+y+z)(x^n+y^n-z^n).$$
Como \(x\), \(y\) y \(z\) son racionales positivos, \(x+y+z>0\) siempre. Por tanto,
$$f_n(x,y,z)=0 \quad\Longleftrightarrow\quad x^n+y^n=z^n.$$
Ese es el puente que conecta el enunciado original con el algoritmo.
Si \(n=0\), la ecuación se reduce a \(1+1=1\), imposible. Si \(n>2\), una solución racional positiva de \(x^n+y^n=z^n\) puede limpiarse de denominadores y producir una solución entera positiva, en contradicción con el último teorema de Fermat. Si \(n<-2\), escribimos \(m=-n>2\) y obtenemos
$$x^n+y^n=z^n \quad\Longleftrightarrow\quad \frac{1}{x^m}+\frac{1}{y^m}=\frac{1}{z^m},$$
que es la misma ecuación prohibida aplicada a los recíprocos.
Así, los únicos exponentes relevantes son
$$n\in\{-2,-1,1,2\}.$$
Fijados \(x\) e \(y\), cada caso da una fórmula explícita:
$$n=1:\quad z=x+y,$$
$$n=-1:\quad z=\frac{xy}{x+y},$$
$$n=2:\quad z=\sqrt{x^2+y^2},$$
$$n=-2:\quad z=\frac{1}{\sqrt{1/x^2+1/y^2}}=\frac{xy}{\sqrt{x^2+y^2}}.$$
Por eso el solucionador rápido recorre pares ordenados \((x,y)\) y no ternas. En las ramas con raíces, primero se calcula \(z^2\) como fracción reducida; solo se acepta el caso si numerador y denominador son cuadrados perfectos. Después, comprobar si \(z\in S_k\) asegura a la vez que \(0<z<1\) y que el denominador reducido no supera \(k\).
En la rama \(n=-1\), si \(x=\tfrac12\) e \(y=\tfrac13\), entonces
$$z=\frac{xy}{x+y}=\frac{\tfrac12\cdot\tfrac13}{\tfrac12+\tfrac13}=\frac15,$$
de modo que \(s=\tfrac12+\tfrac13+\tfrac15=\tfrac{31}{30}\). En la rama cuadrática,
$$\left(\frac{3}{10}\right)^2+\left(\frac{2}{5}\right)^2=\frac{25}{100}=\left(\frac12\right)^2,$$
así que \(\left(\tfrac{3}{10},\tfrac25,\tfrac12\right)\) es una terna válida. Para \(n=-2\), tomar \(x=\tfrac13\) e \(y=\tfrac14\) produce
$$\frac{1}{x^2}+\frac{1}{y^2}=9+16=25=\frac{1}{(1/5)^2},$$
y por tanto \(z=\tfrac15\).
Distintas ternas, e incluso distintos exponentes, pueden llevar al mismo valor final \(s=x+y+z\). Por eso se eliminan duplicados al nivel de las sumas racionales, no al nivel de las ternas.
Las implementaciones en C++, Python y Java generan primero todas las fracciones reducidas de \(S_{35}\). También construyen una estructura hash con esas mismas fracciones para decidir rápidamente si un candidato \(z\) pertenece al conjunto admisible.
El bucle principal recorre todos los pares ordenados \((x,y)\in S_k^2\). Para cada par, la implementación calcula las cuatro expresiones para \(z\) usando aritmética racional exacta. Python utiliza un tipo racional incorporado; C++ y Java trabajan con pares numerador-denominador normalizados tras cada operación. En las ramas \(n=\pm2\), una prueba de raíz cuadrada entera sobre el numerador y el denominador reducidos determina si la raíz sigue siendo racional.
Si el candidato \(z\) pertenece a \(S_k\), se forma \(s=x+y+z\) y se inserta esa fracción reducida en un conjunto de sumas distintas. No se intenta explotar la simetría entre \((x,y)\) y \((y,x)\); simplemente se permiten repeticiones y el conjunto las elimina automáticamente.
Al terminar el barrido, todas las sumas distintas se agregan exactamente y se reducen a una única fracción \(u/v\). La salida pedida es \(u+v\). La versión en C++ añade comprobaciones internas para órdenes pequeños: compara la ecuación factorizada con la definición original, contrasta el método rápido con una búsqueda de ternas por fuerza bruta y verifica que la ejecución con y sin paralelismo produzca el mismo conjunto de sumas.
Sea
$$M=|S_k|=\sum_{b=2}^{k}\varphi(b).$$
Generar la lista de fracciones y la estructura de pertenencia cuesta \(O(M)\). El solucionador principal recorre todos los pares ordenados, por lo que el coste dominante es \(O(M^2)\). Cada par requiere cuatro construcciones de candidatos, un número constante de reducciones por gcd, unas pocas búsquedas en hash y como mucho dos pruebas de cuadrado perfecto.
La memoria es \(O(M+U)\), donde \(U\) es el número de sumas distintas retenidas. En el caso objetivo \(k=35\), \(M=383\), así que el método rápido examina \(146{,}689\) pares ordenados en lugar de \(383^3\) ternas. El enfoque \(O(M^3)\) queda relegado a las validaciones pequeñas de la implementación en C++.
对正整数 \(k\)，题目允许使用的有理数集合是所有既约真分数
$$S_k=\left\{\frac{a}{b}:0<a<b\le k,\ \gcd(a,b)=1\right\}.$$
在 Problem 180 中，目标参数是 \(k=35\)。我们要找出所有满足 \((x,y,z)\in S_k^3\) 且对某个整数 \(n\) 有 \(f_n(x,y,z)=0\) 的三元组。对每个有效三元组，定义 \(s=x+y+z\)；把所有不同的 \(s\) 作为有理数去重后精确求和；若总和约成最简分数 \(u/v\)，最终要求输出的是 \(u+v\)。
如果直接理解题意，就会想到对所有三元组和所有整数 \(n\) 暴力枚举。但实现并没有这样做。核心思路是先把 \(f_n\) 做代数因式分解，再证明真正可能出现解的指数只有四个，于是问题就从“三元组搜索”变成了“有序数对 \((x,y)\) 扫描”。
这道题真正困难的地方不在编程，而在于把原始条件看穿。一旦把零条件写成正确的乘积形式，题目就不再是开放式的三变量搜索，而是四个显式候选公式的有限枚举。
\(S_k\) 中的每个元素都是小于 1 的正有理数，并且已经处于最简形式。对固定分母 \(b\)，与它互素的分子个数正好是 \(\varphi(b)\)，因此
$$|S_k|=\sum_{b=2}^{k}\varphi(b).$$
当 \(k=35\) 时，允许的分数一共有 \(383\) 个。也就是说，如果不先做数学化简，哪怕先不考虑不同的指数，单是三元组就已经有 \(383^3\) 个候选。
实现中采用的原始函数是
$$\begin{aligned} f_n(x,y,z)={}&x^{n+1}+y^{n+1}-z^{n+1}\\ &+(xy+yz+zx)(x^{n-1}+y^{n-1}-z^{n-1})\\ &-xyz(x^{n-2}+y^{n-2}-z^{n-2}). \end{aligned}$$
把后两行展开后，混合项 \(yz\,x^{n-1}\)、\(xz\,y^{n-1}\)、\(xy\,z^{n-1}\) 会两两抵消，剩下的部分恰好可以整理成
$$f_n(x,y,z)=(x+y+z)(x^n+y^n-z^n).$$
因为 \(x\)、\(y\)、\(z\) 都是正有理数，所以 \(x+y+z>0\) 恒成立，于是
$$f_n(x,y,z)=0 \quad\Longleftrightarrow\quad x^n+y^n=z^n.$$
这一等价关系就是全部算法的数学核心。题目表面上是在研究一个三变量函数的零点，实际上是在研究若干低次数的有理数费马型方程。
如果 \(n=0\)，方程直接变成 \(1+1=1\)，显然不可能。若 \(n>2\)，那么正有理数解 \(x^n+y^n=z^n\) 可以通过清除分母转化为正整数解，这与费马大定理矛盾。若 \(n<-2\)，令 \(m=-n>2\)，则
$$x^n+y^n=z^n \quad\Longleftrightarrow\quad \frac{1}{x^m}+\frac{1}{y^m}=\frac{1}{z^m},$$
也就是把同样的费马型方程应用到倒数上，同样不可能有正有理解。
因此真正可能产生解的指数只剩下
$$n\in\{-2,-1,1,2\}.$$
原本“对所有整数 \(n\)”的搜索，到这里已经被压缩成四个固定分支。
一旦 \(x\) 和 \(y\) 给定，四个可行指数分别给出
$$n=1:\quad z=x+y,$$
$$n=-1:\quad z=\frac{xy}{x+y},$$
$$n=2:\quad z=\sqrt{x^2+y^2},$$
$$n=-2:\quad z=\frac{1}{\sqrt{1/x^2+1/y^2}}=\frac{xy}{\sqrt{x^2+y^2}}.$$
这就是为什么最终程序只需要枚举有序对 \((x,y)\)，而不需要再枚举第三个变量 \(z\)。对于带平方根的两条分支，实现会先把 \(z^2\) 化成最简分数，然后检查分子和分母是否分别是完全平方数。只有这样，\(z\) 才仍然是有理数。随后再用 \(S_k\) 的成员测试同时确认 \(0<z<1\) 且约分后的分母不超过 \(k\)。
先看 \(n=-1\) 分支。取 \(x=\tfrac12\)、\(y=\tfrac13\)，则
$$z=\frac{xy}{x+y}=\frac{\tfrac12\cdot\tfrac13}{\tfrac12+\tfrac13}=\frac15,$$
于是 \(s=\tfrac12+\tfrac13+\tfrac15=\tfrac{31}{30}\)。再看 \(n=2\) 分支，
$$\left(\frac{3}{10}\right)^2+\left(\frac{2}{5}\right)^2=\frac{9}{100}+\frac{16}{100}=\frac{25}{100}=\left(\frac12\right)^2,$$
所以 \(\left(\tfrac{3}{10},\tfrac25,\tfrac12\right)\) 是一个有效三元组。对于 \(n=-2\)，如果取 \(x=\tfrac13\)、\(y=\tfrac14\)，那么
$$\frac{1}{x^2}+\frac{1}{y^2}=9+16=25=\frac{1}{(1/5)^2},$$
因此 \(z=\tfrac15\)。
需要特别注意的是，题目并不是要求统计不同的三元组，而是要求统计不同的和 \(s=x+y+z\)。不同三元组，甚至不同的指数分支，都可能产生同一个 \(s\)。所以实现必须在“和”的层面去重，而不是在三元组层面去重。
C++、Python 和 Java 实现都会先生成 \(S_{35}\) 中的全部既约分数，并把这些分数放入哈希结构中，方便后续用常数期望时间判断某个候选 \(z\) 是否属于允许集合。
主循环遍历所有有序对 \((x,y)\in S_k^2\)。对每一对，程序都精确计算四个候选 \(z\)。Python 直接使用精确有理数类型；C++ 和 Java 则显式维护“最简分子 / 最简分母”对，并在每次加、乘、除或取倒数之后约分。对于 \(n=\pm2\) 的分支，程序会对约分后的分子和分母分别做整数平方根检查，以确认平方根仍是有理数。
如果某个候选 \(z\) 通过了 \(S_k\) 的成员测试，程序就计算 \(s=x+y+z\)，并把这个最简分数放入“不同和”的集合里。实现并不会刻意避开 \((x,y)\) 与 \((y,x)\) 的对称重复，而是让集合结构自动去除重复结果。
遍历结束后，所有不同的 \(s\) 都会被精确相加并约成单个分数 \(u/v\)，最后输出 \(u+v\)。C++ 实现还加入了小规模校验：它会在较小的 \(k\) 上比较“原始定义”和“因式分解后的方程”，再把快速的二重循环方法与暴力三重枚举做比对，并检查单线程与多线程得到的和集合是否完全一致。
记
$$M=|S_k|=\sum_{b=2}^{k}\varphi(b).$$
构造分数列表和成员哈希集合需要 \(O(M)\) 时间。主算法遍历全部有序对 \((x,y)\)，因此主导时间复杂度是 \(O(M^2)\)。每一对只会产生四个候选值，并伴随常数次 gcd 约分、少量哈希查询以及最多两次完全平方检测。
空间复杂度为 \(O(M+U)\)，其中 \(U\) 是不同和的数量。对目标参数 \(k=35\) 而言，\(M=383\)，所以快速算法只需检查 \(146{,}689\) 个有序对，而不是 \(383^3\) 个三元组。更慢的 \(O(M^3)\) 暴力方法只出现在 C++ 的小规模验证阶段。
Для положительного целого \(k\) допустимое множество состоит из несократимых правильных дробей
$$S_k=\left\{\frac{a}{b}:0<a<b\le k,\ \gcd(a,b)=1\right\}.$$
В задаче 180 берётся \(k=35\). Нужно найти все тройки \((x,y,z)\in S_k^3\), для которых функция \(f_n(x,y,z)\) обращается в ноль хотя бы для одного целого \(n\). Для каждой подходящей тройки вычисляется \(s=x+y+z\); одинаковые рациональные значения \(s\) учитываются только один раз; затем они суммируются точно, сумма приводится к виду \(u/v\), и требуется вывести \(u+v\).
Наивное чтение задачи подталкивает к перебору всех троек и всех целых показателей. Реальное решение намного уже: сначала выражение \(f_n\) факторизуется, затем доказывается, что важны только четыре степени, после чего поиск сводится к перебору пар \((x,y)\).
Ключ к задаче чисто алгебраический. Сложная на вид формула на самом деле распадается на положительный множитель и уравнение ферматова типа. После этого огромный перебор исчезает.
Каждый элемент \(S_k\) — это положительное рациональное число меньше 1, уже записанное в несократимом виде. Для фиксированного знаменателя \(b\) допустимых числителей ровно \(\varphi(b)\), поэтому
$$|S_k|=\sum_{b=2}^{k}\varphi(b).$$
При \(k=35\) получаем \(383\) допустимые дроби. Значит, даже без учёта разных \(n\), прямой перебор троек должен был бы рассматривать \(383^3\) вариантов.
В реализациях исходная функция записывается так:
$$\begin{aligned} f_n(x,y,z)={}&x^{n+1}+y^{n+1}-z^{n+1}\\ &+(xy+yz+zx)(x^{n-1}+y^{n-1}-z^{n-1})\\ &-xyz(x^{n-2}+y^{n-2}-z^{n-2}). \end{aligned}$$
После раскрытия скобок смешанные члены \(yz\,x^{n-1}\), \(xz\,y^{n-1}\) и \(xy\,z^{n-1}\) сокращаются, а оставшееся выражение точно сворачивается в
$$f_n(x,y,z)=(x+y+z)(x^n+y^n-z^n).$$
Так как \(x\), \(y\) и \(z\) положительны, всегда выполняется \(x+y+z>0\). Следовательно,
$$f_n(x,y,z)=0 \quad\Longleftrightarrow\quad x^n+y^n=z^n.$$
Именно эта эквивалентность позволяет заменить исходное условие гораздо более простой задачей.
При \(n=0\) получается \(1+1=1\), что невозможно. Если \(n>2\), положительное рациональное решение уравнения \(x^n+y^n=z^n\) можно очистить от знаменателей и получить положительное целочисленное решение, противоречащее великой теореме Ферма. Если \(n<-2\), положим \(m=-n>2\); тогда
$$x^n+y^n=z^n \quad\Longleftrightarrow\quad \frac{1}{x^m}+\frac{1}{y^m}=\frac{1}{z^m},$$
то есть возникает та же запрещённая форма для обратных чисел.
Значит, реально возможны только
$$n\in\{-2,-1,1,2\}.$$
После фиксации \(x\) и \(y\) каждая из четырёх степеней даёт явную формулу:
$$n=1:\quad z=x+y,$$
$$n=-1:\quad z=\frac{xy}{x+y},$$
$$n=2:\quad z=\sqrt{x^2+y^2},$$
$$n=-2:\quad z=\frac{1}{\sqrt{1/x^2+1/y^2}}=\frac{xy}{\sqrt{x^2+y^2}}.$$
Поэтому быстрый алгоритм идёт по упорядоченным парам \((x,y)\), а не по тройкам. В ветвях с корнем сначала вычисляется сокращённая дробь для \(z^2\); далее проверяется, являются ли числитель и знаменатель полными квадратами. Только в этом случае \(z\) остаётся рациональным. Затем проверка принадлежности \(S_k\) одновременно гарантирует условия \(0<z<1\) и «сокращённый знаменатель не больше \(k\)».
В ветви \(n=-1\) при \(x=\tfrac12\) и \(y=\tfrac13\) получаем
$$z=\frac{xy}{x+y}=\frac{\tfrac12\cdot\tfrac13}{\tfrac12+\tfrac13}=\frac15,$$
поэтому \(s=\tfrac12+\tfrac13+\tfrac15=\tfrac{31}{30}\). В квадратичной ветви
$$\left(\frac{3}{10}\right)^2+\left(\frac{2}{5}\right)^2=\frac{25}{100}=\left(\frac12\right)^2,$$
значит, \(\left(\tfrac{3}{10},\tfrac25,\tfrac12\right)\) — допустимая тройка. Для \(n=-2\), если взять \(x=\tfrac13\) и \(y=\tfrac14\), то
$$\frac{1}{x^2}+\frac{1}{y^2}=9+16=25=\frac{1}{(1/5)^2},$$
откуда \(z=\tfrac15\).
Разные тройки и даже разные показатели могут приводить к одному и тому же значению \(s=x+y+z\). Поэтому реализации устраняют дубликаты именно на уровне сумм \(s\), а не на уровне троек.
Реализации на C++, Python и Java сначала перечисляют все несократимые дроби из \(S_{35}\). Эти же дроби помещаются в хеш-структуру, чтобы быстро проверять принадлежность кандидата \(z\) допустимому множеству.
Основной цикл проходит по всем упорядоченным парам \((x,y)\in S_k^2\). Для каждой пары вычисляются четыре возможные формулы для \(z\). Все операции выполняются точно: Python использует встроенную рациональную арифметику, а C++ и Java работают с сокращёнными парами «числитель / знаменатель» и нормализуют результат после каждого сложения, умножения, деления или взятия обратного. В ветвях \(n=\pm2\) рациональность квадратного корня проверяется через целочисленный квадратный корень числителя и знаменателя.
Если найденный кандидат \(z\) принадлежит \(S_k\), программа формирует \(s=x+y+z\) и добавляет эту сокращённую дробь в множество различных сумм. Симметрия между \((x,y)\) и \((y,x)\) явно не устраняется; возможные повторы просто отфильтровываются самой структурой множества.
После завершения перебора все различные значения \(s\) точно складываются и приводятся к одному дробному числу \(u/v\). В ответ идёт \(u+v\). В реализации на C++ есть и дополнительные проверки на малых порядках: сравнение факторизованной формулы с исходным определением, сверка быстрого алгоритма с полным перебором троек и проверка совпадения однопоточного и многопоточного режимов.
Пусть
$$M=|S_k|=\sum_{b=2}^{k}\varphi(b).$$
Построение списка дробей и хеш-множества стоит \(O(M)\). Основной алгоритм рассматривает все упорядоченные пары \((x,y)\), поэтому доминирующая сложность равна \(O(M^2)\). На каждую пару приходится четыре построения кандидатов, константное число сокращений через gcd, несколько обращений к хешу и не более двух проверок на полный квадрат.
Память равна \(O(M+U)\), где \(U\) — число различных сумм. Для целевого случая \(k=35\) имеем \(M=383\), значит быстрый метод проверяет \(146{,}689\) упорядоченных пар вместо \(383^3\) троек. Медленный \(O(M^3)\) перебор используется только в маленьких проверках внутри C++-решения.
لأي عدد صحيح موجب \(k\)، تكون مجموعة الكسور المسموح بها هي مجموعة الكسور الحقيقية الموجبة المختزلة:
$$S_k=\left\{\frac{a}{b}:0<a<b\le k,\ \gcd(a,b)=1\right\}.$$
في المسألة 180 نأخذ \(k=35\). المطلوب هو إيجاد جميع الثلاثيات \((x,y,z)\in S_k^3\) التي تجعل الدالة \(f_n(x,y,z)\) مساوية للصفر من أجل عدد صحيح واحد على الأقل \(n\). لكل ثلاثية صالحة نعرّف \(s=x+y+z\)، ثم نأخذ القيم النسبية المميزة فقط، ونجمعها جمعًا دقيقًا، ونكتب المجموع في أبسط صورة \(u/v\)، وتكون القيمة المطلوبة في النهاية هي \(u+v\).
الفهم المباشر للمسألة يوحي بضرورة فحص كل ثلاثية وكل أس صحيح ممكن. لكن الحل الفعلي لا يفعل ذلك. الفكرة الأساسية هي تحليل \(f_n\) إلى عوامل، ثم إثبات أن الأسس التي يمكن أن تعطي حلولًا تنحصر في أربع حالات فقط، وبعد ذلك يتحول البحث إلى مسح للأزواج \((x,y)\) بدلًا من الثلاثيات.
جوهر الحل جبري بالكامل. فالتعبير الذي يبدو معقدًا في نص المسألة ينفصل في الحقيقة إلى عامل موجب دائمًا ومعادلة من نمط فيرما، وعندها ينهار مجال البحث إلى حجم صغير جدًا.
كل عنصر في \(S_k\) هو عدد نسبي موجب أصغر من 1 ومكتوب أصلًا في صورته المختزلة. ولكل مقام ثابت \(b\) يوجد بالضبط \(\varphi(b)\) بسطًا أوليًا معه، ولذلك
$$|S_k|=\sum_{b=2}^{k}\varphi(b).$$
عندما يكون \(k=35\)، نحصل على \(383\) كسرًا مسموحًا. وهذا يعني أن الفحص الساذج لجميع الثلاثيات كان سيحتاج إلى النظر في \(383^3\) احتمالًا حتى قبل التفكير في قيم \(n\) المختلفة.
البرامج تستخدم الدالة الأصلية بالشكل التالي:
$$\begin{aligned} f_n(x,y,z)={}&x^{n+1}+y^{n+1}-z^{n+1}\\ &+(xy+yz+zx)(x^{n-1}+y^{n-1}-z^{n-1})\\ &-xyz(x^{n-2}+y^{n-2}-z^{n-2}). \end{aligned}$$
عند التوسيع، تُلغى الحدود المختلطة \(yz\,x^{n-1}\) و\(xz\,y^{n-1}\) و\(xy\,z^{n-1}\)، ويتحول التعبير كله إلى
$$f_n(x,y,z)=(x+y+z)(x^n+y^n-z^n).$$
وبما أن \(x\) و\(y\) و\(z\) أعداد نسبية موجبة، فإن \(x+y+z>0\) دائمًا. لذلك نحصل على التكافؤ الحاسم
$$f_n(x,y,z)=0 \quad\Longleftrightarrow\quad x^n+y^n=z^n.$$
هذا هو الأساس الرياضي الذي تعتمد عليه كل نسخة من نسخ التنفيذ.
إذا كان \(n=0\)، تصبح المعادلة \(1+1=1\)، وهذا مستحيل. وإذا كان \(n>2\)، فإن أي حل نسبي موجب للمعادلة \(x^n+y^n=z^n\) يمكن إزالة مقاماته لنحصل على حل صحيح موجب، وهو ما يناقض مبرهنة فيرما الأخيرة. وإذا كان \(n<-2\)، نكتب \(m=-n>2\)، فنجد أن
$$x^n+y^n=z^n \quad\Longleftrightarrow\quad \frac{1}{x^m}+\frac{1}{y^m}=\frac{1}{z^m},$$
أي إننا حصلنا على المعادلة نفسها لكن مطبقة على المقلوبات، وبالتالي تبقى مستحيلة أيضًا.
إذن الأسس الوحيدة التي يمكن أن تسهم في الحل هي
$$n\in\{-2,-1,1,2\}.$$
بعد تثبيت \(x\) و\(y\)، تعطي الحالات الأربع الصيغ الصريحة التالية:
$$n=1:\quad z=x+y,$$
$$n=-1:\quad z=\frac{xy}{x+y},$$
$$n=2:\quad z=\sqrt{x^2+y^2},$$
$$n=-2:\quad z=\frac{1}{\sqrt{1/x^2+1/y^2}}=\frac{xy}{\sqrt{x^2+y^2}}.$$
ولهذا السبب يكتفي الحل السريع بالمرور على الأزواج المرتبة \((x,y)\) بدلًا من المرور على الثلاثيات. في فرعي الجذر التربيعي، تُحسب أولًا قيمة \(z^2\) ككسر مختزل، ولا يُقبل المرشح إلا إذا كان كل من البسط والمقام مربعًا كاملًا. وبعد ذلك يختبر التنفيذ انتماء \(z\) إلى \(S_k\)، وبذلك يتحقق في الوقت نفسه أن \(0<z<1\) وأن المقام بعد الاختزال لا يتجاوز \(k\).
في فرع \(n=-1\)، إذا أخذنا \(x=\tfrac12\) و\(y=\tfrac13\)، فإن
$$z=\frac{xy}{x+y}=\frac{\tfrac12\cdot\tfrac13}{\tfrac12+\tfrac13}=\frac15,$$
ومن ثم \(s=\tfrac12+\tfrac13+\tfrac15=\tfrac{31}{30}\). وفي فرع \(n=2\) نجد أن
$$\left(\frac{3}{10}\right)^2+\left(\frac{2}{5}\right)^2=\frac{25}{100}=\left(\frac12\right)^2,$$
ولذلك تكون الثلاثية \(\left(\tfrac{3}{10},\tfrac25,\tfrac12\right)\) صالحة. أما في فرع \(n=-2\)، فإذا أخذنا \(x=\tfrac13\) و\(y=\tfrac14\)، نحصل على
$$\frac{1}{x^2}+\frac{1}{y^2}=9+16=25=\frac{1}{(1/5)^2},$$
ومن هنا يكون \(z=\tfrac15\).
النقطة المهمة هي أن ثلاثيات مختلفة، بل وحتى أسس مختلفة، قد تعطي القيمة نفسها \(s=x+y+z\). لذلك لا تتم إزالة التكرار على مستوى الثلاثيات، وإنما على مستوى المجاميع النسبية النهائية.
تبدأ تطبيقات C++ وPython وJava بتوليد جميع الكسور المختزلة في \(S_{35}\). ثم تُخزن هذه الكسور أيضًا في بنية hash حتى يمكن تقرير ما إذا كان المرشح \(z\) ينتمي إلى المجموعة المسموح بها بزمن متوقع ثابت.
تجتاز الحلقة الرئيسية جميع الأزواج المرتبة \((x,y)\in S_k^2\). ولكل زوج تُحسب قيم \(z\) الأربع السابقة بحساب نسبي دقيق. تستخدم نسخة Python نوع الكسور الدقيق الجاهز، بينما تحتفظ نسختا C++ وJava بزوج «بسط / مقام» مختزل ويجري التطبيع بعد كل عملية جمع أو ضرب أو قسمة أو قلب. وفي حالتي \(n=\pm2\)، يحدد اختبار الجذر التربيعي الصحيح على البسط والمقام المختزلين ما إذا كان الجذر ما يزال عددًا نسبيًا.
إذا كان \(z\) المرشح عنصرًا في \(S_k\)، تُحسب القيمة \(s=x+y+z\) ثم تُضاف هذه الكسرة المختزلة إلى مجموعة المجاميع المميزة. ولا تحاول الشيفرة استغلال التناظر بين \((x,y)\) و\((y,x)\) صراحةً؛ بل تسمح بظهور التكرارات ثم تزيلها مجموعة القيم المميزة تلقائيًا.
بعد انتهاء مسح الأزواج، تُجمع جميع قيم \(s\) المختلفة جمعًا دقيقًا وتُختزل إلى كسر واحد \(u/v\). ثم تكون المخرجة المطلوبة هي \(u+v\). وتضيف نسخة C++ كذلك نقاط تحقق صغيرة: فهي تقارن بين الصيغة المفككة والصيغة الأصلية للمسألة، وتفحص الحل السريع مقابل تعداد ثلاثي بالقوة الغاشمة عند قيم صغيرة لـ \(k\)، وتتحقق من تطابق النتائج بين التشغيل أحادي الخيط ومتعدد الخيوط.
إذا كتبنا
$$M=|S_k|=\sum_{b=2}^{k}\varphi(b),$$
فإن بناء قائمة الكسور وبنية العضوية يكلف \(O(M)\). بعد ذلك يمر الحل الرئيسي على جميع الأزواج المرتبة \((x,y)\)، ولذلك تكون الكلفة المسيطرة \(O(M^2)\). كل زوج ينتج أربع محاولات فقط، مع عدد ثابت من عمليات الاختزال بواسطة gcd، وبضع عمليات بحث في hash، وعلى الأكثر اختبارين للمربع الكامل.
استهلاك الذاكرة هو \(O(M+U)\)، حيث \(U\) هو عدد المجاميع المختلفة المحتفظ بها. وعند \(k=35\) نحصل على \(M=383\)، ولذلك يفحص الحل السريع \(146{,}689\) زوجًا مرتبًا فقط بدلًا من \(383^3\) ثلاثية. أما الفحص الأبطأ \(O(M^3)\) فلا يُستخدم إلا داخل اختبارات التحقق الصغيرة في نسخة C++.