For a positive integer \(n\), the perfection quotient is \(\sigma(n)/n\), where \(\sigma(n)\) is the sum of the positive divisors of \(n\). The task is to sum every \(n \le 10^{18}\) whose perfection quotient is a half-integer. For the bound used here, the implementations split the search into the six target values
$$\frac{3}{2},\ \frac{5}{2},\ \frac{7}{2},\ \frac{9}{2},\ \frac{11}{2},\ \frac{13}{2}.$$
A direct scan up to \(10^{18}\) is hopeless. The successful strategy is to build \(n\) prime-power by prime-power, while tracking an exact residual quotient that measures how far the current partial factorization is from the chosen target.
Fix one target value \(T=\frac{A}{2}\). We want all integers \(n\) satisfying
$$\frac{\sigma(n)}{n}=T.$$
If
$$n=\prod_i p_i^{e_i},$$
then multiplicativity gives
$$\sigma(n)=\prod_i \sigma(p_i^{e_i}),\qquad \frac{\sigma(n)}{n}=\prod_i \frac{\sigma(p_i^{e_i})}{p_i^{e_i}}.$$
For a single prime power,
$$\sigma(p^e)=1+p+p^2+\cdots+p^e=\frac{p^{e+1}-1}{p-1},$$
so its contribution to the perfection quotient is
$$\frac{\sigma(p^e)}{p^e}=1+\frac1p+\frac1{p^2}+\cdots+\frac1{p^e}.$$
This is always greater than 1. Therefore every time we append a new prime power to \(n\), the quotient \(\sigma(n)/n\) increases, and the reciprocal quantity \(n/\sigma(n)\) decreases.
Instead of testing \(\sigma(n)/n\) from scratch at every node, the search keeps the reduced residual quotient
$$Q(n)=T\frac{n}{\sigma(n)}=\frac{u}{v},\qquad \gcd(u,v)=1.$$
At the root, \(n=1\), so \(Q(1)=T\). If we extend the current partial factorization by a new prime power \(p^e\), then
$$Q(np^e)=Q(n)\cdot \frac{p^e}{\sigma(p^e)}.$$
Since \(\sigma(p^e)/p^e>1\), each update multiplies \(Q\) by a factor strictly smaller than 1. The target condition becomes
$$Q(n)=1 \iff T\frac{n}{\sigma(n)}=1 \iff \frac{\sigma(n)}{n}=T.$$
So the entire search is a controlled descent from \(Q=T\) down to \(Q=1\).
Assume the current state is \(Q(n)=u/v\) in lowest terms, and suppose that some unused cofactor \(m\) finishes the construction. Then
$$1=Q(n)\frac{m}{\sigma(m)}=\frac{u}{v}\frac{m}{\sigma(m)},$$
which is equivalent to
$$u\,m=v\,\sigma(m).$$
Because \(\gcd(u,v)=1\), this forces
$$v \mid m.$$
That divisibility is the key invariant. Every prime that appears in the current denominator must still appear later in the unfinished part of the number. Let \(p\) be the smallest prime divisor of \(v\). Then any completion must contain some power \(p^e\), so the recursion branches only on that prime \(p\).
There is also a lower bound on the exponent. If \(p^a \mid v\), then the new numerator must contribute at least \(p^a\) in order to cancel that denominator power after reduction. But in the update factor
$$\frac{p^e}{\sigma(p^e)},$$
the only source of \(p\)-adic valuation in the numerator is \(p^e\) itself, because \(\sigma(p^e)\equiv 1 \pmod p\). Therefore the branch must start at \(e \ge a\).
Once a prime has been inserted into the current partial factorization, the search never comes back to that prime later. This is not an arbitrary restriction. If a valid solution contains \(p^e\), then that full exponent must be chosen precisely when the denominator first forces the prime \(p\). Revisiting \(p\) later would only recreate the same final number in a different order. The recursion therefore explores each admissible exponent exactly once, in a canonical order dictated by the changing denominator of \(Q\).
First, if the reduced residual quotient satisfies \(u<v\), then \(Q(n)<1\). From that point onward every extra prime power multiplies by another factor \(p^e/\sigma(p^e)<1\), so the branch can only move farther below 1. Such a branch is already lost.
Second, the divisibility \(v\mid m\) implies \(m\ge v\). Hence every completion \(N=nm\) satisfies
$$N \ge n\,v.$$
So whenever \(n\,v>10^{18}\), no completion can stay inside the problem limit, and the branch can be discarded immediately.
There is also monotonicity inside a fixed prime loop. For one prime \(p\), the factor
$$\frac{p^e}{\sigma(p^e)}=\frac{1}{1+\frac1p+\cdots+\frac1{p^e}}$$
decreases as \(e\) grows. Therefore, once a chosen exponent pushes the reduced residual below 1, larger exponents cannot repair the branch, so the loop may stop at once.
Take \(T=\frac52\). Start from
$$Q(1)=\frac52.$$
The denominator is 2, so the next forced prime is \(2\). Choose the exponent \(e=3\). Then
$$Q(2^3)=\frac52\cdot\frac{8}{1+2+4+8}=\frac52\cdot\frac{8}{15}=\frac43.$$
Now the denominator is 3, so the next forced prime is \(3\). Taking exponent \(e=1\) gives
$$Q(2^3\cdot 3)=\frac43\cdot\frac{3}{1+3}=\frac43\cdot\frac34=1.$$
Thus
$$\frac{\sigma(24)}{24}=\frac52,$$
so \(24\) is a valid term. This example shows the exact rhythm of the search: read the denominator, force its smallest prime, try admissible exponents, reduce the residual quotient, and repeat until either \(Q=1\) or a pruning rule fires.
The C++, Python, and Java implementations follow the same number-theoretic plan. They solve the six target quotients independently and add the six partial sums.
Each recursive state stores the current partial number together with the reduced numerator and denominator of \(Q\). To keep the denominator-driven search fast, the implementations repeatedly ask for the smallest prime factor of the current denominator. Those denominators can still be large 64-bit integers, so primality is tested with deterministic Miller-Rabin bases, and composite denominators are split with Pollard-Rho. A small cache avoids refactoring the same denominator many times.
At each node, the implementation extracts the smallest prime dividing the current denominator and counts its multiplicity. It then walks through exponents starting at that multiplicity, while updating \(p^e\), \(\sigma(p^e)\), and the reduced residual quotient. The branch stops as soon as one of the mathematical impossibility tests is triggered: the partial number exceeds the limit, the residual quotient drops below 1, or the lower bound \(n\,v\le 10^{18}\) fails.
The implementation also rejects any attempt to reuse a prime that is already present in the partial factorization. That enforces the canonical prime order and removes duplicates automatically.
The six half-integer targets are independent tasks, so they can be processed separately. The compiled implementations distribute them across worker threads, and the Python implementation uses multiple processes when possible. The arithmetic logic is the same in all three languages; only the surrounding execution model differs.
There is no simple closed-form running time, because the algorithm is a heavily pruned search tree rather than a regular table-filling recurrence. The practical cost is determined by how many residual states survive the pruning rules and by how expensive it is to factor the denominators that appear along those states.
Memory use is modest. The recursion depth is the number of distinct primes chosen on the current branch, and the auxiliary storage is mainly a cache of previously factored denominators plus a few larger integer temporaries for overflow-safe arithmetic. The main gain is structural: instead of iterating through all \(10^{18}\) candidates, the search visits only states that are compatible with the exact divisor-sum constraints.
Für eine positive ganze Zahl \(n\) ist der Perfectionsquotient \(\sigma(n)/n\), wobei \(\sigma(n)\) die Summe aller positiven Teiler von \(n\) bezeichnet. Gesucht ist die Summe aller \(n \le 10^{18}\), deren Perfectionsquotient eine Halbzahl ist. Für die hier verwendete Schranke zerlegen die Implementierungen die Suche in die sechs Zielwerte
$$\frac{3}{2},\ \frac{5}{2},\ \frac{7}{2},\ \frac{9}{2},\ \frac{11}{2},\ \frac{13}{2}.$$
Ein direktes Durchprobieren bis \(10^{18}\) ist unmöglich. Stattdessen wird \(n\) Primzahlpotenz für Primzahlpotenz aufgebaut, während ein exakter Restquotient verfolgt, wie weit die bisherige Teilfaktorisierung noch vom Ziel entfernt ist.
Fixiere einen Zielwert \(T=\frac{A}{2}\). Gesucht sind alle \(n\) mit
$$\frac{\sigma(n)}{n}=T.$$
Ist
$$n=\prod_i p_i^{e_i},$$
dann liefert die Multiplikativität
$$\sigma(n)=\prod_i \sigma(p_i^{e_i}),\qquad \frac{\sigma(n)}{n}=\prod_i \frac{\sigma(p_i^{e_i})}{p_i^{e_i}}.$$
Für eine einzelne Primzahlpotenz gilt
$$\sigma(p^e)=1+p+p^2+\cdots+p^e=\frac{p^{e+1}-1}{p-1},$$
also ist ihr Beitrag
$$\frac{\sigma(p^e)}{p^e}=1+\frac1p+\frac1{p^2}+\cdots+\frac1{p^e}.$$
Dieser Faktor ist stets größer als 1. Jedes Hinzufügen einer neuen Primzahlpotenz vergrößert daher \(\sigma(n)/n\) und verkleinert die Gegenrichtung \(n/\sigma(n)\).
Anstatt in jedem Knoten \(\sigma(n)/n\) neu auszurechnen, hält die Suche den gekürzten Restquotienten
$$Q(n)=T\frac{n}{\sigma(n)}=\frac{u}{v},\qquad \gcd(u,v)=1.$$
Am Start ist \(n=1\) und damit \(Q(1)=T\). Wird die aktuelle Teilfaktorisierung um eine neue Primzahlpotenz \(p^e\) erweitert, dann gilt
$$Q(np^e)=Q(n)\cdot \frac{p^e}{\sigma(p^e)}.$$
Da \(\sigma(p^e)/p^e>1\) ist, wird \(Q\) bei jedem Schritt mit einem echt kleineren Faktor multipliziert. Der Trefferfall ist genau
$$Q(n)=1 \iff T\frac{n}{\sigma(n)}=1 \iff \frac{\sigma(n)}{n}=T.$$
Die gesamte Suche ist also ein kontrollierter Abstieg von \(Q=T\) nach \(Q=1\).
Sei der aktuelle Zustand \(Q(n)=u/v\) in vollständig gekürzter Form, und sei \(m\) ein noch nicht verwendeter Kofaktor, der die Konstruktion abschließt. Dann gilt
$$1=Q(n)\frac{m}{\sigma(m)}=\frac{u}{v}\frac{m}{\sigma(m)},$$
also
$$u\,m=v\,\sigma(m).$$
Wegen \(\gcd(u,v)=1\) folgt sofort
$$v \mid m.$$
Genau diese Teilbarkeit steuert die Rekursion. Jede Primzahl, die im aktuellen Nenner auftaucht, muss später noch im offenen Restteil der Zahl erscheinen. Ist \(p\) der kleinste Primteiler von \(v\), dann muss jede vollständige Lösung eine Potenz \(p^e\) enthalten, und deshalb verzweigt die Suche ausschließlich auf dieser Primzahl \(p\).
Zugleich erhält man eine Untergrenze für den Exponenten. Gilt \(p^a \mid v\), dann muss die neue Zählerseite mindestens \(p^a\) beisteuern, um diese Nennerpotenz nach dem Kürzen beseitigen zu können. Im Updatefaktor
$$\frac{p^e}{\sigma(p^e)}$$
kommt \(p\)-adische Bewertung aber nur aus dem Zähler \(p^e\), denn \(\sigma(p^e)\equiv 1 \pmod p\). Also muss der Zweig bei \(e \ge a\) beginnen.
Sobald eine Primzahl einmal in die Teilfaktorisierung aufgenommen wurde, kehrt die Suche später nicht zu ihr zurück. Das ist keine bloße Implementationsentscheidung. Enthält eine gültige Lösung den Faktor \(p^e\), dann muss genau dieser Gesamtexponent in dem Moment gewählt werden, in dem der Nenner zuerst die Primzahl \(p\) erzwingt. Würde man \(p\) später erneut anfassen, entstünde lediglich dieselbe Endfaktorisierung in anderer Reihenfolge. Die Rekursion betrachtet daher jeden zulässigen Exponenten genau einmal.
Erstens: Wenn im gekürzten Restquotienten \(u<v\) gilt, dann ist \(Q(n)<1\). Jeder weitere Primzahlpotenzfaktor multipliziert wieder mit einer Zahl \(p^e/\sigma(p^e)<1\), also kann der Zweig niemals zu 1 zurückkehren.
Zweitens: Aus \(v\mid m\) folgt \(m\ge v\). Für jede vollständige Erweiterung \(N=nm\) gilt also
$$N \ge n\,v.$$
Sobald \(n\,v>10^{18}\) ist, kann keine Fertigstellung mehr innerhalb der Schranke liegen, und der Zweig wird sofort verworfen.
Außerdem gibt es Monotonie innerhalb der Exponentenschleife einer festen Primzahl \(p\). Der Faktor
$$\frac{p^e}{\sigma(p^e)}=\frac{1}{1+\frac1p+\cdots+\frac1{p^e}}$$
nimmt mit wachsendem \(e\) ab. Wenn also ein Exponent den Restquotienten erstmals unter 1 drückt, können größere Exponenten diesen Zweig nicht mehr retten.
Nehmen wir \(T=\frac52\). Zu Beginn ist
$$Q(1)=\frac52.$$
Der Nenner ist 2, also ist die nächste erzwungene Primzahl \(2\). Wählen wir den Exponenten \(e=3\), dann ergibt sich
$$Q(2^3)=\frac52\cdot\frac{8}{1+2+4+8}=\frac52\cdot\frac{8}{15}=\frac43.$$
Jetzt ist der Nenner 3, also wird als Nächstes die Primzahl \(3\) erzwungen. Mit Exponent \(e=1\) folgt
$$Q(2^3\cdot 3)=\frac43\cdot\frac{3}{1+3}=\frac43\cdot\frac34=1.$$
Damit gilt
$$\frac{\sigma(24)}{24}=\frac52,$$
und \(24\) ist tatsächlich ein gültiger Summand. Genau so arbeitet die gesamte Suche: Nenner lesen, kleinsten Primteiler erzwingen, zulässige Exponenten probieren, Restquotient kürzen und wiederholen.
Die C++-, Python- und Java-Implementierungen folgen demselben zahlentheoretischen Plan. Sie lösen die sechs Zielquotienten unabhängig voneinander und addieren am Ende die sechs Teilsummen.
Jeder rekursive Zustand speichert die bisherige Teilzahl zusammen mit dem gekürzten Zähler und Nenner von \(Q\). Damit die nennergesteuerte Suche schnell bleibt, benötigen die Implementierungen immer wieder den kleinsten Primfaktor des aktuellen Nenners. Diese Nenner können dennoch große 64-Bit-Zahlen sein, daher wird Primalität mit deterministischen Miller-Rabin-Basen geprüft und zusammengesetzte Nenner werden mit Pollard-Rho zerlegt. Ein kleiner Cache verhindert wiederholte Faktorisierungen derselben Werte.
In jedem Knoten wird der kleinste Primteiler des aktuellen Nenners bestimmt und seine Vielfachheit gezählt. Danach durchläuft die Implementierung Exponenten ab genau dieser Vielfachheit, aktualisiert \(p^e\), \(\sigma(p^e)\) und den gekürzten Restquotienten und prüft sofort die mathematischen Unmöglichkeitsbedingungen. Ein Zweig endet, sobald die Teilzahl die Schranke überschreitet, der Restquotient unter 1 fällt oder die Untergrenze \(n\,v\le 10^{18}\) verletzt wird.
Zusätzlich wird jeder Versuch verworfen, eine bereits benutzte Primzahl erneut einzuführen. Dadurch ist die kanonische Reihenfolge der Primzahlen direkt in der Rekursion eingebaut.
Die sechs Halbzahlziele sind voneinander unabhängig und können daher getrennt berechnet werden. Die kompilierten Implementierungen verteilen diese Aufgaben auf mehrere Threads; die Python-Implementierung nutzt, wenn möglich, mehrere Prozesse. Die mathematische Kernlogik bleibt in allen drei Sprachen identisch.
Es gibt keine einfache geschlossene Laufzeitformel, weil der Algorithmus kein gleichförmiges DP ist, sondern ein stark beschnittener Suchbaum. Die praktische Laufzeit wird durch die Anzahl der Restzustände bestimmt, die alle Abschneideregeln überleben, sowie durch die Kosten der Nennerfaktorisierungen entlang dieser Zustände.
Der Speicherbedarf ist gering. Die Rekursionstiefe entspricht der Anzahl verschiedener Primzahlen auf dem aktuellen Zweig, und zusätzlicher Speicher wird hauptsächlich für den Faktorisierungscache und einige größere Ganzzahlobjekte zur Überlaufvermeidung benötigt. Der entscheidende Gewinn ist strukturell: Statt alle Zahlen bis \(10^{18}\) zu testen, betrachtet die Suche nur noch Zustände, die mit den exakten Teilersummenbedingungen vereinbar sind.
Pozitif bir \(n\) tam sayısı için mükemmellik bölümü \(\sigma(n)/n\) olarak tanımlanır; burada \(\sigma(n)\), \(n\)'in pozitif bölenleri toplamıdır. İstenen şey, mükemmellik bölümü yarım tam sayı olan bütün \(n \le 10^{18}\) değerlerinin toplamıdır. Bu sınır için uygulamalar aramayı şu altı hedef değere ayırır:
$$\frac{3}{2},\ \frac{5}{2},\ \frac{7}{2},\ \frac{9}{2},\ \frac{11}{2},\ \frac{13}{2}.$$
\(10^{18}\)'e kadar doğrudan tarama yapmak gerçekçi değildir. Başarılı yaklaşım, \(n\)'i asal kuvvetleri tek tek ekleyerek kurmak ve aynı anda mevcut kısmi çarpanlaşmanın hedef orandan ne kadar uzak kaldığını gösteren tam bir artık oranı izlemektir.
Bir hedef değeri sabitleyelim: \(T=\frac{A}{2}\). Aradığımız sayılar
$$\frac{\sigma(n)}{n}=T$$
eşitliğini sağlayan \(n\)'lerdir.
Eğer
$$n=\prod_i p_i^{e_i}$$
ise çarpımsallıktan
$$\sigma(n)=\prod_i \sigma(p_i^{e_i}),\qquad \frac{\sigma(n)}{n}=\prod_i \frac{\sigma(p_i^{e_i})}{p_i^{e_i}}$$
elde edilir. Tek bir asal kuvvet için
$$\sigma(p^e)=1+p+p^2+\cdots+p^e=\frac{p^{e+1}-1}{p-1}$$
olduğundan katkı
$$\frac{\sigma(p^e)}{p^e}=1+\frac1p+\frac1{p^2}+\cdots+\frac1{p^e}$$
şeklindedir. Bu ifade her zaman 1'den büyüktür. Dolayısıyla yeni bir asal kuvvet eklendikçe \(\sigma(n)/n\) artar; buna karşılık \(n/\sigma(n)\) azalır.
Her düğümde \(\sigma(n)/n\)'yi baştan hesaplamak yerine arama, sadeleştirilmiş artık oranı tutar:
$$Q(n)=T\frac{n}{\sigma(n)}=\frac{u}{v},\qquad \gcd(u,v)=1.$$
Başlangıçta \(n=1\) olduğu için \(Q(1)=T\). Mevcut kısmi çarpanlaşmaya yeni bir \(p^e\) asal kuvveti eklenirse
$$Q(np^e)=Q(n)\cdot \frac{p^e}{\sigma(p^e)}$$
olur. \(\sigma(p^e)/p^e>1\) olduğu için her güncelleme \(Q\)'yu 1'den küçük bir katsayıyla çarpar. Hedef durum tam olarak
$$Q(n)=1 \iff T\frac{n}{\sigma(n)}=1 \iff \frac{\sigma(n)}{n}=T$$
şeklindedir. Yani arama, \(Q=T\)'den başlayıp kontrollü biçimde \(Q=1\)'e inmeye çalışır.
Mevcut durumda \(Q(n)=u/v\) tam sadeleştirilmiş olsun ve henüz kullanılmamış bir \(m\) çarpanı bu kısmi çözümü tamamlasın. O zaman
$$1=Q(n)\frac{m}{\sigma(m)}=\frac{u}{v}\frac{m}{\sigma(m)}$$
ve dolayısıyla
$$u\,m=v\,\sigma(m)$$
yazılır. \(\gcd(u,v)=1\) olduğundan hemen
$$v \mid m$$
sonucu çıkar. Bütün dallanma mantığı bu tek bölünebilirlikten gelir. Mevcut paydada görülen her asal, ileride tamamlayıcı çarpan içinde de görünmek zorundadır. \(v\)'nin en küçük asal bölenine \(p\) dersek, her tamamlanmış çözüm mutlaka bir \(p^e\) içerir; bu yüzden arama bir sonraki adımda yalnızca bu asal üzerinde dallanır.
Üs için de alt sınır vardır. Eğer \(p^a \mid v\) ise, bu payda kuvvetini sadeleştirebilmek için yeni payın en az \(p^a\) katkı yapması gerekir. Güncelleme katsayısı
$$\frac{p^e}{\sigma(p^e)}$$
içinde \(p\)-adik değer sadece paydaki \(p^e\)'den gelir; çünkü \(\sigma(p^e)\equiv 1 \pmod p\). Bu nedenle döngü \(e \ge a\) ile başlar.
Bir asal mevcut kısmi çarpanlaşmaya bir kez girdikten sonra arama o asala daha sonra geri dönmez. Bu keyfi bir tercih değildir. Geçerli bir çözüm \(p^e\) içeriyorsa, o tam üs değeri \(p\) asalının payda tarafından ilk kez zorlandığı anda seçilmelidir. Aynı asala daha sonra dönmek yalnızca aynı son çarpanlaşmayı farklı sırayla üretir. Böylece her uygun üs tam olarak bir kez denenmiş olur.
Birincisi: sadeleştirilmiş artık oranda \(u<v\) ise \(Q(n)<1\) olmuştur. Bundan sonra eklenecek her yeni asal kuvvet yine \(p^e/\sigma(p^e)<1\) ile çarpar; dolayısıyla dal 1'e geri dönemeden daha da aşağı iner.
İkincisi: \(v\mid m\) olduğundan \(m\ge v\) olmalıdır. O halde her tamamlanmış çözüm \(N=nm\) için
$$N \ge n\,v$$
geçerlidir. Eğer \(n\,v>10^{18}\) ise, bu dalın problem sınırı içinde tamamlanması imkansızdır.
Ayrıca sabit bir asal \(p\) için üslere göre de tek yönlü davranış vardır. Şu katsayı
$$\frac{p^e}{\sigma(p^e)}=\frac{1}{1+\frac1p+\cdots+\frac1{p^e}}$$
\(e\) büyüdükçe azalır. Dolayısıyla belli bir üs seçimi artık oranı 1'in altına düşürdüğü anda, daha büyük üsler bu dalı kurtaramaz; döngü o noktada kesilir.
\(T=\frac52\) alalım. Başlangıçta
$$Q(1)=\frac52$$
vardır. Payda 2 olduğu için bir sonraki zorunlu asal \(2\)'dir. \(e=3\) seçersek
$$Q(2^3)=\frac52\cdot\frac{8}{1+2+4+8}=\frac52\cdot\frac{8}{15}=\frac43$$
elde edilir. Artık payda 3 olduğu için sıradaki zorunlu asal \(3\)'tür. \(e=1\) alırsak
$$Q(2^3\cdot 3)=\frac43\cdot\frac{3}{1+3}=\frac43\cdot\frac34=1$$
olur. Demek ki
$$\frac{\sigma(24)}{24}=\frac52,$$
yani \(24\) geçerli sayılardan biridir. Tam arama da aynı ritimle ilerler: paydayı oku, en küçük asalını zorla, uygun üsleri dene, artık oranı sadeleştir ve ya hedefe ulaş ya da dalı buda.
C++, Python ve Java uygulamaları aynı sayı kuramı planını izler. Altı hedef oran birbirinden bağımsız çözülür ve sonunda altı kısmi toplam birleştirilir.
Her özyinelemeli durum, mevcut kısmi sayıyı ve \(Q\)'nun sadeleştirilmiş pay-payda çiftini saklar. Payda odaklı aramanın hızlı kalabilmesi için uygulamalar, o andaki paydanın en küçük asal bölenini tekrar tekrar bulur. Bu paydalar 64 bit içinde büyük sayılar olabildiğinden, asal kontrolünde deterministik Miller-Rabin tabanları kullanılır; bileşik durumlarda ise Pollard-Rho ile ayırma yapılır. Küçük bir önbellek aynı paydayı tekrar tekrar çarpanlara ayırmayı önler.
Her düğümde güncel paydanın en küçük asal böleni çıkarılır ve kaç kez geçtiği sayılır. Sonra üsler tam bu çokluktan başlayarak denenir; her adımda \(p^e\), \(\sigma(p^e)\) ve sadeleştirilmiş artık oran güncellenir. Kısmi sayı sınırı aşınca, artık oran 1'in altına düşünce veya \(n\,v\le 10^{18}\) alt sınırı bozulunca dal hemen sonlandırılır.
Uygulama ayrıca, mevcut kısmi çarpanlaşmada zaten kullanılan bir asalı yeniden kullanma girişimlerini reddeder. Böylece kanonik asal sırası doğrudan korunur ve yinelenen üretimler kendiliğinden yok olur.
Altı yarım tam sayı hedefi bağımsız iş yükleridir; bu yüzden ayrı ayrı çalıştırılabilirler. Derlenmiş sürümler bunları iş parçacıklarına dağıtır, Python sürümü ise uygun olduğunda çoklu süreç kullanır. Üç dilde de aritmetik mantık aynıdır; değişen kısım yalnızca yürütme modelidir.
Çalışma süresi için basit kapalı bir form yoktur; çünkü algoritma düzenli bir tablo doldurma yöntemi değil, yoğun biçimde budanmış bir arama ağacıdır. Pratik maliyeti belirleyen şey, budama testlerinden geçebilen artık durum sayısı ve bu durumlarda karşılaşılan paydaların çarpanlara ayrılma maliyetidir.
Bellek kullanımı düşüktür. Özyineleme derinliği, o anda seçilmiş farklı asal sayısı kadardır; ek veri olarak çoğunlukla daha önce ayrıştırılmış paydalar için küçük bir önbellek ve taşmayı güvenli yönetmek için birkaç büyük tamsayı nesnesi tutulur. Asıl kazanç yapısaldır: \(10^{18}\) adayı tek tek sınamak yerine, yalnızca bölen-toplam kısıtlarıyla uyumlu olabilecek durumlar ziyaret edilir.
Para un entero positivo \(n\), el cociente de perfección es \(\sigma(n)/n\), donde \(\sigma(n)\) es la suma de los divisores positivos de \(n\). La tarea consiste en sumar todos los \(n \le 10^{18}\) cuyo cociente de perfección es un semientero. Para el límite usado aquí, las implementaciones dividen la búsqueda en los seis objetivos
$$\frac{3}{2},\ \frac{5}{2},\ \frac{7}{2},\ \frac{9}{2},\ \frac{11}{2},\ \frac{13}{2}.$$
Recorrer todos los enteros hasta \(10^{18}\) es imposible. La idea efectiva es construir \(n\) potencia prima por potencia prima y mantener al mismo tiempo un cociente residual exacto que mide cuánto falta para alcanzar el objetivo elegido.
Fijemos un objetivo \(T=\frac{A}{2}\). Queremos todos los \(n\) tales que
$$\frac{\sigma(n)}{n}=T.$$
Si
$$n=\prod_i p_i^{e_i},$$
entonces la multiplicatividad da
$$\sigma(n)=\prod_i \sigma(p_i^{e_i}),\qquad \frac{\sigma(n)}{n}=\prod_i \frac{\sigma(p_i^{e_i})}{p_i^{e_i}}.$$
Para una sola potencia prima,
$$\sigma(p^e)=1+p+p^2+\cdots+p^e=\frac{p^{e+1}-1}{p-1},$$
y por tanto su contribución es
$$\frac{\sigma(p^e)}{p^e}=1+\frac1p+\frac1{p^2}+\cdots+\frac1{p^e}.$$
Ese factor siempre es mayor que 1. Por lo tanto, cada nueva potencia prima hace crecer \(\sigma(n)/n\), mientras que la cantidad recíproca \(n/\sigma(n)\) disminuye.
En lugar de recalcular \(\sigma(n)/n\) desde cero en cada nodo, la búsqueda mantiene el cociente residual reducido
$$Q(n)=T\frac{n}{\sigma(n)}=\frac{u}{v},\qquad \gcd(u,v)=1.$$
En la raíz, \(n=1\), así que \(Q(1)=T\). Si ampliamos la factorización parcial con una nueva potencia prima \(p^e\), entonces
$$Q(np^e)=Q(n)\cdot \frac{p^e}{\sigma(p^e)}.$$
Como \(\sigma(p^e)/p^e>1\), cada actualización multiplica \(Q\) por un factor estrictamente menor que 1. La condición de éxito es exactamente
$$Q(n)=1 \iff T\frac{n}{\sigma(n)}=1 \iff \frac{\sigma(n)}{n}=T.$$
Toda la búsqueda puede verse así como un descenso controlado desde \(Q=T\) hasta \(Q=1\).
Supongamos que el estado actual es \(Q(n)=u/v\) en forma reducida y que un cofactor todavía no usado \(m\) completa la construcción. Entonces
$$1=Q(n)\frac{m}{\sigma(m)}=\frac{u}{v}\frac{m}{\sigma(m)},$$
de modo que
$$u\,m=v\,\sigma(m).$$
Como \(\gcd(u,v)=1\), se deduce
$$v \mid m.$$
Esa divisibilidad explica toda la estrategia de ramificación. Todo primo que aparezca en el denominador actual tendrá que aparecer más adelante en la parte incompleta del número. Si \(p\) es el menor primo que divide a \(v\), cualquier extensión válida debe contener alguna potencia \(p^e\), y por eso la recursión solo ramifica sobre ese primo \(p\).
Además, el exponente tiene una cota inferior. Si \(p^a \mid v\), el nuevo numerador debe aportar al menos \(p^a\) para poder cancelar esa potencia del denominador al reducir la fracción. En el factor de actualización
$$\frac{p^e}{\sigma(p^e)}$$
la única fuente de valuación \(p\)-ádica en el numerador es \(p^e\), porque \(\sigma(p^e)\equiv 1 \pmod p\). Por eso el bucle de exponentes empieza en \(e \ge a\).
Una vez que un primo entra en la factorización parcial, la búsqueda no vuelve a ese primo más tarde. No es una restricción artificial. Si una solución válida contiene \(p^e\), ese exponente total debe elegirse justo cuando el denominador obliga por primera vez a introducir \(p\). Volver a usar \(p\) más adelante solo reconstruiría el mismo número final en un orden distinto. Así, cada exponente admisible se explora exactamente una vez.
Primero, si en el cociente residual reducido se cumple \(u<v\), entonces \(Q(n)<1\). A partir de ese punto, cualquier nueva potencia prima vuelve a multiplicar por un factor \(p^e/\sigma(p^e)<1\), de modo que la rama nunca podrá regresar a 1.
Segundo, de \(v\mid m\) se sigue que \(m\ge v\). Por tanto, toda extensión completa \(N=nm\) satisface
$$N \ge n\,v.$$
Si \(n\,v>10^{18}\), la rama ya no puede terminar dentro del límite del problema y se descarta sin seguir profundizando.
Además hay monotonicidad dentro del bucle de exponentes de un primo fijo. El factor
$$\frac{p^e}{\sigma(p^e)}=\frac{1}{1+\frac1p+\cdots+\frac1{p^e}}$$
disminuye cuando \(e\) crece. En consecuencia, una vez que cierto exponente hace caer el cociente residual por debajo de 1, exponentes mayores ya no pueden rescatar la rama.
Tomemos \(T=\frac52\). Al inicio
$$Q(1)=\frac52.$$
El denominador es 2, así que el siguiente primo forzado es \(2\). Si elegimos \(e=3\), obtenemos
$$Q(2^3)=\frac52\cdot\frac{8}{1+2+4+8}=\frac52\cdot\frac{8}{15}=\frac43.$$
Ahora el denominador es 3, por lo que el siguiente primo forzado es \(3\). Tomando \(e=1\),
$$Q(2^3\cdot 3)=\frac43\cdot\frac{3}{1+3}=\frac43\cdot\frac34=1.$$
Por tanto,
$$\frac{\sigma(24)}{24}=\frac52,$$
y \(24\) es uno de los enteros buscados. El ejemplo muestra exactamente el ciclo real de la búsqueda: leer el denominador, forzar su menor primo, probar exponentes admisibles, reducir el cociente residual y repetir hasta llegar a 1 o podar la rama.
Las implementaciones en C++, Python y Java siguen el mismo plan aritmético. Resuelven los seis objetivos por separado y luego suman los resultados parciales.
Cada estado recursivo guarda el número parcial actual junto con el numerador y el denominador reducidos de \(Q\). Para que la búsqueda guiada por el denominador sea rápida, las implementaciones necesitan repetidamente el menor factor primo del denominador actual. Como esos denominadores todavía pueden ser enteros grandes de 64 bits, la primalidad se comprueba con bases deterministas de Miller-Rabin y los compuestos se separan con Pollard-Rho. Un pequeño caché evita factorizar el mismo denominador varias veces.
En cada nodo, la implementación extrae el menor primo que divide al denominador y cuenta su multiplicidad. A continuación recorre exponentes empezando exactamente en esa multiplicidad, actualizando \(p^e\), \(\sigma(p^e)\) y el cociente residual reducido. La rama termina en cuanto aparece una imposibilidad matemática: el número parcial supera el límite, el cociente residual cae por debajo de 1 o falla la cota \(n\,v\le 10^{18}\).
La implementación también rechaza cualquier intento de reutilizar un primo ya presente en la factorización parcial. Con eso se impone de forma automática el orden canónico de los primos y se eliminan los duplicados.
Los seis semienteros objetivo son independientes, de modo que pueden resolverse como tareas separadas. Las versiones compiladas los distribuyen entre varios hilos de trabajo, mientras que la versión de Python usa varios procesos cuando resulta posible. La lógica aritmética es la misma en los tres lenguajes; lo que cambia es solo el modelo de ejecución.
No hay una fórmula cerrada sencilla para el tiempo de ejecución, porque el algoritmo no es una recurrencia uniforme sino un árbol de búsqueda muy podado. El coste real viene dado por el número de estados residuales que sobreviven a las podas y por el precio de factorizar los denominadores que aparecen en esos estados.
El uso de memoria es moderado. La profundidad de la recursión coincide con el número de primos distintos elegidos en la rama actual, y el almacenamiento auxiliar consiste sobre todo en un caché de denominadores ya factorizados y algunos enteros más grandes para hacer segura la aritmética frente a desbordamientos. La mejora decisiva es estructural: en vez de examinar todos los enteros hasta \(10^{18}\), solo se visitan estados compatibles con las restricciones exactas de la suma de divisores.
对正整数 \(n\)，其“完美商”是 \(\sigma(n)/n\)，其中 \(\sigma(n)\) 表示 \(n\) 的所有正因数之和。本题要求把所有满足 \(n \le 10^{18}\) 且完美商为半整数的 \(n\) 全部求和。针对这里的上界，三份实现把搜索拆成六个目标值：
$$\frac{3}{2},\ \frac{5}{2},\ \frac{7}{2},\ \frac{9}{2},\ \frac{11}{2},\ \frac{13}{2}.$$
如果从 1 一直枚举到 \(10^{18}\)，计算量完全不可接受。真正可行的方法是按“素数幂”逐步构造 \(n\)，并在整个过程中维护一个精确的剩余商，用它描述当前部分分解离目标商还有多远。
固定一个目标值 \(T=\frac{A}{2}\)。我们要求所有满足
$$\frac{\sigma(n)}{n}=T$$
的整数 \(n\)。
若
$$n=\prod_i p_i^{e_i},$$
则由 \(\sigma\) 的乘法性可得
$$\sigma(n)=\prod_i \sigma(p_i^{e_i}),\qquad \frac{\sigma(n)}{n}=\prod_i \frac{\sigma(p_i^{e_i})}{p_i^{e_i}}.$$
对单个素数幂，有
$$\sigma(p^e)=1+p+p^2+\cdots+p^e=\frac{p^{e+1}-1}{p-1},$$
因此它对完美商的贡献是
$$\frac{\sigma(p^e)}{p^e}=1+\frac1p+\frac1{p^2}+\cdots+\frac1{p^e}.$$
这个因子总是大于 1。也就是说，每加入一个新的素数幂，\(\sigma(n)/n\) 就会上升；反过来看，\(n/\sigma(n)\) 会下降。
搜索并不是在每个节点重新计算一次 \(\sigma(n)/n\)，而是维护下面这个约分后的剩余商：
$$Q(n)=T\frac{n}{\sigma(n)}=\frac{u}{v},\qquad \gcd(u,v)=1.$$
起点是 \(n=1\)，所以 \(Q(1)=T\)。如果把当前部分分解扩展为再乘上一个新的素数幂 \(p^e\)，就有
$$Q(np^e)=Q(n)\cdot \frac{p^e}{\sigma(p^e)}.$$
由于 \(\sigma(p^e)/p^e>1\)，每次更新都在把 \(Q\) 乘上一个严格小于 1 的因子。目标状态正好是
$$Q(n)=1 \iff T\frac{n}{\sigma(n)}=1 \iff \frac{\sigma(n)}{n}=T.$$
因此整棵搜索树可以理解为：从 \(Q=T\) 出发，沿着合法的素数幂选择不断下降，直到恰好落在 \(Q=1\) 上。
设当前状态已经化成最简分数 \(Q(n)=u/v\)，并且某个还未使用的余因子 \(m\) 能把它补成完整解。那么
$$1=Q(n)\frac{m}{\sigma(m)}=\frac{u}{v}\frac{m}{\sigma(m)},$$
等价于
$$u\,m=v\,\sigma(m).$$
因为 \(\gcd(u,v)=1\)，立刻得到
$$v \mid m.$$
这条整除关系就是整个搜索策略的核心。当前分母里出现的每一个素数，将来都必须出现在尚未补上的那一部分里。设 \(p\) 是 \(v\) 的最小素因子，那么任何完整解都必须含有某个 \(p^e\)，于是递归只需要在这个素数 \(p\) 上分支。
指数还有一个下界。若 \(p^a \mid v\)，那么新的分子至少要额外提供 \(p^a\) 的 \(p\)-进赋值，才能把分母中的这部分抵消掉。更新因子
$$\frac{p^e}{\sigma(p^e)}$$
中，分子里的 \(p^e\) 是唯一会贡献新的 \(p\)-因子的地方，因为 \(\sigma(p^e)\equiv 1 \pmod p\)。所以指数循环必须从 \(e \ge a\) 开始。
某个素数一旦被加入当前部分分解，搜索之后就不会再回头补这个素数。这不是随意的实现细节，而是数学上的规范顺序。若一个有效解最终包含 \(p^e\)，那么完整的指数 \(e\) 必须在分母第一次强迫引入素数 \(p\) 的那一刻一次性决定。若以后再回来补 \(p\)，只会把同一个最终分解换一种顺序再生成一遍。于是每个允许的指数组合只会被访问一次。
第一条：如果约分后的剩余商满足 \(u<v\)，也就是 \(Q(n)<1\)，那么这条分支已经“降过头”了。以后无论再乘上哪个新的素数幂，都会继续乘上一个 \(p^e/\sigma(p^e)<1\) 的因子，因此不可能再回到 1。
第二条：由 \(v\mid m\) 可知 \(m\ge v\)。因此任意完整解 \(N=nm\) 都满足
$$N \ge n\,v.$$
只要 \(n\,v>10^{18}\)，这条分支就不可能在题目上界内补完，可以立刻丢弃。
对固定素数 \(p\) 的指数循环，还有一个局部单调性：
$$\frac{p^e}{\sigma(p^e)}=\frac{1}{1+\frac1p+\cdots+\frac1{p^e}}$$
随着 \(e\) 增大而减小。所以一旦某个指数已经让剩余商跌到 1 以下，更大的指数只会更糟，该循环就可以直接停止。
取 \(T=\frac52\)。起始状态是
$$Q(1)=\frac52.$$
当前分母是 2，因此下一个被强制引入的素数是 \(2\)。若选择指数 \(e=3\)，则
$$Q(2^3)=\frac52\cdot\frac{8}{1+2+4+8}=\frac52\cdot\frac{8}{15}=\frac43.$$
此时分母变成 3，所以下一个强制素数是 \(3\)。再取指数 \(e=1\)，得到
$$Q(2^3\cdot 3)=\frac43\cdot\frac{3}{1+3}=\frac43\cdot\frac34=1.$$
于是
$$\frac{\sigma(24)}{24}=\frac52,$$
也就是说 \(24\) 确实是题目要计入的整数之一。这个例子完整展示了搜索的节奏：读取分母，强制其最小素因子，尝试所有合法指数，约分剩余商，然后继续，直到命中 \(Q=1\) 或触发剪枝。
C++、Python 和 Java 三个实现遵循完全相同的数论框架。它们分别处理六个目标半整数，最后把六部分结果相加。
每个递归状态都保存当前的部分数值，以及 \(Q\) 的约分后分子和分母。由于搜索始终由分母驱动，程序需要反复求当前分母的最小素因子。这些分母虽然仍然落在 64 位范围内，但可能很大，因此实现使用确定性的 Miller-Rabin 基组进行素性判断，再用 Pollard-Rho 拆分合数分母。为了避免重复工作，还会缓存已经分解过的分母。
在每个节点，程序先取出当前分母的最小素因子，再统计它在分母中的重数。随后从这个重数开始枚举指数，并同步更新 \(p^e\)、\(\sigma(p^e)\) 以及约分后的剩余商。一旦发现数学上已经不可能成功，分支就立即停止：部分数超出上界、剩余商降到 1 以下，或者下界条件 \(n\,v\le 10^{18}\) 被破坏。
程序也禁止再次使用已经出现在当前部分分解中的素数。这样做正好实现了上面的规范顺序，因此不会生成重复的最终分解。
六个目标值彼此独立，因此可以当作六个单独任务处理。编译型实现把这些任务分配到多个工作线程，Python 实现则在合适时使用多进程。三种语言的差别只在外围执行方式，核心算术逻辑完全一致。
这个算法没有一个简洁的封闭时间公式，因为它不是规则的动态规划，而是一棵经过强力剪枝的搜索树。实际运行时间取决于有多少剩余状态能够通过剪枝，以及这些状态上出现的分母分解起来有多贵。
内存占用并不高。递归深度等于当前分支中已选素数的个数，额外空间主要来自已分解分母的缓存，以及为防止溢出而保留的少量大整数中间量。真正的效率来源于结构性约束：程序并不暴力检查所有不超过 \(10^{18}\) 的整数，而只访问那些与精确除数和条件相容的状态。
Для положительного целого \(n\) коэффициент совершенства равен \(\sigma(n)/n\), где \(\sigma(n)\) обозначает сумму положительных делителей числа \(n\). Нужно просуммировать все \(n \le 10^{18}\), для которых этот коэффициент является полуцелым числом. Для используемой здесь границы реализации разбивают поиск на шесть целевых значений
$$\frac{3}{2},\ \frac{5}{2},\ \frac{7}{2},\ \frac{9}{2},\ \frac{11}{2},\ \frac{13}{2}.$$
Полный перебор до \(10^{18}\) невозможен. Рабочая идея состоит в том, чтобы строить \(n\) по простым степеням и одновременно вести точную остаточную дробь, показывающую, насколько текущая частичная факторизация далека от выбранного целевого коэффициента.
Зафиксируем одну цель \(T=\frac{A}{2}\). Требуется найти все \(n\), для которых
$$\frac{\sigma(n)}{n}=T.$$
Если
$$n=\prod_i p_i^{e_i},$$
то по мультипликативности получаем
$$\sigma(n)=\prod_i \sigma(p_i^{e_i}),\qquad \frac{\sigma(n)}{n}=\prod_i \frac{\sigma(p_i^{e_i})}{p_i^{e_i}}.$$
Для одной простой степени имеем
$$\sigma(p^e)=1+p+p^2+\cdots+p^e=\frac{p^{e+1}-1}{p-1},$$
поэтому вклад равен
$$\frac{\sigma(p^e)}{p^e}=1+\frac1p+\frac1{p^2}+\cdots+\frac1{p^e}.$$
Этот множитель всегда больше 1. Значит, каждое добавление новой простой степени увеличивает \(\sigma(n)/n\), а величина \(n/\sigma(n)\) при этом уменьшается.
Вместо того чтобы каждый раз пересчитывать \(\sigma(n)/n\), поиск хранит сокращенную остаточную дробь
$$Q(n)=T\frac{n}{\sigma(n)}=\frac{u}{v},\qquad \gcd(u,v)=1.$$
В корне \(n=1\), поэтому \(Q(1)=T\). Если текущую частичную факторизацию расширить новой степенью \(p^e\), то
$$Q(np^e)=Q(n)\cdot \frac{p^e}{\sigma(p^e)}.$$
Поскольку \(\sigma(p^e)/p^e>1\), на каждом шаге \(Q\) умножается на число, строго меньшее 1. Точное условие успеха выглядит так:
$$Q(n)=1 \iff T\frac{n}{\sigma(n)}=1 \iff \frac{\sigma(n)}{n}=T.$$
Тем самым вся рекурсия представляет собой управляемое движение от \(Q=T\) вниз к \(Q=1\).
Пусть в текущем состоянии \(Q(n)=u/v\) уже сокращена, и существует еще не использованный множитель \(m\), который завершает решение. Тогда
$$1=Q(n)\frac{m}{\sigma(m)}=\frac{u}{v}\frac{m}{\sigma(m)},$$
то есть
$$u\,m=v\,\sigma(m).$$
Так как \(\gcd(u,v)=1\), отсюда немедленно следует
$$v \mid m.$$
Именно эта делимость управляет ветвлением. Каждый простой, который уже сидит в текущем знаменателе, обязан позже появиться в недостроенной части числа. Если \(p\) — наименьший простой делитель \(v\), то любое продолжение обязано содержать некоторую степень \(p^e\). Поэтому рекурсия ветвится только по этому простому \(p\).
Кроме того, для показателя степени есть нижняя граница. Если \(p^a \mid v\), то новый числитель обязан принести как минимум \(p^a\), чтобы после сокращения убрать эту степень из знаменателя. В множителе обновления
$$\frac{p^e}{\sigma(p^e)}$$
единственный источник новой \(p\)-адической оценки в числителе — это сам множитель \(p^e\), потому что \(\sigma(p^e)\equiv 1 \pmod p\). Поэтому цикл по показателям начинается с \(e \ge a\).
Как только некоторый простой уже включен в частичную факторизацию, поиск больше не возвращается к нему позже. Это не просто техническое удобство. Если допустимое решение содержит \(p^e\), то полный показатель \(e\) должен быть выбран ровно в тот момент, когда знаменатель впервые вынуждает добавить простой \(p\). Поздний возврат к тому же простому лишь воспроизвел бы ту же конечную факторизацию в другом порядке. Поэтому каждая допустимая комбинация рассматривается единственный раз.
Во-первых, если в сокращенной остаточной дроби \(u<v\), то \(Q(n)<1\). После этого любое новое простое звено снова умножает на фактор \(p^e/\sigma(p^e)<1\), так что вернуться к 1 уже невозможно.
Во-вторых, из \(v\mid m\) следует \(m\ge v\). Значит, для любого полного продолжения \(N=nm\) верно
$$N \ge n\,v.$$
Если \(n\,v>10^{18}\), ветвь уже не может дать допустимое число в пределах условия и отсекается немедленно.
Есть и локальная монотонность внутри цикла по показателям для фиксированного простого \(p\). Величина
$$\frac{p^e}{\sigma(p^e)}=\frac{1}{1+\frac1p+\cdots+\frac1{p^e}}$$
убывает при росте \(e\). Следовательно, как только некоторый показатель опускает остаточную дробь ниже 1, большие показатели уже не могут восстановить ветвь.
Возьмем \(T=\frac52\). В начале
$$Q(1)=\frac52.$$
Знаменатель равен 2, значит, следующий принудительный простой — это \(2\). Если взять показатель \(e=3\), получаем
$$Q(2^3)=\frac52\cdot\frac{8}{1+2+4+8}=\frac52\cdot\frac{8}{15}=\frac43.$$
Теперь знаменатель равен 3, поэтому следующим вынужденным простым становится \(3\). При \(e=1\) имеем
$$Q(2^3\cdot 3)=\frac43\cdot\frac{3}{1+3}=\frac43\cdot\frac34=1.$$
Следовательно,
$$\frac{\sigma(24)}{24}=\frac52,$$
то есть \(24\) действительно входит в искомую сумму. Пример показывает точный ритм алгоритма: читаем знаменатель, вынуждаем его наименьший простой, перебираем допустимые показатели, сокращаем остаточную дробь и повторяем процесс до попадания в \(Q=1\) или до отсечения.
Реализации на C++, Python и Java используют один и тот же арифметический план. Они независимо решают шесть целевых задач, а затем складывают частичные суммы.
Каждое рекурсивное состояние хранит текущее частичное число и сокращенные числитель со знаменателем для \(Q\). Поскольку поиск управляется знаменателем, реализации постоянно находят наименьший простой делитель текущего знаменателя. Эти знаменатели все еще могут быть большими 64-битными числами, поэтому простота проверяется детерминированным набором оснований Miller-Rabin, а составные значения раскладываются алгоритмом Pollard-Rho. Небольшой кэш не дает факторизовать один и тот же знаменатель повторно.
В каждой вершине код извлекает наименьший простой делитель знаменателя и считает его кратность. Затем показатели перебираются начиная ровно с этой кратности, одновременно обновляются \(p^e\), \(\sigma(p^e)\) и сокращенная остаточная дробь. Ветвь завершается сразу, как только обнаруживается математическая невозможность: частичное число выходит за предел, остаточная дробь падает ниже 1 или нарушается нижняя оценка \(n\,v\le 10^{18}\).
Также запрещается повторно использовать простой, который уже присутствует в текущей частичной факторизации. Это и реализует канонический порядок простых, автоматически устраняя дубли.
Шесть полуцелых целей независимы друг от друга, поэтому их удобно решать как отдельные задачи. Компилируемые реализации распределяют их по рабочим потокам, а версия на Python при возможности использует несколько процессов. Во всех трех языках меняется только модель исполнения; арифметическая логика остается той же самой.
Простой замкнутой формулы для времени работы здесь нет, потому что алгоритм представляет собой сильно прореженное дерево поиска, а не регулярную динамику по таблице. Практическая стоимость определяется числом остаточных состояний, переживших отсечения, и ценой факторизации знаменателей, которые встречаются на этих состояниях.
Память расходуется умеренно. Глубина рекурсии равна числу различных простых, выбранных в текущей ветви, а дополнительное пространство занимает в основном кэш уже факторизованных знаменателей и несколько более крупных целых объектов для безопасной арифметики без переполнения. Главный выигрыш носит структурный характер: вместо перебора всех чисел до \(10^{18}\) алгоритм посещает только состояния, совместимые с точными условиями на сумму делителей.
لأي عدد صحيح موجب \(n\)، يُعرَّف معامل الكمال على أنه \(\sigma(n)/n\)، حيث تمثل \(\sigma(n)\) مجموع القواسم الموجبة للعدد \(n\). المطلوب هو جمع كل الأعداد \(n \le 10^{18}\) التي يكون فيها هذا المعامل نصف عدد صحيح. ضمن الحد المستخدم هنا، تقسّم التطبيقات البحث إلى القيم الست التالية:
$$\frac{3}{2},\ \frac{5}{2},\ \frac{7}{2},\ \frac{9}{2},\ \frac{11}{2},\ \frac{13}{2}.$$
الفحص المباشر لكل الأعداد حتى \(10^{18}\) غير ممكن عملياً. الفكرة الفعالة هي بناء \(n\) على شكل حاصل ضرب لقوى أولية، مع تتبع كسر متبقٍّ دقيق يعبّر في كل لحظة عن المسافة بين التحليل الجزئي الحالي وبين القيمة الهدف المختارة.
لنثبت هدفاً واحداً \(T=\frac{A}{2}\). نريد كل \(n\) التي تحقق
$$\frac{\sigma(n)}{n}=T.$$
إذا كان
$$n=\prod_i p_i^{e_i},$$
فإن خاصية الضرب تعطي
$$\sigma(n)=\prod_i \sigma(p_i^{e_i}),\qquad \frac{\sigma(n)}{n}=\prod_i \frac{\sigma(p_i^{e_i})}{p_i^{e_i}}.$$
ولقوة أولية واحدة نحصل على
$$\sigma(p^e)=1+p+p^2+\cdots+p^e=\frac{p^{e+1}-1}{p-1},$$
ومن ثم يكون إسهامها في معامل الكمال هو
$$\frac{\sigma(p^e)}{p^e}=1+\frac1p+\frac1{p^2}+\cdots+\frac1{p^e}.$$
هذا العامل أكبر دائماً من 1، ولذلك فإن إضافة أي قوة أولية جديدة ترفع \(\sigma(n)/n\)، بينما تجعل الكمية المعاكسة \(n/\sigma(n)\) أصغر.
بدلاً من إعادة حساب \(\sigma(n)/n\) من الصفر في كل عقدة، يحتفظ البحث بالكسر المتبقي المختزل
$$Q(n)=T\frac{n}{\sigma(n)}=\frac{u}{v},\qquad \gcd(u,v)=1.$$
عند البداية يكون \(n=1\)، وبالتالي \(Q(1)=T\). وإذا وسّعنا التحليل الجزئي الحالي بإضافة قوة أولية جديدة \(p^e\)، فإن
$$Q(np^e)=Q(n)\cdot \frac{p^e}{\sigma(p^e)}.$$
وبما أن \(\sigma(p^e)/p^e>1\)، فإن كل تحديث يضرب \(Q\) بعامل أصغر من 1. أما شرط النجاح الدقيق فهو
$$Q(n)=1 \iff T\frac{n}{\sigma(n)}=1 \iff \frac{\sigma(n)}{n}=T.$$
بهذا تصبح عملية البحث كلها نزولاً مضبوطاً من \(Q=T\) إلى \(Q=1\).
لنفترض أن الحالة الحالية هي \(Q(n)=u/v\) في أبسط صورة، وأن هناك عاملاً مكملاً غير مستخدم بعد اسمه \(m\) يكمل البناء. عندئذ
$$1=Q(n)\frac{m}{\sigma(m)}=\frac{u}{v}\frac{m}{\sigma(m)},$$
أي أن
$$u\,m=v\,\sigma(m).$$
وبما أن \(\gcd(u,v)=1\)، فهذا يفرض
$$v \mid m.$$
هذه العلاقة هي قلب الاستراتيجية كلها. كل عامل أولي يظهر في المقام الحالي لا بد أن يظهر لاحقاً في الجزء غير المكتمل من العدد. إذا كان \(p\) أصغر عامل أولي للمقام \(v\)، فإن أي إكمال صحيح لا بد أن يحتوي على قوة من الشكل \(p^e\)، ولهذا السبب لا تتشعب العودية إلا على هذا العامل \(p\).
وهناك أيضاً حد أدنى للأس. إذا كان \(p^a \mid v\)، فلابد أن يزوّد البسط الجديد ما لا يقل عن \(p^a\) حتى يمكن إلغاء هذه القوة من المقام بعد الاختزال. وفي عامل التحديث
$$\frac{p^e}{\sigma(p^e)}$$
فإن المصدر الوحيد لتقييم \(p\)-الأدي في البسط هو \(p^e\) نفسه، لأن \(\sigma(p^e)\equiv 1 \pmod p\). لذلك يبدأ التفرع من \(e \ge a\).
بمجرد أن يدخل عامل أولي في التحليل الجزئي الحالي، لا يعود البحث إليه مرة ثانية لاحقاً. هذا ليس مجرد قرار برمجي. إذا كانت هناك قيمة صحيحة تحتوي في النهاية على \(p^e\)، فيجب اختيار هذا الأس الكامل في اللحظة التي يفرض فيها المقام العامل \(p\) لأول مرة. أما العودة إلى \(p\) لاحقاً فلن تفعل إلا إعادة بناء العدد النهائي نفسه بترتيب مختلف. وهكذا تُفحص كل حالة مقبولة مرة واحدة فقط.
القاعدة الأولى: إذا تحقق \(u<v\) في الكسر المتبقي المختزل، فهذا يعني أن \(Q(n)<1\). ومنذ تلك اللحظة فإن أي قوة أولية إضافية ستضرب \(Q\) بعامل آخر من النوع \(p^e/\sigma(p^e)<1\)، وبالتالي لن يستطيع الفرع الرجوع أبداً إلى 1.
القاعدة الثانية: من العلاقة \(v\mid m\) نحصل على \(m\ge v\). لذلك فإن كل إكمال نهائي \(N=nm\) يحقق
$$N \ge n\,v.$$
فإذا صار \(n\,v>10^{18}\)، استحال أن ينتج هذا الفرع حلاً داخل الحد المطلوب، ويمكن قطعه فوراً.
وهناك أيضاً رتابة محلية داخل حلقة الأسس لعامل أولي ثابت \(p\). فالعامل
$$\frac{p^e}{\sigma(p^e)}=\frac{1}{1+\frac1p+\cdots+\frac1{p^e}}$$
يتناقص عندما يكبر \(e\). لذا، إذا جعل أس معيّن الكسر المتبقي يهبط تحت 1، فلن تستطيع الأسس الأكبر إصلاح ذلك الفرع.
لنأخذ \(T=\frac52\). في البداية
$$Q(1)=\frac52.$$
المقام الحالي هو 2، ولذلك فإن العامل الأولي المفروض تاليًا هو \(2\). إذا اخترنا \(e=3\)، نحصل على
$$Q(2^3)=\frac52\cdot\frac{8}{1+2+4+8}=\frac52\cdot\frac{8}{15}=\frac43.$$
أصبح المقام الآن 3، ولذلك يكون العامل الأولي المفروض التالي هو \(3\). وعند أخذ \(e=1\) نحصل على
$$Q(2^3\cdot 3)=\frac43\cdot\frac{3}{1+3}=\frac43\cdot\frac34=1.$$
إذن
$$\frac{\sigma(24)}{24}=\frac52,$$
وبالتالي فإن \(24\) عدد صحيح مطلوب في المجموع. يوضح هذا المثال الدورة الكاملة للخوارزمية: قراءة المقام، فرض أصغر عامله الأولي، تجربة الأسس المقبولة، اختزال الكسر المتبقي، ثم التكرار حتى الوصول إلى \(Q=1\) أو تفعيل إحدى قواعد القص.
تتبع تطبيقات C++ وPython وJava الخطة العددية نفسها. فهي تحل القيم الست المستهدفة كلًّا على حدة، ثم تجمع المجاميع الجزئية في النهاية.
كل حالة عودية تخزن العدد الجزئي الحالي مع البسط والمقام بعد الاختزال للكسر \(Q\). ولأن البحث موجه بالمقام، تحتاج التطبيقات بشكل متكرر إلى أصغر عامل أولي للمقام الحالي. هذه المقامات قد تبقى كبيرة ضمن مجال 64 بت، لذلك يُستخدم اختبار Miller-Rabin الحتمي لفحص الأولية، ويُستخدم Pollard-Rho لتفكيك المقامات المركبة. كما يُحتفظ بذاكرة صغيرة حتى لا يُعاد تحليل المقام نفسه مرات كثيرة.
في كل عقدة، يستخرج التنفيذ أصغر عامل أولي للمقام الحالي ويحسب تكراره. ثم يجرّب الأسس ابتداءً من هذا التكرار نفسه، مع تحديث \(p^e\) و\(\sigma(p^e)\) والكسر المتبقي المختزل في كل خطوة. ويتوقف الفرع فور ظهور استحالة رياضية: تجاوز العدد الجزئي للحد، أو هبوط الكسر المتبقي تحت 1، أو فشل الشرط السفلي \(n\,v\le 10^{18}\).
كما يمنع التنفيذ إعادة استخدام عامل أولي سبق أن دخل في التحليل الجزئي. وهذا يحقق تلقائياً الترتيب القانوني للعوامل الأولية ويزيل التكرارات.
القيم الست النصفية مستقلة تماماً، ولذلك يمكن التعامل معها كمهام منفصلة. الإصدارات المترجمة توزعها على خيوط عمل متعددة، بينما تستخدم نسخة Python عمليات متعددة عند الإمكان. المنطق الحسابي نفسه لا يتغير بين اللغات الثلاث، وإنما يختلف فقط أسلوب التنفيذ المحيط به.
لا توجد صيغة مغلقة بسيطة لزمن التنفيذ، لأن الخوارزمية ليست علاقة عودية منتظمة بل شجرة بحث خضعت لقص قوي. الكلفة العملية تحددها كمية الحالات المتبقية التي تنجو من اختبارات القص، إضافة إلى كلفة تحليل المقامات التي تظهر في تلك الحالات.
استهلاك الذاكرة محدود. عمق العودية يساوي عدد العوامل الأولية المختلفة المختارة في الفرع الحالي، أما الذاكرة الإضافية فمعظمها يذهب إلى ذاكرة تخزين المقامات المحللة مسبقاً وبعض القيم الصحيحة الأكبر المستخدمة لحساب آمن من فيضان السعة. الفائدة الأساسية هنا بنيوية: بدلاً من اختبار كل الأعداد حتى \(10^{18}\)، لا يزور البحث إلا الحالات المتوافقة مع القيود الدقيقة لدالة مجموع القواسم.