We seek the smallest positive integer \(n\) for which the Diophantine equation \(\frac{1}{x}+\frac{1}{y}=\frac{1}{n}\) has more than 1000 distinct solutions in positive integers when symmetric pairs are counted once, equivalently with \(x \ge y\).
A brute-force search over \(x\) and \(y\) is not the right viewpoint, because the interesting values of \(n\) are already large. The decisive observation is that the number of admissible pairs depends only on the prime factorization of \(n\), so the problem becomes an optimization over exponent vectors rather than a scan over denominator pairs.
The implementations follow a short but very powerful chain of ideas: convert the reciprocal equation into a factorization of \(n^2\), express the solution count through the divisor function, and then search for the smallest prime factorization whose divisor count is large enough.
Start with
$$\frac{1}{x}+\frac{1}{y}=\frac{1}{n}.$$
Multiplying by \(xyn\) gives
$$n(x+y)=xy.$$
Rearranging and completing the rectangle yields
$$xy-nx-ny=0 \quad\Longrightarrow\quad (x-n)(y-n)=n^2.$$
Thus every solution corresponds to positive integers \(a=x-n\) and \(b=y-n\) with \(ab=n^2\). Conversely, every factorization \(ab=n^2\) with \(a,b>0\) produces a solution \(x=n+a\), \(y=n+b\). Because the original equation is symmetric in \(x\) and \(y\), counting only solutions with \(x \ge y\) is exactly the same as counting each unordered factor pair of \(n^2\) once.
Let \(d(m)\) denote the number of positive divisors of \(m\). The factor pairs of \(n^2\) normally come in mirrored pairs \((a,b)\) and \((b,a)\). Since \(n^2\) is a perfect square, there is one central unpaired divisor \(a=b=n\). Therefore
$$\#\{\text{solutions with } x \ge y\}=\frac{d(n^2)+1}{2}.$$
The problem asks for more than 1000 solutions, so
$$\frac{d(n^2)+1}{2}>1000 \quad\Longleftrightarrow\quad d(n^2)>1999.$$
Because \(d(n^2)\) is odd for every square, this is equivalent to
$$d(n^2)\ge 2001.$$
This odd threshold is what the implementations test during the search.
If
$$n=\prod_{i=1}^{k} p_i^{a_i},$$
then
$$n^2=\prod_{i=1}^{k} p_i^{2a_i},$$
and the divisor function gives
$$d(n^2)=\prod_{i=1}^{k}(2a_i+1).$$
So the original Diophantine question becomes: find the smallest \(n=\prod p_i^{a_i}\) such that
$$\prod_{i=1}^{k}(2a_i+1)\ge 2001.$$
At this point the problem is no longer about solving for \(x\) and \(y\) directly. It is about selecting a good exponent vector \((a_1,a_2,\dots)\).
For a fixed multiset of exponents, the smallest possible value of \(n\) is obtained by assigning the largest exponent to the smallest prime, the next largest exponent to the next smallest prime, and so on. Indeed, if \(p<q\) but the exponents are arranged with \(a<b\), then
$$p^a q^b > p^b q^a,$$
so swapping those two exponents decreases \(n\) without changing \(d(n^2)\). Therefore an optimal factorization may always be written as
$$a_1 \ge a_2 \ge a_3 \ge \cdots \ge 1,$$
using the ascending primes \(2,3,5,7,\dots\). This monotonicity is the key invariant enforced by the depth-first search: once an exponent \(e\) is chosen for one prime, every later exponent is restricted to be at most \(e\).
Take \(n=4=2^2\). Then
$$d(n^2)=d(16)=2\cdot 2+1=5,$$
so the formula predicts
$$\frac{d(16)+1}{2}=\frac{5+1}{2}=3$$
distinct solutions. The unordered factor pairs of \(16\) are
$$16\cdot 1,\qquad 8\cdot 2,\qquad 4\cdot 4.$$
They yield
$$ (x,y)=(20,5),\qquad (12,6),\qquad (8,8), $$
which are exactly the three solutions with \(x \ge y\). This small example captures the full divisor-pair mechanism used in the general argument.
Using exponent 1 on the first seven primes already gives
$$n=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17=510510,$$
and then
$$d(n^2)=3^7=2187\ge 2001.$$
So a valid solution definitely exists below \(510510\). This does not identify the optimum yet, but it shows that only a short prefix of small primes matters and that once the search finds its first admissible candidate, pruning will become effective very quickly.
The C++, Python, and Java implementations all search over exponent vectors attached to the ascending primes \(2,3,5,7,\dots\). At each recursive call, the state contains four mathematical quantities: the next prime position, the largest exponent allowed for that prime, the current partial value of \(n\), and the current value of \(\prod (2a_i+1)\).
For the current prime, the implementation tries exponents \(1,2,\dots\) up to the permitted maximum. Multiplying by the prime updates the candidate \(n\), and choosing exponent \(e\) multiplies the divisor-count product by \(2e+1\). The recursion then continues to the next prime with the new exponent \(e\) as the next upper bound, which automatically preserves the non-increasing pattern \(a_1 \ge a_2 \ge \cdots\).
If the divisor-count product reaches \(2001\) or more, the current \(n\) is already a complete candidate and can update the best answer. There is no benefit in appending more primes, because any extra positive exponent would only make \(n\) larger.
The crucial pruning rule is simple: if the current partial \(n\) is already at least as large as the best solution found so far, the entire branch is abandoned. Since later recursion only multiplies by additional primes, no descendant of that state can improve the answer.
Because the recursion updates both \(n\) and \(\prod (2a_i+1)\) incrementally, each visited state requires only constant-time arithmetic. All three language versions implement the same mathematical search, just in different syntactic forms.
The natural complexity parameter here is the number \(T\) of exponent states visited by the depth-first search. Each state performs only a small amount of arithmetic, so the running time is \(O(T)\). There is no hidden scan over all \((x,y)\) pairs and no brute-force sweep over every integer up to the answer.
The memory usage is \(O(r)\), where \(r\) is the maximum recursion depth, i.e. the number of primes that receive a positive exponent on the current branch. For the threshold 1000, both \(T\) and \(r\) stay small because the non-increasing exponent invariant and the best-so-far pruning eliminate almost all of the nominal search tree. In practice the program finishes essentially instantly.
Gesucht ist die kleinste positive Zahl \(n\), für die die diophantische Gleichung \(\frac{1}{x}+\frac{1}{y}=\frac{1}{n}\) mehr als 1000 verschiedene Lösungen in positiven ganzen Zahlen besitzt, wobei symmetrische Paare nur einmal gezählt werden, also äquivalent mit \(x \ge y\).
Eine brute-force Suche über \(x\) und \(y\) ist hier die falsche Sichtweise, denn die interessanten Werte von \(n\) sind bereits zu groß. Entscheidend ist, dass die Anzahl der zulässigen Paare nur von der Primfaktorzerlegung von \(n\) abhängt. Das Problem wird also zu einer Optimierung über Exponentenvektoren und nicht zu einem Durchprobieren von Nennerpaaren.
Die Implementierungen folgen einer kurzen, aber sehr wirkungsvollen Kette von Ideen: Die Kehrwertgleichung wird in eine Faktorisierung von \(n^2\) umgeschrieben, die Anzahl der Lösungen wird über die Teilerfunktion ausgedrückt, und anschließend sucht man die kleinste Primfaktorzerlegung mit groß genugem Teilerprodukt.
Ausgehend von
$$\frac{1}{x}+\frac{1}{y}=\frac{1}{n}$$
multipliziert man mit \(xyn\) und erhält
$$n(x+y)=xy.$$
Umstellen und Ergänzen liefert
$$xy-nx-ny=0 \quad\Longrightarrow\quad (x-n)(y-n)=n^2.$$
Damit entspricht jede Lösung positiven ganzen Zahlen \(a=x-n\) und \(b=y-n\) mit \(ab=n^2\). Umgekehrt erzeugt jede Faktorisierung \(ab=n^2\) mit \(a,b>0\) die Lösung \(x=n+a\), \(y=n+b\). Da die Ausgangsgleichung symmetrisch in \(x\) und \(y\) ist, bedeutet die Bedingung \(x \ge y\) genau, dass jedes ungeordnete Teilerpaar von \(n^2\) einmal gezählt wird.
Sei \(d(m)\) die Anzahl positiver Teiler von \(m\). Die Teilerpaare von \(n^2\) treten normalerweise als gespiegelte Paare \((a,b)\) und \((b,a)\) auf. Weil \(n^2\) ein Quadrat ist, gibt es genau einen mittleren, ungepaarten Fall \(a=b=n\). Daher gilt
$$\#\{\text{Lösungen mit } x \ge y\}=\frac{d(n^2)+1}{2}.$$
Gesucht sind mehr als 1000 Lösungen, also
$$\frac{d(n^2)+1}{2}>1000 \quad\Longleftrightarrow\quad d(n^2)>1999.$$
Da \(d(n^2)\) für jedes Quadrat ungerade ist, ist das äquivalent zu
$$d(n^2)\ge 2001.$$
Genau diese ungerade Schranke wird in den Implementierungen geprüft.
Ist
$$n=\prod_{i=1}^{k} p_i^{a_i},$$
dann folgt
$$n^2=\prod_{i=1}^{k} p_i^{2a_i},$$
und mit der Teilerformel erhält man
$$d(n^2)=\prod_{i=1}^{k}(2a_i+1).$$
Die ursprüngliche diophantische Frage wird also zu: Finde das kleinste \(n=\prod p_i^{a_i}\) mit
$$\prod_{i=1}^{k}(2a_i+1)\ge 2001.$$
Ab hier spielen nicht mehr \(x\) und \(y\) die Hauptrolle, sondern die Exponenten \(a_i\) der Primfaktoren von \(n\).
Für eine feste Menge von Exponenten erhält man das kleinste \(n\), wenn der größte Exponent zur kleinsten Primzahl gehört, der nächstgrößere zur nächstkleineren Primzahl und so weiter. Denn falls \(p<q\), aber \(a<b\), dann gilt
$$p^a q^b > p^b q^a,$$
und ein Tausch der beiden Exponenten verkleinert \(n\), ohne \(d(n^2)\) zu ändern. Deshalb kann eine optimale Faktorisierung immer in der Form
$$a_1 \ge a_2 \ge a_3 \ge \cdots \ge 1$$
aufsteigend über die Primzahlen \(2,3,5,7,\dots\) geschrieben werden. Diese Monotonie ist die zentrale Invariante der Tiefensuche: Ist für eine Primzahl der Exponent \(e\) gewählt, dann dürfen spätere Exponenten höchstens noch \(e\) sein.
Nehmen wir \(n=4=2^2\). Dann ist
$$d(n^2)=d(16)=2\cdot 2+1=5,$$
also sagt die Formel voraus:
$$\frac{d(16)+1}{2}=\frac{5+1}{2}=3$$
verschiedene Lösungen. Die ungeordneten Teilerpaare von \(16\) sind
$$16\cdot 1,\qquad 8\cdot 2,\qquad 4\cdot 4.$$
Daraus entstehen
$$ (x,y)=(20,5),\qquad (12,6),\qquad (8,8), $$
also genau die drei Lösungen mit \(x \ge y\). Dieses kleine Beispiel zeigt bereits das vollständige Zählprinzip des allgemeinen Falls.
Setzt man auf die ersten sieben Primzahlen jeweils nur den Exponenten 1, so erhält man
$$n=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17=510510,$$
und damit
$$d(n^2)=3^7=2187\ge 2001.$$
Also existiert sicher eine gültige Lösung unterhalb von \(510510\). Das liefert noch nicht das Optimum, zeigt aber, dass nur ein kurzer Anfang der kleinen Primzahlen relevant ist und dass das Beschneiden der Suchzweige sehr schnell wirksam wird, sobald der erste zulässige Kandidat gefunden ist.
Die C++-, Python- und Java-Implementierungen durchsuchen Exponentenvektoren über den aufsteigenden Primzahlen \(2,3,5,7,\dots\). In jedem rekursiven Aufruf besteht der Zustand aus vier mathematischen Größen: der Position der nächsten Primzahl, dem größten noch erlaubten Exponenten, dem aktuellen Teilwert von \(n\) und dem aktuellen Wert von \(\prod (2a_i+1)\).
Für die aktuelle Primzahl probiert die Implementierung die Exponenten \(1,2,\dots\) bis zur erlaubten Obergrenze aus. Das Multiplizieren mit der Primzahl aktualisiert den Kandidaten \(n\), und die Wahl des Exponenten \(e\) multipliziert das Teilerprodukt mit \(2e+1\). Danach geht die Rekursion zur nächsten Primzahl weiter und verwendet \(e\) als neue obere Grenze, wodurch das Muster \(a_1 \ge a_2 \ge \cdots\) automatisch erhalten bleibt.
Sobald das Teilerprodukt \(2001\) oder mehr erreicht, ist das aktuelle \(n\) bereits ein vollständiger Kandidat und kann die beste bisher bekannte Lösung verbessern. Weitere positive Exponenten würden \(n\) nur vergrößern und bringen daher keinen Vorteil mehr.
Die wichtigste Beschneidungsregel ist einfach: Wenn das aktuelle Teilprodukt \(n\) bereits mindestens so groß ist wie die beste bisher gefundene Lösung, wird der gesamte Zweig verworfen. Spätere Rekursionen multiplizieren nur noch weitere Primzahlen hinzu und können diesen Zustand daher nicht mehr verbessern.
Weil die Rekursion sowohl \(n\) als auch \(\prod (2a_i+1)\) inkrementell aktualisiert, kostet jeder besuchte Zustand nur konstante Rechenzeit. Alle drei Sprachversionen implementieren dieselbe mathematische Suche, nur mit unterschiedlicher Syntax.
Der natürliche Komplexitätsparameter ist hier die Anzahl \(T\) der von der Tiefensuche besuchten Exponentenzustände. Jeder Zustand benötigt nur wenig Arithmetik, daher beträgt die Laufzeit \(O(T)\). Es gibt weder einen versteckten Durchlauf über alle \((x,y)\)-Paare noch eine brute-force Suche über alle Zahlen bis zur Antwort.
Der Speicherverbrauch ist \(O(r)\), wobei \(r\) die maximale Rekursionstiefe bezeichnet, also die Anzahl der Primzahlen mit positivem Exponenten auf einem aktuellen Zweig. Für die Schwelle 1000 bleiben sowohl \(T\) als auch \(r\) klein, weil die Monotonie der Exponenten und das Beschneiden mit der besten bekannten Lösung fast den gesamten nominellen Suchbaum eliminieren. In der Praxis läuft das Programm praktisch sofort durch.
Aranan şey, \(\frac{1}{x}+\frac{1}{y}=\frac{1}{n}\) diofant denkleminin pozitif tamsayılarda 1000'den fazla farklı çözümü olduğu en küçük pozitif \(n\)'dir; simetrik çiftler tek kez sayıldığı için bu, \(x \ge y\) koşuluyla aynı anlama gelir.
\(x\) ve \(y\) üzerinde kaba kuvvet araması yapmak doğru yaklaşım değildir, çünkü ilginç \(n\) değerleri zaten büyüktür. Kritik gözlem şudur: çözüm sayısı yalnızca \(n\)'nin asal çarpanlarına ayrılışındaki üslere bağlıdır. Böylece problem, payda çiftlerini taramaktan çıkıp üs vektörleri üzerinde bir minimizasyon problemine dönüşür.
Uygulamalar kısa ama güçlü bir fikir zincirini izler: kesir denklemini \(n^2\)'nin bir çarpanlaşmasına dönüştür, çözüm sayısını bölen fonksiyonuyla ifade et ve sonra bölen sayısı yeterince büyük olan en küçük asal çarpan yapısını ara.
Ş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üzenleyip dikdörtgeni tamamlarsak
$$xy-nx-ny=0 \quad\Longrightarrow\quad (x-n)(y-n)=n^2$$
olur. Demek ki her çözüm, \(a=x-n\) ve \(b=y-n\) olmak üzere \(ab=n^2\) sağlayan pozitif tamsayı çifti verir. Tersi de doğrudur: \(ab=n^2\) olan her pozitif çarpanlaşma \(x=n+a\), \(y=n+b\) çözümünü üretir. Başlangıç denklemi \(x\) ve \(y\) bakımından simetrik olduğundan, yalnızca \(x \ge y\) çözümlerini saymak \(n^2\)'nin her sırasız bölen çiftini bir kez saymakla tamamen aynıdır.
\(d(m)\), \(m\)'nin pozitif bölen sayısı olsun. \(n^2\)'nin bölen çiftleri normalde \((a,b)\) ve \((b,a)\) biçiminde ayna simetrili eşler halinde gelir. Fakat \(n^2\) tam kare olduğundan ortada bir tek eşleşmemiş durum vardır: \(a=b=n\). Bu yüzden
$$\#\{\text{\(x \ge y\) koşulundaki çözümler}\}=\frac{d(n^2)+1}{2}.$$
Soruda 1000'den fazla çözüm istendiği için
$$\frac{d(n^2)+1}{2}>1000 \quad\Longleftrightarrow\quad d(n^2)>1999$$
olmalıdır. \(d(n^2)\) her kare sayı için tek olduğundan bu,
$$d(n^2)\ge 2001$$
ile eşdeğerdir. Uygulamalar arama sırasında tam olarak bu tek eşiği kullanır.
Eğer
$$n=\prod_{i=1}^{k} p_i^{a_i}$$
ise
$$n^2=\prod_{i=1}^{k} p_i^{2a_i}$$
olur ve bölen fonksiyonu bize
$$d(n^2)=\prod_{i=1}^{k}(2a_i+1)$$
formülünü verir. Böylece asıl diofant soru şuna dönüşür: \(\prod p_i^{a_i}\) biçimindeki en küçük \(n\)'yi bul, öyle ki
$$\prod_{i=1}^{k}(2a_i+1)\ge 2001.$$
Buradan sonra odak artık doğrudan \(x\) ve \(y\) değil, üs vektörü \((a_1,a_2,\dots)\) olur.
Belirli bir üs çokluğu için en küçük \(n\), en büyük üssün en küçük asala, ondan sonraki en büyük üssün bir sonraki asala verilmesiyle elde edilir. Gerçekten, \(p<q\) ama üsler \(a<b\) biçiminde ters yerleşmişse
$$p^a q^b > p^b q^a$$
olur; yani bu iki üssü yer değiştirmek \(d(n^2)\)'yi değiştirmeden \(n\)'yi küçültür. Dolayısıyla optimal bir çarpanlaşma her zaman
$$a_1 \ge a_2 \ge a_3 \ge \cdots \ge 1$$
şeklinde, \(2,3,5,7,\dots\) artan asalları üzerinde yazılabilir. Derinlik öncelikli aramanın koruduğu temel değişmez de budur: bir asal için \(e\) üssü seçildiğinde, sonraki bütün üsler en fazla \(e\) olabilir.
\(n=4=2^2\) alalım. O zaman
$$d(n^2)=d(16)=2\cdot 2+1=5$$
olur; dolayısıyla formül
$$\frac{d(16)+1}{2}=\frac{5+1}{2}=3$$
farklı çözüm öngörür. \(16\)'nın sırasız bölen çiftleri
$$16\cdot 1,\qquad 8\cdot 2,\qquad 4\cdot 4$$
olduğundan bunlar
$$ (x,y)=(20,5),\qquad (12,6),\qquad (8,8) $$
çözümlerini verir. Bunlar tam olarak \(x \ge y\) koşulunu sağlayan üç çözümdür. Küçük olmasına rağmen bu örnek genel sayma mantığının tamamını gösterir.
İlk yedi asalın her birine yalnızca 1 üssü verilse bile
$$n=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17=510510$$
elde edilir ve bu durumda
$$d(n^2)=3^7=2187\ge 2001$$
olur. Yani geçerli bir çözümün kesinlikle \(510510\)'dan küçük olduğunu biliyoruz. Bu henüz optimumu vermez, fakat yalnızca küçük asalların kısa bir başlangıç kısmının önemli olduğunu ve ilk geçerli aday bulunur bulunmaz budamanın çok etkili hale geleceğini gösterir.
C++, Python ve Java uygulamaları, \(2,3,5,7,\dots\) artan asallarına bağlanan üs vektörleri üzerinde arama yapar. Her özyinelemeli çağrıda durum dört matematiksel büyüklükten oluşur: sıradaki asalın konumu, o asal için izin verilen en büyük üs, \(n\)'nin mevcut kısmi değeri ve \(\prod (2a_i+1)\) ifadesinin o ana kadarki değeri.
Geçerli asal için uygulama izin verilen üst sınıra kadar \(1,2,\dots\) üslerini dener. Asalla çarpmak aday \(n\)'yi günceller; \(e\) üssünü seçmek ise bölen sayısı çarpanını \(2e+1\) ile çarpar. Sonra özyineleme bir sonraki asala geçer ve yeni üst sınır olarak \(e\)'yi kullanır; böylece \(a_1 \ge a_2 \ge \cdots\) düzeni otomatik olarak korunur.
Eğer bölen çarpımı \(2001\) veya daha fazlasına ulaşırsa mevcut \(n\) artık tam bir adaydır ve en iyi cevabı güncelleyebilir. Daha fazla asal eklemenin faydası yoktur, çünkü her yeni pozitif üs yalnızca \(n\)'yi büyütür.
Temel budama kuralı çok basittir: mevcut kısmi \(n\), şimdiye kadar bulunan en iyi çözümden zaten büyük ya da ona eşitse o dal tamamen bırakılır. Çünkü daha derine inmek yalnızca yeni asallarla çarpmak anlamına gelir ve bu yüzden o daldan daha iyi bir cevap çıkamaz.
Özyineleme hem \(n\)'yi hem de \(\prod (2a_i+1)\) değerini artımlı biçimde güncellediği için ziyaret edilen her durum yalnızca sabit zamanlı birkaç aritmetik işlem gerektirir. Üç dildeki sürümlerin hepsi aynı matematiksel aramayı uygular; fark sadece sözdizimindedir.
Buradaki doğal karmaşıklık parametresi, derinlik öncelikli aramanın ziyaret ettiği üs durumlarının sayısı \(T\)'dir. Her durumda yalnızca az miktarda aritmetik yapıldığı için çalışma süresi \(O(T)\) olur. Ne tüm \((x,y)\) çiftleri üzerinden gizli bir tarama vardır ne de cevaba kadar bütün sayılar kaba kuvvetle denenir.
Bellek kullanımı \(O(r)\)'dir; burada \(r\), özyinelemenin ulaştığı en büyük derinlik, yani mevcut dalda pozitif üs verilen asal sayısıdır. 1000 eşiği için hem \(T\) hem de \(r\) küçüktür; çünkü üslerin azalan sıralı olması zorunluluğu ve en iyi adayla yapılan budama, görünürdeki arama ağacının neredeyse tamamını yok eder. Pratikte program neredeyse anında biter.
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 1000 soluciones distintas en enteros positivos, contando cada par simétrico una sola vez, es decir, de manera equivalente con \(x \ge y\).
No conviene atacar el problema con una búsqueda directa sobre \(x\) e \(y\), porque los valores interesantes de \(n\) ya son grandes. La observación decisiva es que el número de soluciones depende solo de la factorización prima de \(n\), así que el problema se transforma en una optimización sobre vectores de exponentes y no en un barrido sobre pares de denominadores.
Las implementaciones siguen una cadena de ideas corta pero muy potente: convertir la ecuación de recíprocos en una factorización de \(n^2\), expresar el número de soluciones mediante la función divisora y después buscar la menor factorización prima cuyo número de divisores sea suficientemente grande.
Partimos de
$$\frac{1}{x}+\frac{1}{y}=\frac{1}{n}.$$
Al multiplicar por \(xyn\) obtenemos
$$n(x+y)=xy.$$
Reordenando y completando el rectángulo se llega a
$$xy-nx-ny=0 \quad\Longrightarrow\quad (x-n)(y-n)=n^2.$$
Por tanto, cada solución corresponde a enteros positivos \(a=x-n\) y \(b=y-n\) tales que \(ab=n^2\). Y a la inversa, toda factorización \(ab=n^2\) con \(a,b>0\) produce una solución \(x=n+a\), \(y=n+b\). Como la ecuación original es simétrica en \(x\) e \(y\), contar solo las soluciones con \(x \ge y\) equivale exactamente a contar una vez cada par no ordenado de factores de \(n^2\).
Sea \(d(m)\) el número de divisores positivos de \(m\). Los pares de factores de \(n^2\) normalmente aparecen como parejas espejo \((a,b)\) y \((b,a)\). Como \(n^2\) es un cuadrado perfecto, existe un caso central no emparejado, \(a=b=n\). Por eso
$$\#\{\text{soluciones con } x \ge y\}=\frac{d(n^2)+1}{2}.$$
El problema exige más de 1000 soluciones, así que
$$\frac{d(n^2)+1}{2}>1000 \quad\Longleftrightarrow\quad d(n^2)>1999.$$
Dado que \(d(n^2)\) es impar para cualquier cuadrado, esto equivale a
$$d(n^2)\ge 2001.$$
Ese es precisamente el umbral impar que las implementaciones vigilan durante la búsqueda.
Si
$$n=\prod_{i=1}^{k} p_i^{a_i},$$
entonces
$$n^2=\prod_{i=1}^{k} p_i^{2a_i},$$
y la fórmula de los divisores da
$$d(n^2)=\prod_{i=1}^{k}(2a_i+1).$$
Así, la pregunta diofántica original se convierte en: encontrar el menor \(n=\prod p_i^{a_i}\) tal que
$$\prod_{i=1}^{k}(2a_i+1)\ge 2001.$$
A partir de aquí, los objetos realmente importantes ya no son \(x\) e \(y\), sino el vector de exponentes \((a_1,a_2,\dots)\).
Para un multiconjunto fijo de exponentes, el valor mínimo posible de \(n\) se obtiene asignando el exponente mayor al primo más pequeño, el siguiente exponente al siguiente primo, y así sucesivamente. En efecto, si \(p<q\) pero los exponentes están colocados como \(a<b\), entonces
$$p^a q^b > p^b q^a,$$
de modo que intercambiar esos exponentes reduce \(n\) sin cambiar \(d(n^2)\). Por lo tanto, una factorización óptima siempre puede escribirse como
$$a_1 \ge a_2 \ge a_3 \ge \cdots \ge 1$$
sobre los primos crecientes \(2,3,5,7,\dots\). Esta monotonía es el invariante clave de la búsqueda en profundidad: una vez elegido un exponente \(e\) para un primo, todos los exponentes posteriores quedan restringidos a ser como mucho \(e\).
Tomemos \(n=4=2^2\). Entonces
$$d(n^2)=d(16)=2\cdot 2+1=5,$$
así que la fórmula predice
$$\frac{d(16)+1}{2}=\frac{5+1}{2}=3$$
soluciones distintas. Los pares no ordenados de factores de \(16\) son
$$16\cdot 1,\qquad 8\cdot 2,\qquad 4\cdot 4.$$
Eso produce
$$ (x,y)=(20,5),\qquad (12,6),\qquad (8,8), $$
que son exactamente las tres soluciones con \(x \ge y\). Este ejemplo pequeño ya contiene todo el mecanismo de conteo del caso general.
Si ponemos exponente 1 en cada uno de los siete primeros primos, obtenemos
$$n=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17=510510,$$
y entonces
$$d(n^2)=3^7=2187\ge 2001.$$
Por consiguiente, existe con certeza una solución válida por debajo de \(510510\). Esto todavía no demuestra cuál es la óptima, pero sí indica que solo importa un prefijo corto de primos pequeños y que la poda se vuelve muy eficaz en cuanto aparece el primer candidato admisible.
Las implementaciones en C++, Python y Java recorren vectores de exponentes asociados a los primos crecientes \(2,3,5,7,\dots\). En cada llamada recursiva, el estado contiene cuatro cantidades matemáticas: la posición del siguiente primo, el mayor exponente permitido para ese primo, el valor parcial actual de \(n\) y el valor actual de \(\prod (2a_i+1)\).
Para el primo actual, la implementación prueba exponentes \(1,2,\dots\) hasta el máximo permitido. Multiplicar por el primo actualiza el candidato \(n\), y elegir exponente \(e\) multiplica el producto de divisores por \(2e+1\). Después la recursión continúa con el siguiente primo usando \(e\) como nuevo límite superior, lo que preserva automáticamente el patrón no creciente \(a_1 \ge a_2 \ge \cdots\).
Si el producto de divisores alcanza \(2001\) o más, el \(n\) actual ya es un candidato completo y puede mejorar la mejor respuesta conocida. No tiene sentido añadir más primos, porque cualquier exponente positivo extra solo haría \(n\) más grande.
La regla de poda esencial es muy simple: si el valor parcial actual de \(n\) ya es al menos tan grande como la mejor solución encontrada hasta ese momento, se abandona toda esa rama. Las llamadas posteriores solo multiplicarían por más primos, así que ningún descendiente de ese estado puede mejorar la respuesta.
Como la recursión actualiza tanto \(n\) como \(\prod (2a_i+1)\) de forma incremental, cada estado visitado requiere solo aritmética de tiempo constante. Las tres versiones en distintos lenguajes implementan exactamente la misma búsqueda matemática.
El parámetro natural de complejidad aquí es el número \(T\) de estados de exponentes visitados por la búsqueda en profundidad. Cada estado realiza muy poca aritmética, de modo que el tiempo total es \(O(T)\). No existe ningún recorrido oculto sobre todos los pares \((x,y)\) ni un barrido por fuerza bruta sobre todos los enteros hasta la respuesta.
El uso de memoria es \(O(r)\), donde \(r\) es la profundidad máxima de la recursión, es decir, el número de primos que reciben exponente positivo en una rama. Para el umbral 1000, tanto \(T\) como \(r\) permanecen pequeños, porque el invariante de exponentes no crecientes y la poda con la mejor solución conocida eliminan casi todo el árbol de búsqueda nominal. En la práctica el programa termina de forma prácticamente instantánea.
题目要求找出最小的正整数 \(n\)，使得丢番图方程 \(\frac{1}{x}+\frac{1}{y}=\frac{1}{n}\) 在正整数中有超过 1000 组不同解；由于 \((x,y)\) 与 \((y,x)\) 表示同一组对称情形，这等价于只统计 \(x \ge y\) 的解。
如果直接枚举 \(x\) 和 \(y\)，视角就错了，因为真正相关的 \(n\) 已经不小。关键观察是：解的个数只取决于 \(n\) 的质因数分解，而不是取决于如何逐个尝试分母。因此问题本质上变成了一个“怎样安排质因数指数才能让 \(n\) 最小”的优化问题。
实现采用的是一条很紧凑但非常有力的推导链：先把倒数方程改写成 \(n^2\) 的因子分解问题，再用约数函数表达解的个数，最后在所有可能的指数向量中搜索最小的可行 \(n\)。
从
$$\frac{1}{x}+\frac{1}{y}=\frac{1}{n}$$
出发，两边同乘 \(xyn\)，得到
$$n(x+y)=xy.$$
移项并配方后有
$$xy-nx-ny=0 \quad\Longrightarrow\quad (x-n)(y-n)=n^2.$$
这说明每一组解都对应于正整数 \(a=x-n\)、\(b=y-n\)，并满足 \(ab=n^2\)。反过来，只要 \(a,b>0\) 且 \(ab=n^2\)，就能反推出一组解 \(x=n+a\)、\(y=n+b\)。因为原方程对 \(x\) 与 \(y\) 是对称的，所以只统计 \(x \ge y\) 的解，恰好等价于把 \(n^2\) 的每一组无序因子对只算一次。
记 \(d(m)\) 为正整数 \(m\) 的正约数个数。通常情况下，\(n^2\) 的因子对会以 \((a,b)\) 和 \((b,a)\) 的镜像形式成对出现。由于 \(n^2\) 是完全平方数，会有一个居中的未配对情形 \(a=b=n\)。因此
$$\#\{\text{满足 } x \ge y \text{ 的解}\}=\frac{d(n^2)+1}{2}.$$
题目要求解的个数大于 1000，于是
$$\frac{d(n^2)+1}{2}>1000 \quad\Longleftrightarrow\quad d(n^2)>1999.$$
而平方数的约数个数总是奇数，所以这又等价于
$$d(n^2)\ge 2001.$$
实现里真正比较的，就是这个奇数阈值 2001。
若
$$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_{i=1}^{k}(2a_i+1)\ge 2001.$$
也就是说，真正需要选择的对象不再是 \(x,y\)，而是指数向量 \((a_1,a_2,\dots)\)。
对一组固定的指数多重集来说，要让 \(n\) 最小，就必须把最大的指数放在最小的质数上，把次大的指数放在次小的质数上，依此类推。理由很直接：如果 \(p<q\)，但指数排成了 \(a<b\)，那么
$$p^a q^b > p^b q^a,$$
交换这两个指数后，\(d(n^2)\) 不变，但 \(n\) 会更小。因此最优解总可以写成
$$a_1 \ge a_2 \ge a_3 \ge \cdots \ge 1$$
并依次放在递增质数 \(2,3,5,7,\dots\) 上。这正是深度优先搜索所维护的核心不变量：一旦某个质数选了指数 \(e\)，后面的指数就都不能超过 \(e\)。
取 \(n=4=2^2\)。这时
$$d(n^2)=d(16)=2\cdot 2+1=5,$$
所以公式给出
$$\frac{d(16)+1}{2}=\frac{5+1}{2}=3$$
组不同解。\(16\) 的无序因子对是
$$16\cdot 1,\qquad 8\cdot 2,\qquad 4\cdot 4.$$
它们分别对应
$$ (x,y)=(20,5),\qquad (12,6),\qquad (8,8), $$
正好就是全部满足 \(x \ge y\) 的三组解。这个例子虽然很小，却已经把一般情形的计数机制完整展示出来了。
如果前七个质数全部只取指数 1，那么
$$n=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17=510510,$$
并且
$$d(n^2)=3^7=2187\ge 2001.$$
这说明答案一定小于 \(510510\)。虽然这还没有直接给出最优值，但它说明只需要考虑一小段最小质数，而且一旦搜索找到第一个可行候选，剪枝就会迅速变得非常有效。
C++、Python 和 Java 三个实现都在递增质数 \(2,3,5,7,\dots\) 上搜索指数向量。每一次递归调用都维护四个数学量：下一个要处理的质数位置、该质数允许的最大指数、当前部分构造出的 \(n\)，以及当前的 \(\prod (2a_i+1)\) 值。
对当前质数，实现会尝试指数 \(1,2,\dots\)，直到允许的上界。每多乘一次当前质数，就把候选 \(n\) 更新一步；一旦为该质数确定指数 \(e\)，约数乘积就乘上 \(2e+1\)。随后递归进入下一个质数，并把新的上界设为 \(e\)，这样就自动维持了 \(a_1 \ge a_2 \ge \cdots\) 的结构。
当约数乘积达到 2001 或更大时，当前 \(n\) 已经是一个完整候选，可以拿来更新最优答案。此时没有必要再继续附加新的质数，因为任何额外的正指数只会让 \(n\) 更大。
最关键的剪枝规则非常直接：如果当前部分构造出的 \(n\) 已经不小于目前找到的最好答案，那么整棵子树都可以丢弃。因为后续递归只会继续乘上更多质数，这个分支不可能再反超已有最优解。
由于递归对 \(n\) 和 \(\prod (2a_i+1)\) 都采用增量更新，因此访问每个状态只需要常数时间算术操作。三个语言版本虽然写法不同，但实现的是同一个数学搜索过程。
这里最自然的复杂度参数是深度优先搜索访问的状态数 \(T\)。每个状态只做少量算术，因此总时间复杂度是 \(O(T)\)。整个算法没有隐藏地枚举所有 \((x,y)\) 对，也不会对答案之前的所有整数进行暴力扫描。
空间复杂度为 \(O(r)\)，其中 \(r\) 是递归的最大深度，也就是当前分支上拥有正指数的质数个数。对本题的 1000 阈值来说，\(T\) 和 \(r\) 都很小，因为“指数单调不增”这个不变量以及“当前值不优于最优解就剪枝”的策略，已经砍掉了名义搜索树中的绝大部分分支。实际运行几乎是瞬间完成的。
Нужно найти наименьшее положительное число \(n\), для которого диофантово уравнение \(\frac{1}{x}+\frac{1}{y}=\frac{1}{n}\) имеет более 1000 различных решений в положительных целых числах, если симметричные пары считать один раз, то есть эквивалентно при условии \(x \ge y\).
Перебирать напрямую \(x\) и \(y\) здесь бессмысленно, потому что интересующие значения \(n\) уже достаточно велики. Ключевое наблюдение состоит в том, что число решений определяется только разложением \(n\) на простые множители. Значит, задача превращается не в перебор пар знаменателей, а в оптимизацию по векторам показателей.
Во всех реализациях используется одна и та же короткая, но очень сильная цепочка идей: превратить уравнение с обратными величинами в разложение числа \(n^2\), выразить количество решений через функцию числа делителей, а затем искать наименьшую простую факторизацию, у которой это число уже достаточно велико.
Начнём с
$$\frac{1}{x}+\frac{1}{y}=\frac{1}{n}.$$
Умножая на \(xyn\), получаем
$$n(x+y)=xy.$$
Перенос членов и выделение произведения дают
$$xy-nx-ny=0 \quad\Longrightarrow\quad (x-n)(y-n)=n^2.$$
Следовательно, каждому решению соответствуют положительные целые \(a=x-n\) и \(b=y-n\), удовлетворяющие \(ab=n^2\). Обратно, любое разложение \(ab=n^2\) при \(a,b>0\) даёт решение \(x=n+a\), \(y=n+b\). Поскольку исходное уравнение симметрично по \(x\) и \(y\), требование считать только решения с \(x \ge y\) в точности означает: каждый неупорядоченный парный делитель числа \(n^2\) учитывать один раз.
Пусть \(d(m)\) обозначает число положительных делителей числа \(m\). Обычно пары делителей числа \(n^2\) возникают как зеркальные пары \((a,b)\) и \((b,a)\). Но \(n^2\) является точным квадратом, поэтому существует центральный непарный случай \(a=b=n\). Отсюда
$$\#\{\text{решений при } x \ge y\}=\frac{d(n^2)+1}{2}.$$
Нужно больше 1000 решений, то есть
$$\frac{d(n^2)+1}{2}>1000 \quad\Longleftrightarrow\quad d(n^2)>1999.$$
Так как \(d(n^2)\) для любого квадрата нечётно, это эквивалентно условию
$$d(n^2)\ge 2001.$$
Именно этот нечётный порог используется в программе.
Если
$$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_{i=1}^{k}(2a_i+1)\ge 2001.$$
После этого решающими объектами становятся уже не сами \(x\) и \(y\), а показатели \(a_i\) в разложении \(n\).
Для фиксированного набора показателей минимальное значение \(n\) получается тогда, когда наибольший показатель ставится при наименьшем простом числе, следующий по величине показатель при следующем простом и так далее. Действительно, если \(p<q\), но показатели расположены как \(a<b\), то
$$p^a q^b > p^b q^a,$$
и перестановка этих двух показателей уменьшает \(n\), не меняя \(d(n^2)\). Значит, оптимальное разложение всегда можно записать в виде
$$a_1 \ge a_2 \ge a_3 \ge \cdots \ge 1$$
на возрастающих простых \(2,3,5,7,\dots\). Это и есть ключевой инвариант поиска в глубину: как только для некоторого простого выбран показатель \(e\), все последующие показатели ограничиваются сверху тем же \(e\).
Возьмём \(n=4=2^2\). Тогда
$$d(n^2)=d(16)=2\cdot 2+1=5,$$
и формула предсказывает
$$\frac{d(16)+1}{2}=\frac{5+1}{2}=3$$
различных решения. Неупорядоченные пары делителей числа \(16\) таковы:
$$16\cdot 1,\qquad 8\cdot 2,\qquad 4\cdot 4.$$
Они дают
$$ (x,y)=(20,5),\qquad (12,6),\qquad (8,8), $$
то есть ровно три решения с условием \(x \ge y\). Этот маленький пример уже полностью показывает механизм подсчёта в общем случае.
Если взять показатель 1 у первых семи простых чисел, то получится
$$n=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17=510510,$$
и тогда
$$d(n^2)=3^7=2187\ge 2001.$$
Следовательно, допустимое решение заведомо существует ниже \(510510\). Это ещё не даёт оптимум, но сразу показывает, что достаточно рассматривать лишь короткий начальный участок малых простых чисел и что после нахождения первого допустимого кандидата отсечение ветвей становится очень эффективным.
Реализации на C++, Python и Java перебирают векторы показателей, привязанные к возрастающим простым числам \(2,3,5,7,\dots\). В каждом рекурсивном вызове хранятся четыре математические величины: позиция следующего простого, максимально допустимый показатель для него, текущее частичное значение \(n\) и текущее значение произведения \(\prod (2a_i+1)\).
Для текущего простого реализация пробует показатели \(1,2,\dots\) вплоть до разрешённого верхнего предела. Умножение на простое обновляет кандидат \(n\), а выбор показателя \(e\) умножает произведение делителей на \(2e+1\). Затем рекурсия переходит к следующему простому и использует \(e\) как новый верхний предел, благодаря чему автоматически сохраняется структура \(a_1 \ge a_2 \ge \cdots\).
Если произведение делителей достигает 2001 или больше, текущее значение \(n\) уже является полноценным кандидатом и может улучшить лучший найденный ответ. Продолжать добавлять новые простые нет смысла, потому что любой дополнительный положительный показатель только увеличит \(n\).
Главное правило отсечения очень простое: если текущее частичное значение \(n\) уже не меньше лучшего найденного решения, вся ветвь отбрасывается целиком. Дальнейшая рекурсия только домножает на новые простые, а значит, не может привести к лучшему результату.
Поскольку и \(n\), и \(\prod (2a_i+1)\) обновляются инкрементально, каждый посещённый узел требует лишь константного количества арифметики. Во всех трёх языках реализован один и тот же математический поиск.
Естественный параметр сложности здесь - количество \(T\) состояний показателей, которые посещает поиск в глубину. Каждый узел выполняет лишь немного арифметики, поэтому время работы равно \(O(T)\). Здесь нет скрытого перебора всех пар \((x,y)\) и нет полного brute-force прохода по всем целым числам до ответа.
Память составляет \(O(r)\), где \(r\) - максимальная глубина рекурсии, то есть число простых, получивших положительный показатель в текущей ветви. Для порога 1000 и \(T\), и \(r\) малы, потому что инвариант невозрастающих показателей и отсечение по лучшему найденному значению устраняют почти всё номинальное дерево поиска. На практике программа отрабатывает практически мгновенно.
المطلوب هو إيجاد أصغر عدد صحيح موجب \(n\) بحيث تمتلك المعادلة الديوفانتية \(\frac{1}{x}+\frac{1}{y}=\frac{1}{n}\) أكثر من 1000 حل مختلف في الأعداد الصحيحة الموجبة، مع عدّ كل زوج متماثل مرة واحدة فقط، أي بصورة مكافئة تحت الشرط \(x \ge y\).
البحث المباشر على \(x\) و\(y\) ليس هو الزاوية الصحيحة هنا، لأن قيم \(n\) المهمة كبيرة أصلًا. الفكرة الحاسمة هي أن عدد الحلول لا يعتمد إلا على التحليل الأولي للعدد \(n\)، ولذلك تتحول المسألة من فحص أزواج المقامات إلى مسألة تحسين على متجهات الأسس.
تتبع جميع التطبيقات سلسلة قصيرة ولكنها قوية جدًا من الأفكار: تحويل معادلة المقلوبات إلى تحليل لعوامل \(n^2\)، ثم التعبير عن عدد الحلول بدالة عدد القواسم، ثم البحث عن أصغر تحليل أولي يحقق عددًا كافيًا من القواسم.
نبدأ من
$$\frac{1}{x}+\frac{1}{y}=\frac{1}{n}.$$
وبعد الضرب في \(xyn\) نحصل على
$$n(x+y)=xy.$$
وبإعادة الترتيب وإكمال الشكل المناسب نحصل على
$$xy-nx-ny=0 \quad\Longrightarrow\quad (x-n)(y-n)=n^2.$$
إذن كل حل يقابل عددين صحيحين موجبين \(a=x-n\) و\(b=y-n\) يحققان \(ab=n^2\). والعكس صحيح أيضًا: كل تحليل \(ab=n^2\) مع \(a,b>0\) يولد حلًا هو \(x=n+a\) و\(y=n+b\). وبما أن المعادلة الأصلية متناظرة في \(x\) و\(y\)، فإن عدّ الحلول تحت الشرط \(x \ge y\) يساوي تمامًا عدّ كل زوج غير مرتب من عوامل \(n^2\) مرة واحدة.
لنرمز بـ \(d(m)\) إلى عدد القواسم الموجبة للعدد \(m\). أزواج عوامل \(n^2\) تظهر عادة على شكل زوجين متناظرين \((a,b)\) و\((b,a)\). لكن بما أن \(n^2\) مربع كامل، فهناك حالة وسطية غير مزدوجة هي \(a=b=n\). إذا رمزنا بعدد الحلول التي تحقق \(x \ge y\) بالرمز \(N(n)\)، فإن
$$N(n)=\frac{d(n^2)+1}{2}.$$
والمسألة تريد أكثر من 1000 حل، أي
$$\frac{d(n^2)+1}{2}>1000 \quad\Longleftrightarrow\quad d(n^2)>1999.$$
وبما أن \(d(n^2)\) يكون فرديًا لكل مربع كامل، فهذا يكافئ الشرط
$$d(n^2)\ge 2001.$$
وهذا هو الحد الفردي الذي تعتمد عليه التطبيقات أثناء البحث.
إذا كان
$$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_{i=1}^{k}(2a_i+1)\ge 2001.$$
ومن هذه اللحظة لا يعود التركيز على \(x\) و\(y\) مباشرة، بل على متجه الأسس \((a_1,a_2,\dots)\).
إذا ثبتت مجموعة الأسس نفسها، فإن أصغر قيمة ممكنة لـ \(n\) تتحقق عندما يوضع أكبر أس على أصغر عدد أولي، ثم الأس الذي يليه على الأولي التالي، وهكذا. والسبب أنه إذا كان \(p<q\) ولكن الترتيب كان \(a<b\)، فإن
$$p^a q^b > p^b q^a,$$
وبالتالي فإن تبديل هذين الأسين يصغر \(n\) من دون أن يغير \(d(n^2)\). لذلك يمكن دائمًا كتابة التحليل الأمثل على الصورة
$$a_1 \ge a_2 \ge a_3 \ge \cdots \ge 1$$
فوق الأعداد الأولية المتزايدة \(2,3,5,7,\dots\). وهذه الرتبة الأحادية هي الثابت الأساسي الذي تحافظ عليه عملية البحث بالعمق: ما إن يُختَر الأس \(e\) لأولّي ما، حتى تُقيَّد جميع الأسس اللاحقة بألا تتجاوز \(e\).
لنأخذ \(n=4=2^2\). عندئذ
$$d(n^2)=d(16)=2\cdot 2+1=5,$$
ومن ثم تتنبأ الصيغة بوجود
$$\frac{d(16)+1}{2}=\frac{5+1}{2}=3$$
حلول مختلفة. وأزواج عوامل \(16\) غير المرتبة هي
$$16\cdot 1,\qquad 8\cdot 2,\qquad 4\cdot 4.$$
وهذه تعطي
$$ (x,y)=(20,5),\qquad (12,6),\qquad (8,8), $$
وهي بالضبط الحلول الثلاثة التي تحقق \(x \ge y\). ورغم بساطة هذا المثال، فإنه يعرض آلية العد العامة كاملة.
إذا أعطينا الأس 1 لكل واحد من الأعداد الأولية السبعة الأولى، نحصل على
$$n=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17=510510,$$
وعندها
$$d(n^2)=3^7=2187\ge 2001.$$
إذًا يوجد حل صالح بالتأكيد تحت \(510510\). هذا لا يحدد القيمة المثلى بعد، لكنه يوضح أن جزءًا قصيرًا فقط من الأعداد الأولية الصغيرة هو المهم، وأن التقليم يصبح فعّالًا جدًا بمجرد العثور على أول مرشح صالح.
تقوم تطبيقات C++ وPython وJava جميعها بالبحث في متجهات الأسس المرتبطة بالأعداد الأولية المتزايدة \(2,3,5,7,\dots\). وفي كل استدعاء عودي تحفظ الحالة أربع كميات رياضية: موضع الأولي التالي، وأكبر أس مسموح به له، والقيمة الجزئية الحالية لـ \(n\)، والقيمة الحالية للجداء \(\prod (2a_i+1)\).
بالنسبة إلى الأولي الحالي، تجرّب التطبيقات الأسس \(1,2,\dots\) حتى الحد الأعلى المسموح. إن الضرب في الأولي يحدّث المرشح \(n\)، بينما اختيار أس مقداره \(e\) يضرب جداء القواسم في \(2e+1\). بعد ذلك تنتقل العملية العودية إلى الأولي التالي مع استخدام \(e\) بوصفه الحد الأعلى الجديد، وبذلك يُحفَظ النمط \(a_1 \ge a_2 \ge \cdots\) تلقائيًا.
إذا بلغ جداء القواسم 2001 أو تجاوزه، فإن القيمة الحالية لـ \(n\) تصبح مرشحًا كاملًا ويمكنها تحديث أفضل جواب معروف. وليس هناك فائدة من إضافة أعداد أولية أخرى، لأن أي أس موجب إضافي لن يفعل سوى تكبير \(n\).
قاعدة التقليم الأساسية بسيطة جدًا: إذا كانت القيمة الجزئية الحالية لـ \(n\) قد أصبحت بالفعل أكبر من أو مساوية لأفضل حل عُثر عليه حتى الآن، فإن الفرع كله يُهمل. فكل نزول لاحق في الشجرة يعني فقط الضرب في أعداد أولية إضافية، ولذلك لا يمكن لأي ابن من هذه الحالة أن يعطي جوابًا أفضل.
وبما أن التحديثين الخاصين بـ \(n\) و\(\prod (2a_i+1)\) يجريان بطريقة تراكمية، فإن كل حالة مزارة تحتاج فقط إلى حسابات زمنها ثابت. النسخ الثلاث تختلف في الصياغة اللغوية فقط، أما البحث الرياضي فهو نفسه تمامًا.
معامل التعقيد الطبيعي هنا هو عدد الحالات \(T\) التي يزورها البحث بالعمق داخل فضاء الأسس. كل حالة تتطلب مقدارًا صغيرًا فقط من الحساب، لذلك يكون الزمن الكلي \(O(T)\). لا يوجد هنا مسح خفي لكل الأزواج \((x,y)\)، ولا يوجد تعداد brute-force لكل الأعداد الصحيحة حتى الجواب.
أما الذاكرة فهي \(O(r)\)، حيث \(r\) هو أقصى عمق للاستدعاء العودي، أي عدد الأعداد الأولية التي تأخذ أسًا موجبًا في الفرع الحالي. بالنسبة إلى العتبة 1000، يبقى كل من \(T\) و\(r\) صغيرًا، لأن ثابت "الأسس غير المتزايدة" مع التقليم اعتمادًا على أفضل قيمة حالية يزيلان معظم شجرة البحث الاسمية. عمليًا ينتهي البرنامج بسرعة شبه فورية.