We seek the smallest positive integer \(n\) for which the Diophantine equation \( \frac{1}{x} + \frac{1}{y} = \frac{1}{n} \) has more than \(4{,}000{,}000\) distinct positive integer solutions. The successful approach does not search over pairs \((x,y)\) directly. Instead, it rewrites the equation as a divisor-count condition on \(n^2\), then searches over the prime factorization of \(n\).
That reformulation turns a two-variable equation into a multiplicative optimization problem. Once the exponent pattern of \(n\) is known, the number of solutions is determined, and the remaining task is to find the smallest \(n\) whose exponent pattern forces the solution count past the required threshold.
The key step is to convert the reciprocal equation into a factorization problem.
Starting from
$$\frac{1}{x} + \frac{1}{y} = \frac{1}{n},$$
multiply through by \(xyn\):
$$n(x+y)=xy.$$
Rearranging gives
$$xy-nx-ny=0,$$
and after adding \(n^2\) to both sides we obtain
$$\boxed{(x-n)(y-n)=n^2.}$$
So every positive solution corresponds to a factorization \(uv=n^2\) with
$$u=x-n,\qquad v=y-n,$$
and conversely every positive factor pair of \(n^2\) produces a solution
$$x=n+u,\qquad y=n+v.$$
If ordered pairs were counted, then each divisor \(u\mid n^2\) would determine exactly one pair \((u,n^2/u)\), so the ordered count would be \(d(n^2)\), where \(d\) is the divisor function.
Project Euler counts distinct solutions, so \((x,y)\) and \((y,x)\) are the same unless they lie on the diagonal. Because \(n^2\) is a square, there is exactly one central factorization with \(u=v=n\). Therefore the number of distinct solutions is
$$\boxed{N(n)=\frac{d(n^2)+1}{2}.}$$
Hence the requirement
$$N(n) \gt 4{,}000{,}000$$
is equivalent to
$$d(n^2)\ge 8{,}000{,}001.$$
The odd threshold is not accidental: every exponent in \(n^2\) is even, so \(d(n^2)\) is always an odd number.
Write the prime factorization of \(n\) as
$$n=\prod_{i=1}^{k} p_i^{a_i}.$$
Then
$$n^2=\prod_{i=1}^{k} p_i^{2a_i},$$
and the divisor formula becomes
$$d(n^2)=\prod_{i=1}^{k}(2a_i+1).$$
So the original problem is equivalent to finding the smallest number of the form
$$n=\prod p_i^{a_i}$$
such that
$$\prod (2a_i+1)\ge 8{,}000{,}001.$$
At this point the variables \(x\) and \(y\) have disappeared completely; everything is controlled by the exponent vector \((a_1,a_2,\dots)\).
To minimize \(n\), the exponents must be arranged in a very specific way.
First, the used primes must form an initial segment \(2,3,5,\dots\). If some larger prime \(q\) appears while a smaller prime \(p\lt q\) does not, replacing \(q\) by \(p\) leaves the divisor product unchanged and makes \(n\) smaller, so such a pattern cannot be optimal.
Second, the exponents may be assumed to be non-increasing:
$$a_1\ge a_2\ge a_3\ge \cdots \ge 1.$$
Indeed, if \(p\lt q\) but \(a_p \lt a_q\), then swapping those two exponents changes
$$p^{a_p}q^{a_q}$$
into
$$p^{a_q}q^{a_p},$$
which is smaller because the larger exponent is now attached to the smaller prime. The divisor product \(\prod(2a_i+1)\) is unchanged by the swap, so an optimal candidate must respect this monotonic ordering. This is the main invariant enforced by the recursive search.
A concrete example makes the divisor-count formula visible. Let \(n=6=2^1\cdot 3^1\). Then
$$n^2=36=2^2\cdot 3^2,$$
so
$$d(n^2)=(2\cdot 1+1)(2\cdot 1+1)=9.$$
Therefore the number of distinct solutions is
$$\frac{9+1}{2}=5.$$
The corresponding factor pairs of \(36\) are
$$ (1,36),\ (2,18),\ (3,12),\ (4,9),\ (6,6), $$
which produce
$$ (x,y)=(7,42),\ (8,24),\ (9,18),\ (10,15),\ (12,12). $$
This is exactly why the implementations track the divisor product \(\prod(2a_i+1)\): it counts solutions without ever constructing them explicitly.
After all the algebra, the real task is now clear: search through exponent vectors assigned to the consecutive primes
$$2,3,5,7,\dots,53,$$
maintain the current value of \(n\) and the current value of \(\prod(2a_i+1)\), and keep the smallest \(n\) whose divisor product reaches \(8{,}000{,}001\). The entire problem is therefore a depth-first search over a structured exponent space, not a search over solutions \((x,y)\).
The C++, Python, and Java implementations use the same recursive state: the index of the next prime, the largest exponent that the next prime is allowed to take, the current candidate value of \(n\), the current divisor product \(\prod(2a_i+1)\), and the best complete answer found so far.
The first prime receives a generous upper bound, and every later prime is restricted by the exponent chosen for the previous one. If the current exponent is \(e\), the recursive call passes \(e\) down as the next upper bound. That enforces the invariant \(a_1\ge a_2\ge \cdots\) automatically.
At each level the implementation multiplies the current \(n\) by the current prime one more time, so trying exponents \(1,2,3,\dots\) is done incrementally rather than recomputing powers from scratch. In parallel, it multiplies the running divisor product by \(2e+1\). As soon as that product reaches \(8{,}000{,}001\), the current \(n\) is a valid answer candidate.
The pruning rule is simple and effective: if the current \(n\) has already reached or exceeded the best answer found so far, the whole branch is discarded, because any deeper continuation would only make \(n\) larger. The languages differ only in numeric representation: C++ uses 128-bit integer arithmetic, Python uses arbitrary-precision integers, and Java uses big integers, but the search logic is the same.
The algorithm never enumerates the actual solution pairs \((x,y)\), so the meaningful cost measure is the number of recursive exponent states it visits. If that number is \(T\), then the running time is \(O(T)\), with only small arithmetic work per visited state.
The recursion depth is bounded by the number of primes supplied to the search, which here is 16. Thus the auxiliary space is \(O(16)\), or more generally \(O(k)\) for \(k\) explored primes. In practice the search is fast because the non-increasing exponent constraint removes most combinations, and the current-best cutoff prunes the remaining branches aggressively.
Gesucht ist die kleinste positive ganze Zahl \(n\), für die die diophantische Gleichung \( \frac{1}{x} + \frac{1}{y} = \frac{1}{n} \) mehr als \(4{,}000{,}000\) verschiedene positive ganzzahlige Lösungen besitzt. Die Lösung sucht nicht direkt über Paare \((x,y)\). Stattdessen wird die Gleichung in eine Teilerbedingung für \(n^2\) umgeformt, und danach wird über die Primfaktorzerlegung von \(n\) gesucht.
Dadurch wird aus einer Gleichung in zwei Variablen ein multiplikatives Optimierungsproblem. Sobald das Exponentenprofil von \(n\) feststeht, ist die Anzahl der Lösungen vollständig bestimmt, und übrig bleibt nur noch die Frage, welches kleinstmögliche \(n\) die geforderte Schranke überschreitet.
Der entscheidende Schritt besteht darin, die Kehrbruchgleichung in eine Faktorisierung von \(n^2\) zu verwandeln.
Ausgehend von
$$\frac{1}{x} + \frac{1}{y} = \frac{1}{n}$$
multipliziert man mit \(xyn\) und erhält
$$n(x+y)=xy.$$
Umstellen liefert
$$xy-nx-ny=0,$$
und nach Addition von \(n^2\) folgt
$$\boxed{(x-n)(y-n)=n^2.}$$
Jede positive Lösung entspricht also einer Faktorisierung \(uv=n^2\) mit
$$u=x-n,\qquad v=y-n,$$
und umgekehrt erzeugt jedes positive Faktorenpaar von \(n^2\) die Lösung
$$x=n+u,\qquad y=n+v.$$
Wenn geordnete Paare gezählt würden, gäbe es genau \(d(n^2)\) davon, denn jeder Teiler \(u\mid n^2\) bestimmt das Paar \((u,n^2/u)\). In der Aufgabe gelten jedoch \((x,y)\) und \((y,x)\) als dieselbe Lösung, solange sie nur vertauscht sind.
Da \(n^2\) ein Quadrat ist, gibt es genau einen mittleren Fall mit \(u=v=n\). Deshalb ist die Anzahl der verschiedenen positiven Lösungen
$$\boxed{N(n)=\frac{d(n^2)+1}{2}.}$$
Die Bedingung
$$N(n)\gt 4{,}000{,}000$$
ist also äquivalent zu
$$d(n^2)\ge 8{,}000{,}001.$$
Dass rechts eine ungerade Zahl steht, ist folgerichtig: Weil alle Exponenten in \(n^2\) gerade sind, ist \(d(n^2)\) immer ungerade.
Schreibt man
$$n=\prod_{i=1}^{k} p_i^{a_i},$$
dann gilt
$$n^2=\prod_{i=1}^{k} p_i^{2a_i},$$
und damit
$$d(n^2)=\prod_{i=1}^{k}(2a_i+1).$$
Das ursprüngliche Problem ist damit gleichbedeutend mit der Suche nach dem kleinsten
$$n=\prod p_i^{a_i}$$
mit
$$\prod (2a_i+1)\ge 8{,}000{,}001.$$
Die Variablen \(x\) und \(y\) verschwinden also vollständig; alles hängt nur noch vom Exponentenvektor \((a_1,a_2,\dots)\) ab.
Damit \(n\) minimal wird, muss die Zerlegung eine sehr starre Form haben.
Erstens müssen die verwendeten Primzahlen ein Anfangsstück \(2,3,5,\dots\) bilden. Wenn eine größere Primzahl \(q\) verwendet wird, eine kleinere \(p\lt q\) aber nicht, dann kann man \(q\) durch \(p\) ersetzen, ohne das Teilerprodukt zu ändern, und erhält ein kleineres \(n\). Ein optimales \(n\) kann daher keine Lücke in den verwendeten Primzahlen haben.
Zweitens dürfen die Exponenten als nicht steigend angenommen werden:
$$a_1\ge a_2\ge a_3\ge \cdots \ge 1.$$
Falls nämlich \(p\lt q\), aber \(a_p \lt a_q\) gilt, dann verwandelt ein Vertauschen der Exponenten
$$p^{a_p}q^{a_q}$$
in
$$p^{a_q}q^{a_p},$$
und diese Zahl ist kleiner, weil der größere Exponent nun auf der kleineren Primzahl liegt. Das Produkt \(\prod(2a_i+1)\) ändert sich dabei nicht. Genau diese Monotonie ist die zentrale Invariante der rekursiven Suche.
Ein kleines Beispiel macht die Formel anschaulich. Setze \(n=6=2^1\cdot 3^1\). Dann ist
$$n^2=36=2^2\cdot 3^2,$$
also
$$d(n^2)=(2\cdot 1+1)(2\cdot 1+1)=9.$$
Damit beträgt die Zahl der verschiedenen Lösungen
$$\frac{9+1}{2}=5.$$
Die zugehörigen Faktorenpaare von \(36\) sind
$$ (1,36),\ (2,18),\ (3,12),\ (4,9),\ (6,6), $$
und daraus entstehen die Lösungen
$$ (x,y)=(7,42),\ (8,24),\ (9,18),\ (10,15),\ (12,12). $$
Genau deshalb verfolgt die Implementierung das Produkt \(\prod(2a_i+1)\): Es zählt die Lösungen, ohne sie einzeln aufzubauen.
Nach dieser Umformung ist die Aufgabe nicht mehr „Finde viele Paare \((x,y)\)“, sondern: Durchsuche Exponentenvektoren auf den aufeinanderfolgenden Primzahlen
$$2,3,5,7,\dots,53,$$
verfolge dabei den aktuellen Wert von \(n\) und von \(\prod(2a_i+1)\), und behalte das kleinste \(n\), dessen Teilerprodukt mindestens \(8{,}000{,}001\) erreicht. Genau dieses strukturierte Suchproblem lösen alle drei Implementierungen.
Die Implementierungen in C++, Python und Java benutzen denselben rekursiven Zustand: den Index der nächsten Primzahl, den größten noch erlaubten Exponenten für diese Primzahl, den aktuellen Kandidatenwert \(n\), das laufende Produkt \(\prod(2a_i+1)\) und den bisher besten vollständigen Kandidaten.
Für die erste Primzahl wird eine großzügige Obergrenze gesetzt; jede spätere Primzahl darf höchstens den Exponenten der vorherigen bekommen. Wenn der aktuelle Exponent \(e\) gewählt wird, wird \(e\) als neue Schranke an den nächsten Rekursionsschritt weitergegeben. Dadurch wird \(a_1\ge a_2\ge \cdots\) automatisch erzwungen.
Auf jeder Ebene wird \(n\) inkrementell mit der aktuellen Primzahl multipliziert. So entstehen die Exponenten \(1,2,3,\dots\), ohne Potenzen jedes Mal neu auszurechnen. Parallel dazu wird das laufende Teilerprodukt mit \(2e+1\) multipliziert. Sobald dieses Produkt mindestens \(8{,}000{,}001\) erreicht, ist der aktuelle Wert von \(n\) ein gültiger Kandidat.
Die Abschneideregel ist einfach: Sobald das aktuelle \(n\) bereits größer oder gleich dem besten bisher bekannten Kandidaten ist, wird der gesamte Teilbaum verworfen, denn jede Fortsetzung würde \(n\) nur noch weiter vergrößern. Unterschiede zwischen den Sprachen gibt es nur bei den Zahltypen: C++ verwendet 128-Bit-Arithmetik, Python beliebig große ganze Zahlen und Java BigInteger.
Das Verfahren enumeriert niemals die eigentlichen Lösungspaare \((x,y)\). Sinnvoll ist daher nur die Anzahl der besuchten Rekursionszustände als Kostenmaß. Bezeichnet man sie mit \(T\), so ist die Laufzeit \(O(T)\), wobei pro Zustand nur wenig Arithmetik anfällt.
Die Rekursionstiefe ist durch die Anzahl der vorgegebenen Primzahlen beschränkt; hier sind das 16. Damit liegt der zusätzliche Speicher bei \(O(16)\), allgemein also bei \(O(k)\) für \(k\) berücksichtigte Primzahlen. Praktisch ist die Suche schnell, weil die Monotonie der Exponenten den Raum drastisch verkleinert und der Vergleich mit dem bisher besten Kandidaten den Rest aggressiv abschneidet.
Aranan şey, \( \frac{1}{x} + \frac{1}{y} = \frac{1}{n} \) denkleminin \(4{,}000{,}000\)'dan fazla farklı pozitif tamsayı çözümü olduğu en küçük pozitif tamsayı \(n\)'dir. Başarılı yaklaşım \((x,y)\) çiftlerini doğrudan aramaz. Bunun yerine denklemi \(n^2\) üzerindeki bir bölen sayısı koşuluna dönüştürür ve ardından \(n\)'in asal çarpan üsleri üzerinde arama yapar.
Böylece iki değişkenli bir Diofant denklemi, çarpımsal bir minimizasyon problemine indirgenir. \(n\)'in üs profili bilindiğinde çözüm sayısı da belirlenmiş olur; geriye yalnızca bu eşiği geçen en küçük \(n\)'yi bulmak kalır.
Ana fikir, ters kesir denkleminden \(n^2\)'nin çarpanlarına geçmektir.
Şuradan başlayalım:
$$\frac{1}{x} + \frac{1}{y} = \frac{1}{n}.$$
Her iki tarafı \(xyn\) ile çarpınca
$$n(x+y)=xy$$
elde edilir. Düzenlersek
$$xy-nx-ny=0,$$
ve her iki tarafa \(n^2\) eklersek
$$\boxed{(x-n)(y-n)=n^2}$$
sonucuna ulaşırız. Demek ki her pozitif çözüm,
$$u=x-n,\qquad v=y-n$$
olacak şekilde \(uv=n^2\) çarpanlaşmasına karşılık gelir. Tersine, \(n^2\)'nin her pozitif çarpan çifti
$$x=n+u,\qquad y=n+v$$
şeklinde bir çözüm üretir.
Eğer sıralı çiftler sayılsaydı, \(u\mid n^2\) olan her bölen tam olarak bir \((u,n^2/u)\) çifti vereceği için toplam sayı \(d(n^2)\) olurdu.
Fakat soruda farklı çözümler sayılıyor; yani \((x,y)\) ile \((y,x)\) aynı çözüm kabul ediliyor. \(n^2\) tam kare olduğu için ortada \(u=v=n\) olan tek bir simetrik durum vardır. Bu yüzden farklı pozitif çözüm sayısı
$$\boxed{N(n)=\frac{d(n^2)+1}{2}}$$
olur. Dolayısıyla
$$N(n)\gt 4{,}000{,}000$$
koşulu
$$d(n^2)\ge 8{,}000{,}001$$
ile aynıdır. Buradaki tek sayılı eşik tesadüf değildir; \(n^2\)'deki bütün üsler çift olduğu için \(d(n^2)\) her zaman tektir.
\(n\)'i
$$n=\prod_{i=1}^{k} p_i^{a_i}$$
şeklinde yazalım. O zaman
$$n^2=\prod_{i=1}^{k} p_i^{2a_i},$$
dolayısıyla
$$d(n^2)=\prod_{i=1}^{k}(2a_i+1).$$
Yani asıl problem,
$$n=\prod p_i^{a_i}$$
biçimindeki en küçük sayıyı,
$$\prod (2a_i+1)\ge 8{,}000{,}001$$
koşulu altında bulmaya dönüşür. Bu noktadan sonra \(x\) ve \(y\) tamamen ortadan kalkar; her şey üs vektörü \((a_1,a_2,\dots)\) ile belirlenir.
En küçük \(n\)'yi bulmak için üslerin çok belirli bir düzen izlemesi gerekir.
Önce kullanılan asalların bir başlangıç parçası olması gerekir: \(2,3,5,\dots\). Eğer daha büyük bir asal \(q\) kullanılırken daha küçük bir asal \(p\lt q\) hiç kullanılmıyorsa, \(q\) yerine \(p\) koymak bölen çarpımını değiştirmez ama \(n\)'yi küçültür. Demek ki en iyi çözümde asal boşluğu olamaz.
İkinci olarak üsler azalmayan değil, küçük asallardan büyüklere doğru azalmayanın tersi, yani azalan biçimde alınabilir:
$$a_1\ge a_2\ge a_3\ge \cdots \ge 1.$$
Gerçekten \(p\lt q\) iken \(a_p \lt a_q\) olsaydı,
$$p^{a_p}q^{a_q}$$
ifadesindeki üsleri yer değiştirip
$$p^{a_q}q^{a_p}$$
elde etmek sayıyı küçültürdü; çünkü büyük üs küçük asala taşınmış olurdu. Buna karşılık \(\prod(2a_i+1)\) değişmez. Bu nedenle optimal aday mutlaka bu monotonluk kuralını sağlamalıdır. Kodun koruduğu temel invariant budur.
Küçük bir örnek formülü netleştirir. \(n=6=2^1\cdot 3^1\) olsun. O zaman
$$n^2=36=2^2\cdot 3^2,$$
ve
$$d(n^2)=(2\cdot 1+1)(2\cdot 1+1)=9$$
olur. Dolayısıyla farklı çözüm sayısı
$$\frac{9+1}{2}=5$$
çıkar. \(36\)'nın ilgili çarpan çiftleri
$$ (1,36),\ (2,18),\ (3,12),\ (4,9),\ (6,6) $$
olduğundan çözümler
$$ (x,y)=(7,42),\ (8,24),\ (9,18),\ (10,15),\ (12,12) $$
şeklindedir. Uygulamanın \(\prod(2a_i+1)\) değerini izlemesinin nedeni tam olarak budur: çözümleri tek tek üretmeden sayıyı verir.
Bütün cebir bittikten sonra problem artık iki değişkenli denklem çözmek değildir. Yapılması gereken şey,
$$2,3,5,7,\dots,53$$
asallarına atanmış üs vektörleri arasında derinlik öncelikli gezinmek, her adımda \(n\)'in güncel değerini ve \(\prod(2a_i+1)\) çarpımını tutmak, sonra da bu çarpımı \(8{,}000{,}001\)'e ulaştıran en küçük \(n\)'yi seçmektir.
C++, Python ve Java uygulamaları aynı özyinelemeli durumu taşır: sıradaki asalın indeksi, bu asal için izin verilen en büyük üs, şu ana kadarki aday \(n\), güncel bölen çarpımı \(\prod(2a_i+1)\) ve şimdiye kadar bulunan en iyi tam aday.
İlk asal için geniş bir üst sınır verilir; sonraki her asalın üssü ise bir önceki seçimin üstüne çıkamaz. Eğer mevcut seviyede \(e\) seçilmişse, bir sonraki çağrıya yeni üst sınır olarak yine \(e\) gönderilir. Böylece \(a_1\ge a_2\ge \cdots\) koşulu otomatik biçimde uygulanır.
Her seviyede aday \(n\), ilgili asal ile tekrar tekrar çarpılarak güncellenir; böylece \(1,2,3,\dots\) üslerini denemek için kuvvetler yeniden hesaplanmaz. Aynı anda bölen çarpımı da \(2e+1\) ile güncellenir. Bu çarpım \(8{,}000{,}001\)'e ulaşır ulaşmaz eldeki \(n\) geçerli bir aday olur.
Budama kuralı basit ama güçlüdür: mevcut \(n\), bilinen en iyi cevaba erişmiş ya da onu geçmişse o dal tamamen bırakılır; çünkü aşağı doğru devam etmek yalnızca daha büyük sayılar üretecektir. Diller arasındaki fark yalnızca sayı temsillerindedir: C++ 128 bit, Python keyfi hassasiyetli tamsayılar, Java ise büyük tamsayılar kullanır.
Algoritma gerçek çözüm çiftlerini \((x,y)\) hiç üretmez. Bu yüzden anlamlı maliyet ölçüsü, ziyaret edilen özyinelemeli üs durumlarının sayısıdır. Bu sayıya \(T\) dersek çalışma süresi \(O(T)\) olur; her durum başına yapılan aritmetik küçüktür.
Özyineleme derinliği aramaya verilen asal sayısıyla sınırlıdır; burada bu sayı 16'dır. Dolayısıyla ek bellek \(O(16)\), genel yazımla \(O(k)\) düzeyindedir. Pratikte arama hızlıdır; çünkü azalan üs koşulu kombinasyonların çoğunu baştan yok eder, mevcut en iyi adayla yapılan karşılaştırma da kalan dalları sert biçimde budar.
Se busca el menor entero positivo \(n\) para el cual la ecuación diofántica \( \frac{1}{x} + \frac{1}{y} = \frac{1}{n} \) tiene más de \(4{,}000{,}000\) soluciones positivas distintas. El enfoque eficaz no explora directamente los pares \((x,y)\). En su lugar, transforma la ecuación en una condición sobre el número de divisores de \(n^2\) y después busca sobre la factorización prima de \(n\).
Esa reformulación convierte una ecuación en dos variables en un problema multiplicativo de optimización. Una vez fijado el perfil de exponentes de \(n\), el número de soluciones queda determinado, y solo falta encontrar el menor \(n\) cuyo perfil obligue a superar el umbral pedido.
La idea central es convertir la ecuación con recíprocos en una factorización de \(n^2\).
Partimos de
$$\frac{1}{x} + \frac{1}{y} = \frac{1}{n}.$$
Multiplicando por \(xyn\) obtenemos
$$n(x+y)=xy.$$
Reordenando:
$$xy-nx-ny=0,$$
y al sumar \(n^2\) a ambos lados aparece
$$\boxed{(x-n)(y-n)=n^2.}$$
Por tanto, toda solución positiva corresponde a una factorización \(uv=n^2\) con
$$u=x-n,\qquad v=y-n,$$
y, recíprocamente, cada par de factores positivos de \(n^2\) produce la solución
$$x=n+u,\qquad y=n+v.$$
Si contáramos pares ordenados, habría exactamente \(d(n^2)\) de ellos, porque cada divisor \(u\mid n^2\) determina el par \((u,n^2/u)\).
Pero el problema cuenta soluciones distintas, así que \((x,y)\) y \((y,x)\) se identifican. Como \(n^2\) es un cuadrado perfecto, existe exactamente una factorización central con \(u=v=n\). Por ello, el número de soluciones positivas distintas vale
$$\boxed{N(n)=\frac{d(n^2)+1}{2}.}$$
En consecuencia, la exigencia
$$N(n)\gt 4{,}000{,}000$$
equivale a
$$d(n^2)\ge 8{,}000{,}001.$$
El umbral impar es natural: como todos los exponentes de \(n^2\) son pares, \(d(n^2)\) siempre es impar.
Escribamos
$$n=\prod_{i=1}^{k} p_i^{a_i}.$$
Entonces
$$n^2=\prod_{i=1}^{k} p_i^{2a_i},$$
y por la fórmula del número de divisores
$$d(n^2)=\prod_{i=1}^{k}(2a_i+1).$$
Así, el problema original se convierte en hallar el menor número de la forma
$$n=\prod p_i^{a_i}$$
tal que
$$\prod (2a_i+1)\ge 8{,}000{,}001.$$
En este punto \(x\) e \(y\) ya no aparecen: todo queda codificado por el vector de exponentes \((a_1,a_2,\dots)\).
Para minimizar \(n\), la estructura de los exponentes no es arbitraria.
Primero, los primos usados deben formar un prefijo \(2,3,5,\dots\). Si apareciera un primo grande \(q\) mientras un primo menor \(p\lt q\) estuviera ausente, sustituir \(q\) por \(p\) dejaría igual el producto de divisores y produciría un \(n\) menor. Por lo tanto, una solución mínima no puede saltarse primos pequeños.
Segundo, los exponentes pueden suponerse no crecientes:
$$a_1\ge a_2\ge a_3\ge \cdots \ge 1.$$
En efecto, si \(p\lt q\) pero \(a_p \lt a_q\), entonces intercambiar los exponentes transforma
$$p^{a_p}q^{a_q}$$
en
$$p^{a_q}q^{a_p},$$
que es menor porque el exponente mayor pasa al primo más pequeño. El producto \(\prod(2a_i+1)\) no cambia. Esa monotonía es precisamente la invariante que impone la búsqueda recursiva.
Un ejemplo concreto aclara la fórmula. Tomemos \(n=6=2^1\cdot 3^1\). Entonces
$$n^2=36=2^2\cdot 3^2,$$
de modo que
$$d(n^2)=(2\cdot 1+1)(2\cdot 1+1)=9.$$
El número de soluciones distintas es por tanto
$$\frac{9+1}{2}=5.$$
Los pares de factores de \(36\) son
$$ (1,36),\ (2,18),\ (3,12),\ (4,9),\ (6,6), $$
y producen
$$ (x,y)=(7,42),\ (8,24),\ (9,18),\ (10,15),\ (12,12). $$
Eso muestra exactamente por qué las implementaciones siguen \(\prod(2a_i+1)\) en vez de construir soluciones una por una.
Tras la transformación algebraica, el reto ya no es resolver la ecuación en dos variables, sino explorar vectores de exponentes asignados a los primos consecutivos
$$2,3,5,7,\dots,53,$$
mantener el valor actual de \(n\) y de \(\prod(2a_i+1)\), y conservar el menor \(n\) cuyo producto de divisores alcance \(8{,}000{,}001\). Ese es exactamente el espacio que recorren las implementaciones.
Las implementaciones en C++, Python y Java mantienen el mismo estado recursivo: el índice del siguiente primo, el mayor exponente permitido para ese primo, el valor actual de \(n\), el producto acumulado \(\prod(2a_i+1)\) y la mejor respuesta completa encontrada hasta ese momento.
Al primer primo se le da una cota superior amplia, y cada primo posterior queda limitado por el exponente elegido para el primo anterior. Si en un nivel se elige \(e\), la llamada recursiva siguiente recibe \(e\) como nueva cota. Así se impone automáticamente la condición \(a_1\ge a_2\ge \cdots\).
En cada nivel, el valor de \(n\) se actualiza multiplicando una vez más por el primo actual, de modo que los exponentes \(1,2,3,\dots\) se prueban de forma incremental. A la vez, el producto de divisores se multiplica por \(2e+1\). En cuanto ese producto llega a \(8{,}000{,}001\), el \(n\) actual ya es un candidato válido.
La poda es sencilla y potente: si el \(n\) actual ya ha alcanzado o superado la mejor respuesta conocida, se descarta toda esa rama, porque cualquier continuación solo puede aumentar \(n\). Las diferencias entre lenguajes están solo en el tipo numérico: C++ usa enteros de 128 bits, Python enteros de precisión arbitraria y Java enteros grandes.
El algoritmo nunca enumera las soluciones reales \((x,y)\), así que la medida de coste relevante es el número de estados recursivos visitados. Si ese número es \(T\), el tiempo total es \(O(T)\), con muy poco trabajo aritmético por estado.
La profundidad de la recursión está acotada por la cantidad de primos ofrecidos a la búsqueda, que aquí es 16. Por tanto, el espacio auxiliar es \(O(16)\), o de forma más general \(O(k)\) para \(k\) primos explorados. En la práctica la búsqueda es rápida porque la restricción de exponentes no crecientes elimina la mayor parte del árbol y la poda por mejor candidato corta con agresividad lo que queda.
题目要求找出最小的正整数 \(n\)，使得丢番图方程 \( \frac{1}{x} + \frac{1}{y} = \frac{1}{n} \) 的不同正整数解超过 \(4{,}000{,}000\) 个。有效的解法并不直接枚举 \((x,y)\)；它先把方程改写成关于 \(n^2\) 的因子计数问题，然后只在 \(n\) 的素因子指数上做搜索。
这样一来，原本看似是二元方程的题目，实质上变成了一个乘法结构下的最优化问题。只要确定了 \(n\) 的指数向量，解的个数就完全确定；剩下的任务只是找到满足门槛的最小 \(n\)。
整道题的关键，是把倒数方程改写成 \(n^2\) 的因式分解。
从
$$\frac{1}{x} + \frac{1}{y} = \frac{1}{n}$$
出发，两边同时乘以 \(xyn\)，得到
$$n(x+y)=xy.$$
移项后有
$$xy-nx-ny=0,$$
再在两边同时加上 \(n^2\)，就得到
$$\boxed{(x-n)(y-n)=n^2.}$$
这说明每一个正整数解都对应于 \(n^2\) 的一个正因子分解 \(uv=n^2\)，其中
$$u=x-n,\qquad v=y-n.$$
反过来，\(n^2\) 的每一组正因子对又都会给出
$$x=n+u,\qquad y=n+v$$
这样一组解。
如果把有序对全部区分开，那么每个除数 \(u\mid n^2\) 都对应一个因子对 \((u,n^2/u)\)，因此有序计数恰好是 \(d(n^2)\)，这里 \(d\) 表示约数函数。
但题目统计的是不同解，所以 \((x,y)\) 和 \((y,x)\) 不能重复计算。由于 \(n^2\) 是完全平方数，正中间会有唯一一个对角情形 \(u=v=n\)。于是不同正整数解的数量为
$$\boxed{N(n)=\frac{d(n^2)+1}{2}.}$$
因此条件
$$N(n)\gt 4{,}000{,}000$$
等价于
$$d(n^2)\ge 8{,}000{,}001.$$
这里出现奇数门槛并不是偶然，因为 \(n^2\) 的所有素因子指数都是偶数，所以 \(d(n^2)\) 一定是奇数。
设
$$n=\prod_{i=1}^{k} p_i^{a_i}.$$
那么
$$n^2=\prod_{i=1}^{k} p_i^{2a_i},$$
从而
$$d(n^2)=\prod_{i=1}^{k}(2a_i+1).$$
于是原题等价于：在所有形如
$$n=\prod p_i^{a_i}$$
的正整数中，找出满足
$$\prod (2a_i+1)\ge 8{,}000{,}001$$
的最小者。走到这一步以后，\(x\) 和 \(y\) 已经完全消失，整个问题只由指数向量 \((a_1,a_2,\dots)\) 决定。
为了让 \(n\) 最小，指数的布局不能随意选择。
第一，使用到的素数一定是连续的前缀 \(2,3,5,\dots\)。如果某个较大的素数 \(q\) 被用了，而较小的素数 \(p\lt q\) 却完全没用，那么把 \(q\) 换成 \(p\) 不会改变 \(\prod(2a_i+1)\)，却会让 \(n\) 变小，所以那样的结构不可能是最优解。
第二，指数可以假设满足
$$a_1\ge a_2\ge a_3\ge \cdots \ge 1.$$
理由也很直接：如果 \(p\lt q\)，却出现 \(a_p \lt a_q\)，那么把这两个指数互换，就会把
$$p^{a_p}q^{a_q}$$
变成
$$p^{a_q}q^{a_p},$$
而后者更小，因为更大的指数被放到了更小的素数上。与此同时，\(\prod(2a_i+1)\) 完全不变。所以任何极小候选都可以写成指数单调不增的形式。这正是递归搜索始终维持的核心不变量。
用一个小例子可以把公式看得更清楚。令 \(n=6=2^1\cdot 3^1\)。则
$$n^2=36=2^2\cdot 3^2,$$
所以
$$d(n^2)=(2\cdot 1+1)(2\cdot 1+1)=9.$$
于是不同解的个数是
$$\frac{9+1}{2}=5.$$
\(36\) 的相关因子对为
$$ (1,36),\ (2,18),\ (3,12),\ (4,9),\ (6,6), $$
对应的解就是
$$ (x,y)=(7,42),\ (8,24),\ (9,18),\ (10,15),\ (12,12). $$
这个例子正好说明了为什么实现程序只需要追踪 \(\prod(2a_i+1)\)，而不需要显式生成所有解对。
经过上述变形以后，题目真正变成了这样：在连续素数
$$2,3,5,7,\dots,53$$
上枚举满足单调条件的指数向量，维护当前的 \(n\) 和当前的 \(\prod(2a_i+1)\)，并记录所有使该乘积达到 \(8{,}000{,}001\) 的候选中最小的那个。也就是说，程序搜索的不是 \((x,y)\) 空间，而是指数向量空间。
C++、Python 和 Java 三个实现维护的是同一组递归状态：下一个要处理的素数位置、该素数允许使用的最大指数、当前候选值 \(n\)、当前的约数乘积 \(\prod(2a_i+1)\)，以及到目前为止找到的最优完整答案。
第一个素数会给一个比较宽松的初始上界，而后续每个素数的指数上界都来自前一个已选指数。如果这一层选择了指数 \(e\)，下一层就把 \(e\) 当作新的上界传下去，于是 \(a_1\ge a_2\ge \cdots\) 会被自动保证。
在每一层里，程序通过不断再乘一次当前素数来尝试指数 \(1,2,3,\dots\)，因此不需要重复计算幂。同时，当前的约数乘积会乘上 \(2e+1\)。只要这个乘积达到 \(8{,}000{,}001\)，当前 \(n\) 就已经是一个合法候选。
剪枝规则非常直接：如果当前 \(n\) 已经达到或超过已知最优答案，那么整条分支都会被放弃，因为继续向下只会使 \(n\) 更大。三个语言版本的差别只在整数表示上：C++ 使用 128 位整数，Python 使用任意精度整数，Java 使用大整数；搜索逻辑本身完全一致。
算法从不真正枚举所有解对 \((x,y)\)，因此合理的成本度量是它访问了多少个递归状态。若这个数量记为 \(T\)，则总时间复杂度就是 \(O(T)\)，每个状态只做少量乘法和比较。
递归深度不会超过提供给搜索的素数个数，这里是 16 个，因此额外空间为 \(O(16)\)，更一般地说是 \(O(k)\)。在实际运行中，这个搜索很快，因为“指数单调不增”的约束已经砍掉了绝大多数组合，而“当前值不优于已知最优答案”又会继续强力剪枝。
Нужно найти наименьшее положительное целое \(n\), для которого диофантово уравнение \( \frac{1}{x} + \frac{1}{y} = \frac{1}{n} \) имеет более \(4{,}000{,}000\) различных положительных целочисленных решений. Эффективный подход не перебирает пары \((x,y)\) напрямую. Вместо этого уравнение преобразуется в условие на число делителей \(n^2\), а затем поиск ведется по разложению \(n\) на простые множители.
После такого преобразования задача из уравнения в двух переменных превращается в мультипликативную задачу минимизации. Как только известен вектор показателей в разложении \(n\), число решений полностью определено, и остается лишь найти минимальное \(n\), для которого это число превышает требуемый порог.
Главный шаг состоит в том, чтобы превратить уравнение с обратными величинами в факторизацию числа \(n^2\).
Начнем с равенства
$$\frac{1}{x} + \frac{1}{y} = \frac{1}{n}.$$
Умножим обе части на \(xyn\):
$$n(x+y)=xy.$$
Переносим слагаемые:
$$xy-nx-ny=0,$$
и после прибавления \(n^2\) получаем
$$\boxed{(x-n)(y-n)=n^2.}$$
Значит, каждое положительное решение соответствует разложению \(uv=n^2\), где
$$u=x-n,\qquad v=y-n,$$
а каждое положительное разложение \(n^2\) на пару множителей, наоборот, дает
$$x=n+u,\qquad y=n+v.$$
Если бы мы считали упорядоченные пары, то их было бы ровно \(d(n^2)\), потому что каждый делитель \(u\mid n^2\) однозначно задает пару \((u,n^2/u)\).
Но в задаче решения считаются без учета перестановки \(x\) и \(y\). Поскольку \(n^2\) является квадратом, существует ровно один центральный случай \(u=v=n\). Поэтому число различных положительных решений равно
$$\boxed{N(n)=\frac{d(n^2)+1}{2}.}$$
Следовательно, условие
$$N(n)\gt 4{,}000{,}000$$
равносильно
$$d(n^2)\ge 8{,}000{,}001.$$
Порог получается нечетным не случайно: все показатели в \(n^2\) четные, а значит \(d(n^2)\) всегда нечетно.
Пусть
$$n=\prod_{i=1}^{k} p_i^{a_i}.$$
Тогда
$$n^2=\prod_{i=1}^{k} p_i^{2a_i},$$
и формула для числа делителей принимает вид
$$d(n^2)=\prod_{i=1}^{k}(2a_i+1).$$
Итак, исходная задача эквивалентна поиску наименьшего числа вида
$$n=\prod p_i^{a_i}$$
при условии
$$\prod (2a_i+1)\ge 8{,}000{,}001.$$
После этого \(x\) и \(y\) полностью исчезают из формул; все сводится к вектору показателей \((a_1,a_2,\dots)\).
Чтобы \(n\) было минимальным, структура показателей должна быть строго организована.
Во-первых, использованные простые обязаны образовывать начальный отрезок \(2,3,5,\dots\). Если некоторый больший простой \(q\) используется, а меньший \(p\lt q\) нет, то замена \(q\) на \(p\) оставит произведение \(\prod(2a_i+1)\) тем же, но уменьшит \(n\). Значит, в минимальном решении пропусков среди использованных простых быть не может.
Во-вторых, показатели можно считать невозрастающими:
$$a_1\ge a_2\ge a_3\ge \cdots \ge 1.$$
Действительно, если \(p\lt q\), но \(a_p \lt a_q\), то перестановка этих показателей заменяет
$$p^{a_p}q^{a_q}$$
на
$$p^{a_q}q^{a_p},$$
а новое число меньше, потому что больший показатель прикреплен к меньшему простому. При этом произведение \(\prod(2a_i+1)\) не меняется. Именно это условие монотонности и поддерживает рекурсивный перебор.
Небольшой пример хорошо показывает суть формулы. Возьмем \(n=6=2^1\cdot 3^1\). Тогда
$$n^2=36=2^2\cdot 3^2,$$
и потому
$$d(n^2)=(2\cdot 1+1)(2\cdot 1+1)=9.$$
Число различных решений равно
$$\frac{9+1}{2}=5.$$
Соответствующие пары делителей числа \(36\) таковы:
$$ (1,36),\ (2,18),\ (3,12),\ (4,9),\ (6,6), $$
и они дают решения
$$ (x,y)=(7,42),\ (8,24),\ (9,18),\ (10,15),\ (12,12). $$
Этот пример ровно объясняет, почему реализации отслеживают произведение \(\prod(2a_i+1)\), а не строят сами пары решений.
После преобразования задача уже не про поиск решений уравнения в двух переменных. Она становится такой: перебрать допустимые векторы показателей на последовательных простых
$$2,3,5,7,\dots,53,$$
поддерживать текущее значение \(n\) и текущее произведение \(\prod(2a_i+1)\), а затем выбрать наименьшее \(n\), для которого это произведение достигает \(8{,}000{,}001\). Именно это и делает поиск во всех трех реализациях.
Реализации на C++, Python и Java поддерживают одно и то же рекурсивное состояние: индекс следующего простого, максимальный показатель, разрешенный для этого простого, текущее значение кандидата \(n\), накопленное произведение \(\prod(2a_i+1)\) и лучший полный ответ, найденный к данному моменту.
Для первого простого задается достаточно широкая верхняя граница, а для каждого следующего простого максимальный показатель ограничивается тем, который был выбран на предыдущем шаге. Если на текущем уровне выбран показатель \(e\), именно \(e\) передается дальше как новый предел. Так автоматически соблюдается условие \(a_1\ge a_2\ge \cdots\).
На каждом уровне алгоритм еще раз умножает текущее \(n\) на текущий простой, поэтому показатели \(1,2,3,\dots\) перебираются наращиванием, без повторного вычисления степеней. Параллельно накопленное произведение умножается на \(2e+1\). Как только это произведение достигает \(8{,}000{,}001\), текущее \(n\) становится допустимым кандидатом.
Правило отсечения очень простое: если текущее \(n\) уже не меньше лучшего найденного ответа, то вся ветвь отбрасывается, потому что любое продолжение только увеличит число. Различия между языками касаются лишь числового типа: C++ использует 128-битные целые, Python целые произвольной точности, Java большие целые.
Алгоритм никогда не перечисляет сами пары решений \((x,y)\), поэтому разумная оценка стоимости выражается через число посещенных рекурсивных состояний. Если обозначить это число через \(T\), то время работы равно \(O(T)\), а на каждое состояние приходится лишь небольшое количество арифметики.
Глубина рекурсии ограничена числом простых, переданных в поиск; здесь их 16. Следовательно, дополнительная память имеет порядок \(O(16)\), а в общем виде \(O(k)\) для \(k\) рассматриваемых простых. На практике поиск выполняется быстро, потому что условие невозрастания показателей резко уменьшает пространство вариантов, а отсечение по текущему лучшему кандидату агрессивно убирает оставшиеся ветви.
المطلوب هو إيجاد أصغر عدد صحيح موجب \(n\) بحيث تمتلك المعادلة الديوفانتية \( \frac{1}{x} + \frac{1}{y} = \frac{1}{n} \) أكثر من \(4{,}000{,}000\) حل موجب متميز. المنهج الفعلي لا يبحث مباشرة في الأزواج \((x,y)\)، بل يحول المعادلة إلى شرط يتعلق بعدد قواسم \(n^2\)، ثم يجري البحث على تحليل \(n\) إلى عوامل أولية.
بهذا التحويل تنتقل المسألة من معادلة بمتغيرين إلى مسألة تحسين ضربي. ما إن نعرف متجه أسس العوامل الأولية في \(n\) حتى يصبح عدد الحلول معلومًا بالكامل، ويبقى فقط إيجاد أصغر \(n\) يحقق حد الحلول المطلوب.
الفكرة الأساسية هي تحويل معادلة الكسور إلى تفكيك عددي للعدد \(n^2\).
نبدأ من
$$\frac{1}{x} + \frac{1}{y} = \frac{1}{n}.$$
بضرب الطرفين في \(xyn\) نحصل على
$$n(x+y)=xy.$$
وبإعادة الترتيب يصبح لدينا
$$xy-nx-ny=0,$$
ثم بإضافة \(n^2\) إلى الطرفين نحصل على
$$\boxed{(x-n)(y-n)=n^2.}$$
إذًا كل حل موجب يقابل تحليلًا من الشكل \(uv=n^2\) حيث
$$u=x-n,\qquad v=y-n,$$
وبالعكس فإن كل زوج قواسم موجب للعدد \(n^2\) يعطي الحل
$$x=n+u,\qquad y=n+v.$$
لو كنا نعد الأزواج المرتبة، لكان عددها بالضبط \(d(n^2)\)، لأن كل قاسم \(u\mid n^2\) يحدد الزوج \((u,n^2/u)\).
لكن المسألة تعد الحلول المتميزة فقط، أي إن \((x,y)\) و\((y,x)\) يمثلان الحل نفسه. وبما أن \(n^2\) مربع كامل، فهناك حالة مركزية وحيدة هي \(u=v=n\). لذلك يكون عدد الحلول الموجبة المتميزة
$$\boxed{N(n)=\frac{d(n^2)+1}{2}.}$$
ومن ثم فإن الشرط
$$N(n)\gt 4{,}000{,}000$$
يكافئ
$$d(n^2)\ge 8{,}000{,}001.$$
وكون الحد المطلوب عددًا فرديًا ليس مصادفة، لأن جميع الأسس في \(n^2\) زوجية، وبالتالي فإن \(d(n^2)\) فردي دائمًا.
لنكتب
$$n=\prod_{i=1}^{k} p_i^{a_i}.$$
عندئذ
$$n^2=\prod_{i=1}^{k} p_i^{2a_i},$$
ومن ثم
$$d(n^2)=\prod_{i=1}^{k}(2a_i+1).$$
وهكذا تصبح المسألة الأصلية هي: ابحث عن أصغر عدد من الشكل
$$n=\prod p_i^{a_i}$$
بحيث
$$\prod (2a_i+1)\ge 8{,}000{,}001.$$
بعد هذه الخطوة يختفي \(x\) و\(y\) تمامًا من الوصف، وتصبح المسألة كلها محكومة بمتجه الأسس \((a_1,a_2,\dots)\).
إذا أردنا تصغير \(n\)، فلا بد أن تكون بنية الأسس مقيدة جدًا.
أولًا، الأعداد الأولية المستخدمة يجب أن تشكل بادئة متتالية \(2,3,5,\dots\). فإذا استُخدم عدد أولي أكبر \(q\) بينما لم يُستخدم عدد أولي أصغر \(p\lt q\)، فإن استبدال \(q\) بـ \(p\) لا يغير الجداء \(\prod(2a_i+1)\) لكنه يصغر \(n\). لذلك لا يمكن أن يكون الحل الأدنى فيه فجوة بين الأوليات المستخدمة.
ثانيًا، يمكن دائمًا افتراض أن الأسس غير متزايدة:
$$a_1\ge a_2\ge a_3\ge \cdots \ge 1.$$
فإذا كان \(p\lt q\) لكن \(a_p \lt a_q\)، فإن تبديل الأسين يحول
$$p^{a_p}q^{a_q}$$
إلى
$$p^{a_q}q^{a_p},$$
وهو عدد أصغر لأن الأس الأكبر انتقل إلى العدد الأولي الأصغر. أما الجداء \(\prod(2a_i+1)\) فلا يتغير. هذه الرتابة هي الثابت الأساسي الذي يحافظ عليه البحث التعاودي.
مثال صغير يوضح الصيغة عمليًا. خذ \(n=6=2^1\cdot 3^1\). عندئذ
$$n^2=36=2^2\cdot 3^2,$$
ومن ثم
$$d(n^2)=(2\cdot 1+1)(2\cdot 1+1)=9.$$
لذلك يكون عدد الحلول المتميزة
$$\frac{9+1}{2}=5.$$
وأزواج قواسم \(36\) الموافقة هي
$$ (1,36),\ (2,18),\ (3,12),\ (4,9),\ (6,6), $$
فتنتج عنها الحلول
$$ (x,y)=(7,42),\ (8,24),\ (9,18),\ (10,15),\ (12,12). $$
وهذا يبين مباشرة لماذا تتبع التطبيقات الجداء \(\prod(2a_i+1)\) بدلًا من بناء الحلول واحدًا واحدًا.
بعد هذا الاشتقاق لم تعد المسألة هي إيجاد حلول للمعادلة في متغيرين، بل أصبحت: استكشف متجهات الأسس على الأعداد الأولية المتتالية
$$2,3,5,7,\dots,53,$$
واحتفظ بالقيمة الحالية لـ \(n\) وبالجداء الحالي \(\prod(2a_i+1)\)، ثم اختر أصغر \(n\) يصل بهذا الجداء إلى \(8{,}000{,}001\). هذا بالضبط هو الفضاء الذي تبحث فيه التطبيقات.
تنفذ تطبيقات C++ وPython وJava الفكرة نفسها باستخدام حالة تعاودية واحدة: فهرس العدد الأولي التالي، أكبر أس مسموح لهذا العدد، القيمة الحالية للمرشح \(n\)، الجداء الجاري \(\prod(2a_i+1)\)، وأفضل جواب كامل عُثر عليه حتى الآن.
يُعطى العدد الأولي الأول حد أعلى واسع، ثم يُقيد كل عدد أولي تال بالأس الذي اختير للعدد السابق. فإذا اختير في مستوى ما الأس \(e\)، يُمرر \(e\) إلى المستوى التالي بوصفه الحد الأعلى الجديد. وبهذا تُفرض العلاقة \(a_1\ge a_2\ge \cdots\) تلقائيًا.
في كل مستوى، تُحدَّث قيمة \(n\) بضربها مرة إضافية في العدد الأولي الحالي، لذلك تُجرَّب الأسس \(1,2,3,\dots\) بصورة تراكمية من دون إعادة حساب القوى من الصفر. وفي الوقت نفسه يُضرب الجداء الجاري في \(2e+1\). وما إن يصل هذا الجداء إلى \(8{,}000{,}001\)، يصبح \(n\) الحالي مرشحًا صالحًا.
قاعدة التقليم بسيطة وفعالة: إذا كانت قيمة \(n\) الحالية قد بلغت أو تجاوزت أفضل جواب معروف، تُستبعد تلك الشعبة كلها، لأن أي امتداد أعمق لن يؤدي إلا إلى زيادة \(n\). الاختلاف بين اللغات يقتصر على تمثيل الأعداد: C++ تستخدم أعدادًا صحيحة 128-بت، وPython تستخدم أعدادًا صحيحة غير محدودة الدقة، وJava تستخدم أعدادًا صحيحة كبيرة.
الخوارزمية لا تُعدّد أزواج الحلول \((x,y)\) نفسها، لذلك فإن مقياس الكلفة المناسب هو عدد حالات الأسس التعاودية التي تُزار أثناء البحث. إذا رمزنا إلى هذا العدد بـ \(T\)، فإن زمن التنفيذ يساوي \(O(T)\)، مع قدر صغير من الحساب في كل حالة.
عمق التعاود محدود بعدد الأعداد الأولية المزودة للبحث، وهو هنا 16. لذلك تكون الذاكرة الإضافية \(O(16)\)، أو بصورة عامة \(O(k)\) عند استخدام \(k\) أعداد أولية. عمليًا يكون البحث سريعًا لأن شرط الأسس غير المتزايدة يزيل معظم التركيبات، ثم يأتي القطع اعتمادًا على أفضل جواب حالي ليزيل ما تبقى من الفروع بقوة.