Let \(F(n)\) be the number of tuples \((a,b,c,e,f)\) of positive integers satisfying
$$a^e+b^e=c^f\le n,\qquad a<b,\qquad e\ge 2,\qquad f\ge 3.$$
The goal is to compute \(F(10^{18})\). The challenge is that the same right-hand side value can be a perfect power in more than one way, while the left-hand side behaves very differently for \(e=2\), \(e=3\), and \(e\ge 4\).
The implementation separates the problem into three parts. First it catalogs all perfect powers \(c^f\le n\) with \(f\ge 3\). Then it counts representations \(a^e+b^e=N\) using a special method for squares, another for cubes, and a direct scan for higher exponents.
For every base \(c\ge 2\) and exponent \(f\ge 3\), generate
$$N=c^f\le n.$$
This produces a catalogue of perfect-power descriptions, not merely a set of distinct values. That distinction matters because one numerical value may support several exponents. If a number is both a cube and a fifth power, then a single identity \(a^e+b^e=N\) contributes once for each admissible exponent \(f\).
For each numerical value \(N\), the implementation stores the full set of exponents \(f\) with \(N=c^f\). The largest possible exponent is
$$f_{\max}=\left\lfloor \log_2 n \right\rfloor,$$
because \(2^f\le n\) is the smallest perfect power having exponent \(f\).
Fix a perfect power \(N=c^f\), and write
$$N=\prod p^{\alpha_p}.$$
The classical formula for the number of integer solutions of \(x^2+y^2=N\) is
$$r_2(N)=4\prod_{p\equiv 1 \pmod 4}(\alpha_p+1),$$
provided every prime \(p\equiv 3\pmod 4\) appears with even exponent. If one such prime has odd exponent, then \(r_2(N)=0\).
This count includes signs and order, so it is not yet the desired number of positive pairs with \(a<b\). Two special families must be removed first:
$$\text{axis solutions }(t,0)\text{ or }(0,t),\qquad \text{equal solutions }(t,t).$$
If \(N\) is a square, there are four axis solutions. If \(N=2t^2\), there are four equal solutions. Every remaining nonzero unequal representation occurs in exactly \(8\) signed-and-ordered forms, so the required count is
$$\frac{r_2(N)-\text{axis}-\text{equal}}{8}.$$
Because \(N=c^f\), it is enough to factor \(c\) and multiply every prime exponent by \(f\).
For cubes we use the identity
$$a^3+b^3=(a+b)(a^2-ab+b^2).$$
Set
$$u=a+b,\qquad v=a^2-ab+b^2,\qquad N=uv.$$
Now enumerate divisors \(u\mid N\), set \(v=N/u\), and recover \(a\) and \(b\) from symmetric data. Since
$$u^2-v=3ab,$$
we obtain
$$ab=\frac{u^2-v}{3}.$$
Then \(a\) and \(b\) are roots of
$$t^2-ut+ab=0,$$
so the discriminant
$$\Delta=u^2-4ab$$
must be a perfect square. If \(\Delta=s^2\) and \(u\pm s\) are even, then
$$a=\frac{u-s}{2},\qquad b=\frac{u+s}{2}.$$
Only solutions with \(a>0\) and \(a<b\) are kept. The implementation also skips right-hand-side exponents divisible by \(3\), because then \(c^f\) is itself a cube and \(a^3+b^3=z^3\) would contradict Fermat's Last Theorem for positive integers.
For a fixed exponent \(e\ge 4\), precompute
$$1^e,2^e,\dots,\left\lfloor n^{1/e}\right\rfloor^e.$$
For each \(b\), admissible values of \(a\) satisfy
$$1\le a\le \min\!\left(b-1,\left\lfloor (n-b^e)^{1/e}\right\rfloor\right).$$
Each candidate sum
$$s=a^e+b^e$$
is looked up in the perfect-power catalogue. If \(s=c^f\) for several exponents \(f\), each such exponent contributes except the multiples of \(e\). Indeed, if \(e\mid f\), then
$$s=c^f=\left(c^{f/e}\right)^e,$$
which would produce a nontrivial solution of \(a^e+b^e=z^e\), impossible for \(e\ge 3\).
There is also a parity pruning for even \(e\). If both \(a\) and \(b\) are odd, then
$$a^e+b^e\equiv 1+1\equiv 2 \pmod 4,$$
but a perfect power \(c^f\) with \(f\ge 3\) is either odd or divisible by \(8\), never \(2\bmod 4\). So when \(e\) is even and \(b\) is odd, only even values of \(a\) need to be tested.
The count is over exponent choices as well as numerical values. A single value \(N\) may correspond to several admissible right-hand-side exponents, so a solution \(a^e+b^e=N\) may contribute more than once. This is why the implementation keeps both a list of all perfect-power descriptions and a compact record of which exponents belong to each value.
The checkpoint built into the implementation is
$$F(1000)=7.$$
The seven counted tuples come from exactly four right-hand-side values:
$$125=2^2+11^2=5^2+10^2=5^3,$$
$$243=3^3+6^3=3^5,$$
$$625=7^2+24^2=15^2+20^2=5^4,$$
$$1000=10^2+30^2=18^2+26^2=10^3.$$
That is \(2+1+2+2=7\). The square cases are detected by the two-squares theorem, the cubic case is reconstructed from divisors and a discriminant test, and no exponent \(e\ge 4\) contributes below \(1000\).
The C++, Python, and Java implementations all follow the same counting strategy. They first enumerate all perfect powers \(c^f\le 10^{18}\) with \(f\ge 3\), preserving every individual \((c,f)\) description while also recording, for each value \(N\), the set of exponents that produce it.
Next, the implementation builds a smallest-prime-factor sieve up to the largest base appearing in the catalogue. The \(e=2\) branch uses that sieve to factor bases quickly and then applies the sum-of-two-squares theorem. The \(e=3\) branch enumerates divisors of the perfect power, reconstructs possible pairs \((a,b)\), and caches the cubic count for each numerical value so repeated values are not recomputed.
For \(e\ge 4\), the implementation precomputes the table of \(e\)-th powers, scans the admissible range \(a<b\), applies the parity pruning for even exponents, and consults the perfect-power catalogue for every sum. The C++ implementation parallelizes large outer loops; the Python implementation keeps the same logic in a direct serial form; the Java implementation delegates to the same computational core.
Let
$$M=\sum_{f=3}^{\lfloor \log_2 n\rfloor}\left\lfloor n^{1/f}\right\rfloor.$$
Generating the perfect-power catalogue costs \(O(M)\), dominated by cubes and therefore behaving like \(O(n^{1/3})\). Building the smallest-prime-factor sieve up to the largest base costs \(O(n^{1/3}\log\log n)\) time and \(O(n^{1/3})\) memory.
The \(e=2\) branch is essentially linear in the number of catalogue entries after sieve preprocessing. The \(e=3\) branch depends on divisor enumeration for the perfect powers that survive the \(3\nmid f\) filter, but caching makes repeated values cheap. The dominant direct scan is
$$\sum_{e=4}^{\lfloor \log_2 n\rfloor} O\!\left(n^{2/e}\right),$$
with the largest contribution coming from \(e=4\). In practice, the special handling of \(e=2\) and \(e=3\), parity pruning, perfect-power lookup, and parallel work splitting make the full \(n=10^{18}\) computation feasible.
Sei \(F(n)\) die Anzahl aller Tupel \((a,b,c,e,f)\) positiver ganzer Zahlen mit
$$a^e+b^e=c^f\le n,\qquad a<b,\qquad e\ge 2,\qquad f\ge 3.$$
Gesucht ist also \(F(10^{18})\). Die Schwierigkeit liegt darin, dass derselbe rechte Zahlenwert auf mehrere Arten eine perfekte Potenz sein kann, während die linke Seite für \(e=2\), \(e=3\) und \(e\ge 4\) ganz unterschiedlich behandelt werden muss.
Die Lösung zerlegt die Aufgabe in drei Regime. Zuerst werden alle perfekten Potenzen \(c^f\le n\) mit \(f\ge 3\) katalogisiert. Danach zählt man Darstellungen \(a^e+b^e=N\) mit einem Spezialverfahren für Quadrate, einem zweiten für Kuben und einem direkten Scan für höhere Exponenten.
Für jede Basis \(c\ge 2\) und jeden Exponenten \(f\ge 3\) erzeugen wir
$$N=c^f\le n.$$
Dabei entsteht nicht nur eine Menge verschiedener Werte, sondern ein Katalog von Darstellungen. Das ist wichtig, weil ein Zahlenwert mehrere zulässige Exponenten besitzen kann. Wenn ein Wert zugleich Kubus und fünfte Potenz ist, dann trägt dieselbe Gleichung \(a^e+b^e=N\) für jeden zulässigen Exponenten \(f\) separat bei.
Für jeden Zahlenwert \(N\) speichert die Implementierung daher die gesamte Menge der Exponenten \(f\) mit \(N=c^f\). Der größte mögliche Exponent ist
$$f_{\max}=\left\lfloor \log_2 n \right\rfloor,$$
denn \(2^f\le n\) ist die kleinste perfekte Potenz mit Exponent \(f\).
Fixiere \(N=c^f\) und schreibe
$$N=\prod p^{\alpha_p}.$$
Die klassische Formel für die Anzahl ganzzahliger Lösungen von \(x^2+y^2=N\) lautet
$$r_2(N)=4\prod_{p\equiv 1 \pmod 4}(\alpha_p+1),$$
sofern jede Primzahl \(p\equiv 3\pmod 4\) mit geradem Exponenten vorkommt. Sobald eine solche Primzahl ungeraden Exponenten hat, ist \(r_2(N)=0\).
Diese Zahl enthält Vorzeichen und Reihenfolge. Gesucht sind aber nur positive Paare mit \(a<b\). Deshalb entfernt man zunächst zwei Sonderfälle:
$$\text{Achsenlösungen }(t,0)\text{ oder }(0,t),\qquad \text{gleiche Lösungen }(t,t).$$
Ist \(N\) ein Quadrat, gibt es vier Achsenlösungen. Ist \(N=2t^2\), gibt es vier gleiche Lösungen. Jede verbleibende nichttriviale Darstellung erscheint in genau \(8\) Vorzeichen- und Reihenfolgevarianten, daher ist die gesuchte Anzahl
$$\frac{r_2(N)-\text{Achse}-\text{gleich}}{8}.$$
Weil \(N=c^f\) gilt, genügt es, \(c\) zu faktorisieren und alle Primexponenten mit \(f\) zu multiplizieren.
Für Kuben verwenden wir
$$a^3+b^3=(a+b)(a^2-ab+b^2).$$
Setze
$$u=a+b,\qquad v=a^2-ab+b^2,\qquad N=uv.$$
Nun durchläuft man alle Teiler \(u\mid N\), setzt \(v=N/u\) und rekonstruiert \(a\) und \(b\) aus diesen symmetrischen Daten. Aus
$$u^2-v=3ab$$
folgt
$$ab=\frac{u^2-v}{3}.$$
Damit sind \(a\) und \(b\) die Nullstellen von
$$t^2-ut+ab=0,$$
also muss die Diskriminante
$$\Delta=u^2-4ab$$
ein Quadrat sein. Gilt \(\Delta=s^2\) und sind \(u\pm s\) gerade, dann erhält man
$$a=\frac{u-s}{2},\qquad b=\frac{u+s}{2}.$$
Behalten werden nur Lösungen mit \(a>0\) und \(a<b\). Außerdem überspringt die Implementierung rechte Exponenten, die durch \(3\) teilbar sind, denn dann wäre \(c^f\) selbst ein Kubus und \(a^3+b^3=z^3\) würde dem großen Satz von Fermat für positive ganze Zahlen widersprechen.
Für einen festen Exponenten \(e\ge 4\) werden zuerst die Werte
$$1^e,2^e,\dots,\left\lfloor n^{1/e}\right\rfloor^e$$
vorberechnet. Für jedes \(b\) gilt dann
$$1\le a\le \min\!\left(b-1,\left\lfloor (n-b^e)^{1/e}\right\rfloor\right).$$
Jede Kandidatensumme
$$s=a^e+b^e$$
wird im Katalog perfekter Potenzen nachgeschlagen. Ist \(s=c^f\) für mehrere Exponenten \(f\), dann zählt jeder dieser Exponenten mit Ausnahme der Vielfachen von \(e\). Denn aus \(e\mid f\) würde folgen
$$s=c^f=\left(c^{f/e}\right)^e,$$
also eine nichttriviale Lösung von \(a^e+b^e=z^e\), unmöglich für \(e\ge 3\).
Zusätzlich gibt es eine Paritätskürzung für gerade \(e\). Sind sowohl \(a\) als auch \(b\) ungerade, dann gilt
$$a^e+b^e\equiv 1+1\equiv 2 \pmod 4,$$
während eine perfekte Potenz \(c^f\) mit \(f\ge 3\) entweder ungerade oder durch \(8\) teilbar ist, aber nie \(2\bmod 4\). Deshalb müssen bei geradem \(e\) und ungeradem \(b\) nur gerade Werte von \(a\) geprüft werden.
Gezählt werden nicht nur Zahlenwerte, sondern auch Exponentenwahlen. Ein einzelner Wert \(N\) kann mehrere zulässige rechte Exponenten besitzen, also kann dieselbe Identität \(a^e+b^e=N\) mehr als einmal beitragen. Darum speichert die Implementierung sowohl jede einzelne perfekte-Potenz-Darstellung als auch kompakt die Exponentenmengen pro Zahlenwert.
Die Implementierung benutzt den Kontrollwert
$$F(1000)=7.$$
Die sieben gezählten Tupel stammen genau von vier rechten Zahlenwerten:
$$125=2^2+11^2=5^2+10^2=5^3,$$
$$243=3^3+6^3=3^5,$$
$$625=7^2+24^2=15^2+20^2=5^4,$$
$$1000=10^2+30^2=18^2+26^2=10^3.$$
Das ergibt \(2+1+2+2=7\). Die quadratischen Fälle liefert der Zwei-Quadrate-Satz, der kubische Fall entsteht aus der Teiler- und Diskriminantenrekonstruktion, und unterhalb von \(1000\) gibt es keinen Beitrag mit \(e\ge 4\).
Die Implementierungen in C++, Python und Java folgen derselben Zählstrategie. Zuerst werden alle perfekten Potenzen \(c^f\le 10^{18}\) mit \(f\ge 3\) erzeugt. Dabei bleibt jede einzelne Darstellung \((c,f)\) erhalten, und zusätzlich wird pro Zahlenwert \(N\) gespeichert, welche Exponenten ihn erzeugen.
Anschließend baut die Implementierung ein Sieb der kleinsten Primfaktoren bis zur größten im Katalog vorkommenden Basis auf. Der Zweig für \(e=2\) faktorisiert damit die Basen schnell und wendet dann den Zwei-Quadrate-Satz an. Der Zweig für \(e=3\) enumeriert Teiler der perfekten Potenz, rekonstruiert mögliche Paare \((a,b)\) und puffert die Anzahl kubischer Zerlegungen pro Zahlenwert, damit wiederholte Werte nicht erneut bearbeitet werden.
Für \(e\ge 4\) werden Tabellen der \(e\)-ten Potenzen vorbereitet, der Bereich \(a<b\) abgescannt, die Paritätskürzung für gerade Exponenten angewendet und jede Summe gegen den Katalog perfekter Potenzen geprüft. Die C++-Implementierung parallelisiert große äußere Schleifen; die Python-Implementierung behält dieselbe Logik seriell bei; die Java-Implementierung delegiert an denselben Rechenkern.
Mit
$$M=\sum_{f=3}^{\lfloor \log_2 n\rfloor}\left\lfloor n^{1/f}\right\rfloor$$
kostet die Erzeugung des perfekte-Potenzen-Katalogs \(O(M)\), dominiert von der Kubusschicht und damit effektiv \(O(n^{1/3})\). Das Sieb der kleinsten Primfaktoren bis zur größten Basis benötigt \(O(n^{1/3}\log\log n)\) Zeit und \(O(n^{1/3})\) Speicher.
Der Zweig \(e=2\) ist nach dem Sieb praktisch linear in der Zahl der Katalogeinträge. Der Zweig \(e=3\) hängt von der Teileranzahl der perfekten Potenzen ab, die den Filter \(3\nmid f\) überstehen, aber Zwischenspeicherung macht wiederholte Werte billig. Der dominierende direkte Scan ist
$$\sum_{e=4}^{\lfloor \log_2 n\rfloor} O\!\left(n^{2/e}\right),$$
wobei der größte Beitrag von \(e=4\) kommt. In der Praxis machen die Sonderbehandlung von \(e=2\) und \(e=3\), die Paritätskürzung, der Nachschlagetisch für perfekte Potenzen und die Parallelisierung die volle Rechnung für \(n=10^{18}\) praktikabel.
\(F(n)\),
$$a^e+b^e=c^f\le n,\qquad a<b,\qquad e\ge 2,\qquad f\ge 3$$
koşullarını sağlayan tüm pozitif tamsayı \((a,b,c,e,f)\) beşlilerinin sayısı olsun. Amaç \(F(10^{18})\) değerini bulmaktır. Zorluk, aynı sağ taraf değerinin birden fazla mükemmel üs biçiminde yazılabilmesi ve sol tarafın \(e=2\), \(e=3\) ve \(e\ge 4\) durumlarında farklı teknikler gerektirmesidir.
Çözüm üç parçaya ayrılır. Önce \(f\ge 3\) için tüm \(c^f\le n\) değerleri kataloglanır. Sonra \(a^e+b^e=N\) sayımı, kareler için ayrı, küpler için ayrı, daha büyük üsler için ise doğrudan tarama ile yapılır.
Her \(c\ge 2\) tabanı ve \(f\ge 3\) üssü için
$$N=c^f\le n$$
üretilir. Burada sadece farklı sayıların kümesini tutmak yetmez; her sayı için hangi üslerle yazılabildiği de önemlidir. Çünkü tek bir özdeşlik \(a^e+b^e=N\), eğer \(N\) hem küp hem de beşinci kuvvet ise, her uygun \(f\) için ayrı katkı verir.
Bu nedenle uygulama her sayısal \(N\) değeri için, \(N=c^f\) olacak tüm üslerin kümesini saklar. İlgili en büyük üs
$$f_{\max}=\left\lfloor \log_2 n \right\rfloor$$
olur; çünkü üs \(f\) için mümkün olan en küçük mükemmel üs \(2^f\)'dir.
Sabit bir \(N=c^f\) alalım ve
$$N=\prod p^{\alpha_p}$$
şeklinde asal çarpanlarına ayıralım. \(x^2+y^2=N\) tam sayı çözümlerinin klasik formülü
$$r_2(N)=4\prod_{p\equiv 1 \pmod 4}(\alpha_p+1)$$
şeklindedir; ancak bu ancak \(p\equiv 3\pmod 4\) olan her asalın çift üs ile geldiği durumda geçerlidir. Böyle bir asal tek üs ile görünürse \(r_2(N)=0\) olur.
Bu sayı işaretleri ve sıralamayı da içerir. Oysa bizim istediğimiz yalnızca \(a<b\) koşulunu sağlayan pozitif çiftlerdir. Bu yüzden önce iki özel durumu ayıklamak gerekir:
$$\text{eksen çözümleri }(t,0)\text{ veya }(0,t),\qquad \text{eşit çözümler }(t,t).$$
\(N\) tam kare ise dört eksen çözümü vardır. \(N=2t^2\) ise dört eşit çözüm vardır. Geriye kalan her sıfır olmayan ve eşit olmayan temsil, işaret ve sıra bakımından tam \(8\) kez görünür. Dolayısıyla aranan sayı
$$\frac{r_2(N)-\text{eksen}-\text{eşit}}{8}$$
olur. \(N=c^f\) olduğundan, yalnızca \(c\)'yi çarpanlara ayırıp üsleri \(f\) ile çarpmak yeterlidir.
Küpler için şu özdeşliği kullanırız:
$$a^3+b^3=(a+b)(a^2-ab+b^2).$$
Şimdi
$$u=a+b,\qquad v=a^2-ab+b^2,\qquad N=uv$$
tanımlarını yapalım. Tüm \(u\mid N\) bölenlerini gezip \(v=N/u\) alırız ve buradan \(a,b\) değerlerini geri çıkarırız. Çünkü
$$u^2-v=3ab,$$
dolayısıyla
$$ab=\frac{u^2-v}{3}$$
elde edilir. Böylece \(a\) ve \(b\),
$$t^2-ut+ab=0$$
denklemindeki kökler olur. Demek ki diskriminant
$$\Delta=u^2-4ab$$
tam kare olmalıdır. Eğer \(\Delta=s^2\) ise ve \(u\pm s\) çiftse,
$$a=\frac{u-s}{2},\qquad b=\frac{u+s}{2}$$
elde edilir. Burada sadece \(a>0\) ve \(a<b\) olan çözümler tutulur. Ayrıca uygulama, sağ taraftaki \(3\)'ün katı üsleri atlar; çünkü o durumda \(c^f\) zaten bir küptür ve \(a^3+b^3=z^3\) eşitliği pozitif tamsayılarda Fermat'nın Son Teoremi ile çelişir.
Sabit bir \(e\ge 4\) için önce
$$1^e,2^e,\dots,\left\lfloor n^{1/e}\right\rfloor^e$$
tablosu hazırlanır. Her \(b\) için uygun \(a\) aralığı
$$1\le a\le \min\!\left(b-1,\left\lfloor (n-b^e)^{1/e}\right\rfloor\right)$$
şeklindedir. Sonra
$$s=a^e+b^e$$
toplamı mükemmel üs kataloğunda aranır. Eğer \(s=c^f\) birden fazla üs için mümkünse, \(e\)'nin katı olanlar dışındaki her \(f\) sayılır. Çünkü \(e\mid f\) ise
$$s=c^f=\left(c^{f/e}\right)^e$$
olur ve bu da \(a^e+b^e=z^e\) biçiminde, \(e\ge 3\) için imkansız bir çözüm üretir.
Çift \(e\) için ek bir parite budaması vardır. Hem \(a\) hem \(b\) tek ise
$$a^e+b^e\equiv 1+1\equiv 2 \pmod 4$$
olur. Oysa \(f\ge 3\) olan bir mükemmel üs \(c^f\) ya tektir ya da \(8\)'e bölünür; \(4\) ile bölümünden kalan hiçbir zaman \(2\) olmaz. Bu yüzden \(e\) çift ve \(b\) tekken sadece çift \(a\) değerleri denenir.
Sayım yalnızca sayısal değerlere göre değil, üs seçimlerine göre de yapılır. Tek bir \(N\) değeri sağ tarafta birden fazla uygun üs ile yazılabiliyorsa, \(a^e+b^e=N\) özdeşliği birden fazla kez katkı verebilir. Bu nedenle uygulama hem tüm bireysel mükemmel üs tanımlarını hem de her sayı için hangi üslerin geçerli olduğunu ayrı ayrı saklar.
Uygulamadaki kontrol değeri
$$F(1000)=7$$
şeklindedir. Bu yedi katkı yalnızca dört sağ taraf değerinden gelir:
$$125=2^2+11^2=5^2+10^2=5^3,$$
$$243=3^3+6^3=3^5,$$
$$625=7^2+24^2=15^2+20^2=5^4,$$
$$1000=10^2+30^2=18^2+26^2=10^3.$$
Böylece toplam \(2+1+2+2=7\) olur. Kare durumları iki kare toplamı teoreminden, küp durumu bölen ve diskriminant yönteminden gelir; \(1000\)'in altında \(e\ge 4\) için katkı yoktur.
C++, Python ve Java implementasyonları aynı sayım fikrini izler. Önce \(f\ge 3\) için tüm \(c^f\le 10^{18}\) değerleri üretilir. Böylece hem her ayrı \((c,f)\) tanımı korunur hem de her sayısal \(N\) için hangi üslerin mümkün olduğu kaydedilir.
Sonra katalogda görülen en büyük tabana kadar en küçük asal bölen süzgeci kurulur. \(e=2\) kolu bu süzgeç sayesinde tabanları hızlıca çarpanlara ayırır ve iki kare toplamı teoremini uygular. \(e=3\) kolu mükemmel üssün bölenlerini gezer, olası \((a,b)\) çiftlerini yeniden kurar ve aynı sayısal değer tekrar ortaya çıktığında işi baştan yapmamak için kübik sayımı önbelleğe alır.
\(e\ge 4\) için uygulama \(e\). kuvvetler tablosunu hazırlar, \(a<b\) aralığını tarar, çift üslerde parite budamasını uygular ve her toplamı mükemmel üs kataloğunda sorgular. C++ sürümü büyük dış döngüleri paralel çalıştırır; Python sürümü aynı mantığı seri biçimde uygular; Java sürümü ise aynı hesaplama çekirdeğini çağırır.
Şimdi
$$M=\sum_{f=3}^{\lfloor \log_2 n\rfloor}\left\lfloor n^{1/f}\right\rfloor$$
olsun. Mükemmel üs kataloğunu üretmek \(O(M)\) zaman alır; baskın terim küplerden geldiği için bu davranış pratikte \(O(n^{1/3})\) olur. En büyük tabana kadar en küçük asal bölen süzgeci kurmak \(O(n^{1/3}\log\log n)\) zaman ve \(O(n^{1/3})\) bellek gerektirir.
\(e=2\) kolu, süzgeçten sonra katalog boyutuna göre neredeyse lineerdir. \(e=3\) kolunun maliyeti, \(3\nmid f\) filtresini geçen mükemmel üsler için bölen sayısına bağlıdır; fakat önbellekleme tekrar eden değerleri ucuz hale getirir. Baskın doğrudan tarama
$$\sum_{e=4}^{\lfloor \log_2 n\rfloor} O\!\left(n^{2/e}\right)$$
şeklindedir ve en büyük katkı \(e=4\)'ten gelir. Pratikte \(e=2\) ve \(e=3\) için özel formüller, parite budaması, mükemmel üs tablosu ve paralel iş bölüşümü sayesinde \(n=10^{18}\) hesabı yapılabilir hale gelir.
Sea \(F(n)\) el número de quíntuplas \((a,b,c,e,f)\) de enteros positivos tales que
$$a^e+b^e=c^f\le n,\qquad a<b,\qquad e\ge 2,\qquad f\ge 3.$$
El objetivo es calcular \(F(10^{18})\). La dificultad principal es que un mismo valor del lado derecho puede ser una potencia perfecta de varias maneras, mientras que el lado izquierdo requiere técnicas diferentes para \(e=2\), \(e=3\) y \(e\ge 4\).
La solución separa el problema en tres regímenes. Primero se catalogan todas las potencias perfectas \(c^f\le n\) con \(f\ge 3\). Después se cuentan las representaciones \(a^e+b^e=N\) usando un método especial para cuadrados, otro para cubos y un barrido directo para exponentes mayores.
Para cada base \(c\ge 2\) y cada exponente \(f\ge 3\), generamos
$$N=c^f\le n.$$
No basta con guardar solo los valores distintos. También importa con qué exponentes aparece cada valor. Si un mismo número es a la vez un cubo y una quinta potencia, entonces una identidad \(a^e+b^e=N\) aporta una vez por cada exponente admisible del lado derecho.
Por eso la implementación guarda, para cada valor numérico \(N\), el conjunto completo de exponentes \(f\) tales que \(N=c^f\). El mayor exponente relevante es
$$f_{\max}=\left\lfloor \log_2 n \right\rfloor,$$
porque \(2^f\le n\) es la menor potencia perfecta posible con exponente \(f\).
Fijemos \(N=c^f\) y escribamos
$$N=\prod p^{\alpha_p}.$$
La fórmula clásica para el número de soluciones enteras de \(x^2+y^2=N\) es
$$r_2(N)=4\prod_{p\equiv 1 \pmod 4}(\alpha_p+1),$$
siempre que cada primo \(p\equiv 3\pmod 4\) aparezca con exponente par. Si alguno aparece con exponente impar, entonces \(r_2(N)=0\).
Ese conteo incluye signos y orden. Lo que se necesita aquí son solo pares positivos con \(a<b\). Por eso primero hay que quitar dos familias especiales:
$$\text{soluciones de eje }(t,0)\text{ o }(0,t),\qquad \text{soluciones iguales }(t,t).$$
Si \(N\) es un cuadrado, existen cuatro soluciones de eje. Si \(N=2t^2\), existen cuatro soluciones iguales. Toda representación restante, no nula y con \(a\ne b\), aparece exactamente en \(8\) versiones con signos y orden, de modo que el número deseado es
$$\frac{r_2(N)-\text{eje}-\text{igual}}{8}.$$
Como \(N=c^f\), basta factorizar \(c\) y multiplicar cada exponente primo por \(f\).
Para cubos usamos
$$a^3+b^3=(a+b)(a^2-ab+b^2).$$
Definimos
$$u=a+b,\qquad v=a^2-ab+b^2,\qquad N=uv.$$
Entonces se enumeran los divisores \(u\mid N\), se fija \(v=N/u\) y se reconstruyen \(a\) y \(b\) a partir de esos datos simétricos. Como
$$u^2-v=3ab,$$
se obtiene
$$ab=\frac{u^2-v}{3}.$$
Luego \(a\) y \(b\) son raíces de
$$t^2-ut+ab=0,$$
así que el discriminante
$$\Delta=u^2-4ab$$
debe ser un cuadrado perfecto. Si \(\Delta=s^2\) y \(u\pm s\) son pares, entonces
$$a=\frac{u-s}{2},\qquad b=\frac{u+s}{2}.$$
Solo se conservan las soluciones con \(a>0\) y \(a<b\). Además, la implementación descarta exponentes del lado derecho divisibles por \(3\), porque en ese caso \(c^f\) ya es un cubo y \(a^3+b^3=z^3\) contradice el último teorema de Fermat en enteros positivos.
Para un exponente fijo \(e\ge 4\), primero se precalcula
$$1^e,2^e,\dots,\left\lfloor n^{1/e}\right\rfloor^e.$$
Para cada \(b\), el rango admisible de \(a\) es
$$1\le a\le \min\!\left(b-1,\left\lfloor (n-b^e)^{1/e}\right\rfloor\right).$$
Cada suma candidata
$$s=a^e+b^e$$
se busca en el catálogo de potencias perfectas. Si \(s=c^f\) para varios exponentes \(f\), todos ellos cuentan salvo los múltiplos de \(e\). En efecto, si \(e\mid f\), entonces
$$s=c^f=\left(c^{f/e}\right)^e,$$
lo que produciría una solución no trivial de \(a^e+b^e=z^e\), imposible para \(e\ge 3\).
También hay una poda de paridad cuando \(e\) es par. Si \(a\) y \(b\) son ambos impares, entonces
$$a^e+b^e\equiv 1+1\equiv 2 \pmod 4,$$
mientras que una potencia perfecta \(c^f\) con \(f\ge 3\) es impar o divisible por \(8\), pero nunca congruente con \(2\) módulo \(4\). Por eso, si \(e\) es par y \(b\) es impar, solo hay que probar valores pares de \(a\).
El conteo no depende solo del valor numérico, sino también de la elección del exponente derecho. Un mismo valor \(N\) puede admitir varios exponentes \(f\), así que una identidad \(a^e+b^e=N\) puede aportar más de una vez. Por eso la implementación conserva tanto la lista completa de descripciones de potencias perfectas como el conjunto compacto de exponentes asociados a cada valor.
El punto de control incorporado en la implementación es
$$F(1000)=7.$$
Las siete contribuciones provienen exactamente de cuatro valores del lado derecho:
$$125=2^2+11^2=5^2+10^2=5^3,$$
$$243=3^3+6^3=3^5,$$
$$625=7^2+24^2=15^2+20^2=5^4,$$
$$1000=10^2+30^2=18^2+26^2=10^3.$$
Eso da \(2+1+2+2=7\). Los casos cuadrados salen del teorema de suma de dos cuadrados, el caso cúbico sale de la reconstrucción por divisores y discriminante, y no hay aportes con \(e\ge 4\) por debajo de \(1000\).
Las implementaciones en C++, Python y Java siguen la misma estrategia. Primero enumeran todas las potencias perfectas \(c^f\le 10^{18}\) con \(f\ge 3\). Se conserva cada descripción individual \((c,f)\) y, además, para cada valor \(N\) se registra el conjunto de exponentes que lo producen.
Después, la implementación construye una criba de menor factor primo hasta la base más grande del catálogo. La rama \(e=2\) usa esa criba para factorizar bases rápidamente y aplicar el teorema de suma de dos cuadrados. La rama \(e=3\) enumera divisores de la potencia perfecta, reconstruye posibles pares \((a,b)\) y guarda en caché el número de descomposiciones cúbicas de cada valor numérico para no repetir trabajo.
Para \(e\ge 4\), la implementación precalcula las \(e\)-ésimas potencias, recorre el rango \(a<b\), aplica la poda de paridad para exponentes pares y consulta el catálogo de potencias perfectas en cada suma. La versión en C++ paraleliza los grandes bucles exteriores; la versión en Python mantiene la misma lógica en serie; la versión en Java delega en el mismo núcleo de cálculo.
Sea
$$M=\sum_{f=3}^{\lfloor \log_2 n\rfloor}\left\lfloor n^{1/f}\right\rfloor.$$
Construir el catálogo de potencias perfectas cuesta \(O(M)\), dominado por la capa de cubos y por tanto con comportamiento \(O(n^{1/3})\). La criba de menor factor primo hasta la base máxima cuesta \(O(n^{1/3}\log\log n)\) tiempo y \(O(n^{1/3})\) memoria.
La rama \(e=2\) es esencialmente lineal en el número de entradas del catálogo una vez construida la criba. La rama \(e=3\) depende de la enumeración de divisores para las potencias perfectas que pasan el filtro \(3\nmid f\), pero la caché abarata los valores repetidos. El barrido directo dominante es
$$\sum_{e=4}^{\lfloor \log_2 n\rfloor} O\!\left(n^{2/e}\right),$$
y la contribución mayor proviene de \(e=4\). En la práctica, el tratamiento especial de \(e=2\) y \(e=3\), la poda de paridad, la tabla de búsqueda de potencias perfectas y el reparto paralelo del trabajo hacen viable el caso completo \(n=10^{18}\).
记 \(F(n)\) 为满足下式的所有正整数五元组 \((a,b,c,e,f)\) 的个数：
$$a^e+b^e=c^f\le n,\qquad a<b,\qquad e\ge 2,\qquad f\ge 3.$$
目标是求出 \(F(10^{18})\)。这道题难的地方不在于某一个单独公式，而在于两个结构同时存在：一方面，右边的同一个数值可能对应多个不同的幂指数；另一方面，左边在 \(e=2\)、\(e=3\) 和 \(e\ge 4\) 时又需要完全不同的数学处理方式。
整体思路是先把右边所有可能出现的完全幂 \(c^f\) 全部整理出来，再按左边指数 \(e\) 的不同范围分类计数。平方和分支使用经典数论公式，立方和分支使用因子分解与判别式恢复，更高次幂分支则做受控枚举并配合完全幂查表。
对每个底数 \(c\ge 2\) 和每个指数 \(f\ge 3\)，生成
$$N=c^f\le n.$$
这里不能只保留不同的数值集合，因为题目的计数对象不仅包含数值，也包含右侧指数的选择。同一个数 \(N\) 可能既是立方数，又是五次幂，甚至还是更高次幂；如果某个左侧表达式恰好等于这个 \(N\)，那么每个合法的 \(f\) 都应当分别贡献一次。
因此，实现中对每个数值 \(N\) 都保存“它可以由哪些指数 \(f\) 产生”的完整信息。相关的最大指数是
$$f_{\max}=\left\lfloor \log_2 n \right\rfloor,$$
因为当底数最小取 \(2\) 时，\(2^f\le n\) 给出了指数 \(f\) 是否可能出现的上界。
固定一个完全幂 \(N=c^f\)，写成素因子分解
$$N=\prod p^{\alpha_p}.$$
经典的两平方和公式告诉我们，整数方程 \(x^2+y^2=N\) 的解数满足
$$r_2(N)=4\prod_{p\equiv 1 \pmod 4}(\alpha_p+1),$$
前提是所有满足 \(p\equiv 3\pmod 4\) 的素数在分解中都以偶数次出现。只要有一个这样的素数出现奇数次，就根本不存在表示，亦即 \(r_2(N)=0\)。
但是 \(r_2(N)\) 统计的是“带符号、带顺序”的整数解，而题目真正需要的是正整数且满足 \(a<b\) 的表示数，所以还要做两步修正。首先剔除坐标轴上的解：
$$\text{轴上解 }(t,0)\text{ 和 }(0,t).$$
如果 \(N\) 本身是平方数，就会有四个这样的解。其次剔除相等解：
$$\text{相等解 }(t,t).$$
当且仅当 \(N=2t^2\) 时，会出现这四个解。除去这些特殊情况以后，其余每个非零且不相等的表示都会以 \(8\) 种带符号和交换次序的方式重复出现，因此目标数量就是
$$\frac{r_2(N)-\text{轴上修正}-\text{相等修正}}{8}.$$
由于 \(N=c^f\)，实现时并不直接分解 \(N\)，而是先分解底数 \(c\)，再把得到的每个素数指数统一乘上 \(f\)。
对立方和，关键恒等式是
$$a^3+b^3=(a+b)(a^2-ab+b^2).$$
令
$$u=a+b,\qquad v=a^2-ab+b^2,\qquad N=uv.$$
这样一来，只要枚举 \(N\) 的每个因子 \(u\mid N\)，再令 \(v=N/u\)，理论上就可以从 \((u,v)\) 反推出 \((a,b)\)。因为
$$u^2-v=3ab,$$
所以
$$ab=\frac{u^2-v}{3}.$$
于是 \(a\) 和 \(b\) 就是二次方程
$$t^2-ut+ab=0$$
的两个根。为了得到整数解，判别式
$$\Delta=u^2-4ab$$
必须是完全平方数。若 \(\Delta=s^2\)，并且 \(u-s\) 与 \(u+s\) 都是偶数，就能写出
$$a=\frac{u-s}{2},\qquad b=\frac{u+s}{2}.$$
最后只保留 \(a>0\) 且 \(a<b\) 的情形。实现中还会跳过所有右侧指数满足 \(3\mid f\) 的条目，因为那时 \(c^f\) 本身就是一个立方数，方程就变成 \(a^3+b^3=z^3\)，这在正整数范围内会被费马大定理排除。
固定一个指数 \(e\ge 4\) 后，先预计算
$$1^e,2^e,\dots,\left\lfloor n^{1/e}\right\rfloor^e.$$
对每个 \(b\)，可行的 \(a\) 必须满足
$$1\le a\le \min\!\left(b-1,\left\lfloor (n-b^e)^{1/e}\right\rfloor\right).$$
于是我们检查每个候选和
$$s=a^e+b^e$$
是否出现在右侧完全幂目录里。如果 \(s\) 对应多个指数 \(f\)，那么这些指数原则上都应计数，但要排除所有 \(e\mid f\) 的情况。原因很简单：若 \(e\mid f\)，则
$$s=c^f=\left(c^{f/e}\right)^e,$$
这就会导出一个非平凡的同次方程 \(a^e+b^e=z^e\)，而当 \(e\ge 3\) 时它被费马大定理否定。
这里还有一个非常有效的奇偶剪枝。若 \(e\) 为偶数，且 \(a,b\) 都是奇数，那么
$$a^e+b^e\equiv 1+1\equiv 2 \pmod 4.$$
但一个满足 \(f\ge 3\) 的完全幂 \(c^f\) 要么是奇数，要么至少被 \(8\) 整除，不可能模 \(4\) 余 \(2\)。所以当 \(e\) 为偶数且 \(b\) 为奇数时，只需要枚举偶数 \(a\)。
题目统计的是五元组，而不是单纯统计有多少个数 \(N\) 可被写成两边相等。因此，右边的指数 \(f\) 本身就是答案的一部分。只要同一个数值 \(N\) 对应多个合法的 \(f\)，那么同一个左侧表示 \(a^e+b^e=N\) 就应该按这些不同的指数分别计入。也正因为如此，实现中一方面保存“所有单独的完全幂条目”，另一方面又保存“每个数值对应哪些指数”的紧凑信息。
实现中内置的小规模校验是
$$F(1000)=7.$$
这 \(7\) 个贡献恰好来自下面四个右侧值：
$$125=2^2+11^2=5^2+10^2=5^3,$$
$$243=3^3+6^3=3^5,$$
$$625=7^2+24^2=15^2+20^2=5^4,$$
$$1000=10^2+30^2=18^2+26^2=10^3.$$
因此总数就是 \(2+1+2+2=7\)。其中平方和分支给出 \(125,625,1000\) 的六个解，立方和分支给出 \(243\) 的一个解，而 \(e\ge 4\) 在 \(1000\) 以下没有命中。
C++、Python 和 Java 三个实现遵循同一套计数流程。首先枚举全部 \(c^f\le 10^{18}\) 且 \(f\ge 3\) 的完全幂；既保留每一条单独的 \((c,f)\) 描述，也为每个数值 \(N\) 保存对应的全部指数集合。
随后，实现建立到最大底数为止的最小素因子筛。\(e=2\) 分支借助这个筛快速分解底数，再套用两平方和定理。\(e=3\) 分支对完全幂枚举因子，恢复候选 \((a,b)\)，并把每个数值的立方和计数缓存起来，避免重复计算。
对于 \(e\ge 4\)，实现先生成 \(e\) 次幂表，再扫描满足 \(a<b\) 的范围，对偶数指数应用奇偶剪枝，并在每个候选和上查询完全幂目录。C++ 版本会把较大的外层循环拆给多个工作线程；Python 版本按同样逻辑顺序执行；Java 版本则调用同一套核心计算过程。
记
$$M=\sum_{f=3}^{\lfloor \log_2 n\rfloor}\left\lfloor n^{1/f}\right\rfloor.$$
生成完全幂目录需要 \(O(M)\) 时间，其中主导项来自立方层，所以整体表现相当于 \(O(n^{1/3})\)。建立到最大底数的最小素因子筛需要 \(O(n^{1/3}\log\log n)\) 时间和 \(O(n^{1/3})\) 空间。
\(e=2\) 分支在筛建好以后，基本上与目录条目数线性相关。\(e=3\) 分支的代价取决于通过 \(3\nmid f\) 过滤后那些完全幂的因子个数，但缓存会显著降低重复值的成本。占主导地位的直接枚举部分是
$$\sum_{e=4}^{\lfloor \log_2 n\rfloor} O\!\left(n^{2/e}\right),$$
其中最大贡献来自 \(e=4\)。在实际运行中，\(e=2\) 和 \(e=3\) 的特化处理、偶数指数的奇偶剪枝、完全幂查表以及 C++ 版本的并行分工，共同把 \(n=10^{18}\) 的完整计算控制在可接受范围内。
Пусть \(F(n)\) обозначает число всех пятёрок \((a,b,c,e,f)\) положительных целых чисел, для которых
$$a^e+b^e=c^f\le n,\qquad a<b,\qquad e\ge 2,\qquad f\ge 3.$$
Нужно вычислить \(F(10^{18})\). Основная трудность состоит в том, что один и тот же числовой правый член может быть совершенной степенью несколькими способами, а левая часть требует разных методов при \(e=2\), \(e=3\) и \(e\ge 4\).
Решение делит задачу на три режима. Сначала каталогизируются все совершенные степени \(c^f\le n\) при \(f\ge 3\). Затем представления вида \(a^e+b^e=N\) считаются отдельно для квадратов, отдельно для кубов и отдельно для больших показателей.
Для каждого основания \(c\ge 2\) и каждого показателя \(f\ge 3\) строится
$$N=c^f\le n.$$
Недостаточно хранить только множество различных значений \(N\). В ответе участвует и выбор показателя \(f\), поэтому важно знать, какими именно степенями является каждый числовой правый член. Один и тот же \(N\) может быть, например, и кубом, и пятой степенью, и тогда одно равенство \(a^e+b^e=N\) должно учитываться по одному разу для каждого допустимого \(f\).
Именно поэтому для каждого значения \(N\) реализация хранит полный набор показателей \(f\), для которых \(N=c^f\). Максимально возможный показатель равен
$$f_{\max}=\left\lfloor \log_2 n \right\rfloor,$$
поскольку \(2^f\le n\) задаёт нижнюю границу для появления степени с показателем \(f\).
Зафиксируем совершенную степень \(N=c^f\) и запишем её как
$$N=\prod p^{\alpha_p}.$$
Классическая формула для числа целочисленных решений уравнения \(x^2+y^2=N\) имеет вид
$$r_2(N)=4\prod_{p\equiv 1 \pmod 4}(\alpha_p+1),$$
если каждый простой \(p\equiv 3\pmod 4\) входит с чётным показателем. Если хотя бы один такой простой имеет нечётный показатель, то \(r_2(N)=0\).
Однако эта величина считает решения с учётом порядка и знаков. В задаче нужны только положительные пары с \(a<b\), поэтому сначала вычитаются два специальных семейства:
$$\text{осевые решения }(t,0)\text{ и }(0,t),\qquad \text{равные решения }(t,t).$$
Если \(N\) является квадратом, существует четыре осевых решения. Если \(N=2t^2\), существует четыре равных решения. После удаления этих исключений каждое оставшееся ненулевое и неравное представление возникает ровно в \(8\) вариантах по знакам и порядку, поэтому нужное число равно
$$\frac{r_2(N)-\text{ось}-\text{равенство}}{8}.$$
Так как \(N=c^f\), на практике достаточно один раз разложить основание \(c\) и умножить все показатели простых на \(f\).
Для кубов используется тождество
$$a^3+b^3=(a+b)(a^2-ab+b^2).$$
Положим
$$u=a+b,\qquad v=a^2-ab+b^2,\qquad N=uv.$$
Затем перечислим все делители \(u\mid N\), положим \(v=N/u\) и восстановим \(a\) и \(b\) по симметрическим данным. Из равенства
$$u^2-v=3ab$$
получаем
$$ab=\frac{u^2-v}{3}.$$
Значит, \(a\) и \(b\) являются корнями квадратного уравнения
$$t^2-ut+ab=0,$$
поэтому дискриминант
$$\Delta=u^2-4ab$$
должен быть полным квадратом. Если \(\Delta=s^2\) и числа \(u-s\) и \(u+s\) чётные, то
$$a=\frac{u-s}{2},\qquad b=\frac{u+s}{2}.$$
Оставляются только решения с \(a>0\) и \(a<b\). Кроме того, реализация пропускает все правые показатели, кратные \(3\), поскольку тогда \(c^f\) само является кубом, а равенство \(a^3+b^3=z^3\) для положительных целых исключается великой теоремой Ферма.
Для фиксированного показателя \(e\ge 4\) сначала предвычисляются значения
$$1^e,2^e,\dots,\left\lfloor n^{1/e}\right\rfloor^e.$$
Для каждого \(b\) допустимый диапазон \(a\) таков:
$$1\le a\le \min\!\left(b-1,\left\lfloor (n-b^e)^{1/e}\right\rfloor\right).$$
Каждая кандидатная сумма
$$s=a^e+b^e$$
ищется в каталоге совершенных степеней. Если число \(s\) совпадает с \(c^f\) для нескольких показателей \(f\), то учитываются все такие показатели, кроме кратных \(e\). Действительно, при \(e\mid f\) имеем
$$s=c^f=\left(c^{f/e}\right)^e,$$
а это означало бы нетривиальное решение уравнения \(a^e+b^e=z^e\), невозможное при \(e\ge 3\).
Есть и полезное сокращение по чётности. Если \(e\) чётно и оба числа \(a\) и \(b\) нечётные, то
$$a^e+b^e\equiv 1+1\equiv 2 \pmod 4.$$
Но совершенная степень \(c^f\) при \(f\ge 3\) либо нечётна, либо делится на \(8\), и никогда не даёт остаток \(2\) по модулю \(4\). Поэтому при чётном \(e\) и нечётном \(b\) достаточно проверять только чётные значения \(a\).
Ответ считает не только числовое значение справа, но и сам показатель \(f\). Поэтому один и тот же \(N\), если он допускает несколько допустимых показателей, может давать несколько вкладов для одного и того же левого представления \(a^e+b^e=N\). По этой причине реализация хранит одновременно и полный список всех описаний совершенных степеней, и компактную информацию о том, какие показатели относятся к каждому значению.
Во встроенной проверке используется значение
$$F(1000)=7.$$
Все семь вкладов приходят ровно от четырёх правых частей:
$$125=2^2+11^2=5^2+10^2=5^3,$$
$$243=3^3+6^3=3^5,$$
$$625=7^2+24^2=15^2+20^2=5^4,$$
$$1000=10^2+30^2=18^2+26^2=10^3.$$
Итого получается \(2+1+2+2=7\). Квадратные случаи даёт теорема о сумме двух квадратов, кубический случай получается из перебора делителей и проверки дискриминанта, а при \(e\ge 4\) ниже \(1000\) совпадений нет.
Реализации на C++, Python и Java следуют одной и той же схеме. Сначала они перечисляют все совершенные степени \(c^f\le 10^{18}\) при \(f\ge 3\). При этом сохраняется каждая отдельная пара \((c,f)\), а также для каждого значения \(N\) запоминается множество показателей, которыми это значение достигается.
Затем строится таблица наименьших простых делителей до максимального основания из каталога. Ветка \(e=2\) использует эту таблицу для быстрого разложения оснований и применяет теорему о сумме двух квадратов. Ветка \(e=3\) перечисляет делители совершенной степени, восстанавливает кандидаты \((a,b)\) и кеширует число кубических разложений для каждого числового значения, чтобы не пересчитывать повторы.
Для \(e\ge 4\) реализация заранее строит таблицу \(e\)-х степеней, сканирует область \(a<b\), применяет сокращение по чётности для чётных показателей и для каждой суммы делает запрос в каталоге совершенных степеней. В версии на C++ крупные внешние циклы распараллеливаются; версия на Python выполняет ту же логику последовательно; версия на Java обращается к тому же вычислительному ядру.
Пусть
$$M=\sum_{f=3}^{\lfloor \log_2 n\rfloor}\left\lfloor n^{1/f}\right\rfloor.$$
Построение каталога совершенных степеней занимает \(O(M)\) времени и определяется главным образом слоем кубов, то есть ведёт себя как \(O(n^{1/3})\). Построение таблицы наименьших простых делителей до максимального основания требует \(O(n^{1/3}\log\log n)\) времени и \(O(n^{1/3})\) памяти.
Ветка \(e=2\) после предварительного просеивания работает почти линейно по числу элементов каталога. Стоимость ветки \(e=3\) зависит от числа делителей у тех совершенных степеней, которые проходят фильтр \(3\nmid f\), но кеширование сильно снижает цену повторов. Доминирующий прямой перебор имеет вид
$$\sum_{e=4}^{\lfloor \log_2 n\rfloor} O\!\left(n^{2/e}\right),$$
и наибольший вклад даёт \(e=4\). На практике специальные формулы для \(e=2\) и \(e=3\), сокращение по чётности, быстрый поиск по каталогу совершенных степеней и распараллеливание делают вычисление для \(n=10^{18}\) выполнимым.
لنرمز بـ \(F(n)\) إلى عدد الخماسيات \((a,b,c,e,f)\) من الأعداد الصحيحة الموجبة التي تحقق
$$a^e+b^e=c^f\le n,\qquad a<b,\qquad e\ge 2,\qquad f\ge 3.$$
المطلوب هو حساب \(F(10^{18})\). تكمن الصعوبة في أن القيمة نفسها في الطرف الأيمن قد تكون قوة تامة بأكثر من أس واحد، وفي المقابل فإن الطرف الأيسر يحتاج إلى معالجة مختلفة تمامًا عندما يكون \(e=2\) أو \(e=3\) أو \(e\ge 4\).
تقسم الفكرة الحل إلى ثلاثة أجزاء. أولًا نحصر جميع القوى التامة \(c^f\le n\) مع \(f\ge 3\). بعد ذلك نعد تمثيلات \(a^e+b^e=N\) باستخدام نظرية مجموع مربعين عندما \(e=2\)، وطريقة تحليل مجموع مكعبين عندما \(e=3\)، ثم مسح مباشر مضبوط عندما \(e\ge 4\).
لكل أساس \(c\ge 2\) ولكل أس \(f\ge 3\) نولد
$$N=c^f\le n.$$
لا يكفي حفظ مجموعة القيم المختلفة فقط، لأن العد هنا لا يعتمد على القيمة العددية وحدها بل على اختيار الأس \(f\) أيضًا. فقد تكون قيمة واحدة في الوقت نفسه مكعبًا وقوة خامسة، وعندئذ فإن هوية واحدة من الشكل \(a^e+b^e=N\) ينبغي أن تحسب مرة لكل أس مسموح به.
لهذا السبب تحفظ الشيفرة، لكل قيمة عددية \(N\)، مجموعة الأسس \(f\) التي تحقق \(N=c^f\). أما أكبر أس ممكن فهو
$$f_{\max}=\left\lfloor \log_2 n \right\rfloor,$$
لأن \(2^f\le n\) هو أصغر شكل ممكن لقوة تامة ذات الأس \(f\).
نثبت قيمة \(N=c^f\) ونكتب تحليلها الأولي على الصورة
$$N=\prod p^{\alpha_p}.$$
الصيغة الكلاسيكية لعدد حلول المعادلة الصحيحة \(x^2+y^2=N\) هي
$$r_2(N)=4\prod_{p\equiv 1 \pmod 4}(\alpha_p+1),$$
وذلك بشرط أن يظهر كل عدد أولي \(p\equiv 3\pmod 4\) بأس زوجي. فإذا ظهر أحد هذه الأعداد بأس فردي فليس هناك أي تمثيل، أي إن \(r_2(N)=0\).
لكن \(r_2(N)\) يحسب الحلول مع ترتيب الحدود ومع الإشارات. أما هنا فنريد فقط الأزواج الموجبة التي تحقق \(a<b\). لذلك يجب أولًا حذف نوعين خاصين من الحلول: حلول المحور \((t,0)\) و\((0,t)\)، ثم الحلول المتساوية \((t,t)\).
إذا كانت \(N\) مربعًا كاملًا فهناك أربع حلول من النوع الأول. وإذا كانت \(N=2t^2\) فهناك أربع حلول من النوع الثاني. بعد حذف هذه الحالات، يظهر كل تمثيل غير صفري وغير متساوٍ في \(8\) صور مختلفة بسبب الترتيب والإشارة، ومن ثم يكون العدد المطلوب
$$\frac{r_2(N)-A-E}{8},$$
حيث يرمز \(A\) إلى تصحيح حلول المحور، ويرمز \(E\) إلى تصحيح الحلول المتساوية.
وبما أن \(N=c^f\)، فيكفي عمليًا تحليل \(c\) ثم ضرب كل أس أولي في \(f\).
بالنسبة إلى المكعبات نستخدم الهوية
$$a^3+b^3=(a+b)(a^2-ab+b^2).$$
لنضع
$$u=a+b,\qquad v=a^2-ab+b^2,\qquad N=uv.$$
الآن نعدد القواسم \(u\mid N\)، ثم نأخذ \(v=N/u\)، وبعد ذلك نستعيد \(a\) و\(b\) من هذه البيانات المتماثلة. فمن العلاقة
$$u^2-v=3ab$$
نحصل على
$$ab=\frac{u^2-v}{3}.$$
وعندئذ يكون \(a\) و\(b\) جذري المعادلة التربيعية
$$t^2-ut+ab=0,$$
ولذلك يجب أن يكون المميز
$$\Delta=u^2-4ab$$
مربعًا كاملًا. فإذا كان \(\Delta=s^2\) وكان \(u-s\) و\(u+s\) زوجيين، نحصل على
$$a=\frac{u-s}{2},\qquad b=\frac{u+s}{2}.$$
ثم نحتفظ فقط بالحلول التي تحقق \(a>0\) و\(a<b\). كذلك تتجاهل الشيفرة كل أس يمين يحقق \(3\mid f\)، لأن \(c^f\) عندئذ يكون مكعبًا بحد ذاته، فتتحول المعادلة إلى \(a^3+b^3=z^3\)، وهو ما يمنعه مبرهن فيرما الأخير في الأعداد الصحيحة الموجبة.
لأس ثابت \(e\ge 4\) نحسب مسبقًا
$$1^e,2^e,\dots,\left\lfloor n^{1/e}\right\rfloor^e.$$
وبالنسبة إلى كل \(b\)، فإن مجال \(a\) المسموح به هو
$$1\le a\le \min\!\left(b-1,\left\lfloor (n-b^e)^{1/e}\right\rfloor\right).$$
بعد ذلك نفحص كل مجموع مرشح
$$s=a^e+b^e$$
داخل فهرس القوى التامة. إذا كانت القيمة \(s\) مساوية لـ \(c^f\) لعدة أسس \(f\)، فإن جميع هذه الأسس تعد ما عدا المضاعفات لـ \(e\). والسبب هو أنه إذا كان \(e\mid f\)، فإن
$$s=c^f=\left(c^{f/e}\right)^e,$$
وبهذا نحصل على حل غير بدهي للمعادلة \(a^e+b^e=z^e\)، وهذا مستحيل عندما \(e\ge 3\).
هناك أيضًا تقليم بسيط لكنه فعال في حالة الأس الزوجي. إذا كان \(e\) زوجيًا وكان كل من \(a\) و\(b\) فرديًا، فسنحصل على
$$a^e+b^e\equiv 1+1\equiv 2 \pmod 4.$$
لكن القوة التامة \(c^f\) مع \(f\ge 3\) تكون إما فردية أو قابلة للقسمة على \(8\)، ولا يمكن أن تعطي باقيًا يساوي \(2\) modulo \(4\). لذلك عندما يكون \(e\) زوجيًا و\(b\) فرديًا يكفي اختبار القيم الزوجية لـ \(a\) فقط.
العد هنا لا يمر على القيم العددية وحدها، بل على اختيارات الأس أيضًا. فإذا كانت القيمة نفسها \(N\) تقبل أكثر من أس يمين صالح، فإن التمثيل الواحد \(a^e+b^e=N\) قد يسهم أكثر من مرة. ولهذا تحتفظ الشيفرة في الوقت نفسه بقائمة جميع أوصاف القوى التامة، وبمعلومة مضغوطة عن الأسس المرتبطة بكل قيمة.
قيمة الفحص الصغيرة المضمنة في التنفيذ هي
$$F(1000)=7.$$
وتأتي هذه المساهمات السبع من أربع قيم فقط في الطرف الأيمن:
$$125=2^2+11^2=5^2+10^2=5^3,$$
$$243=3^3+6^3=3^5,$$
$$625=7^2+24^2=15^2+20^2=5^4,$$
$$1000=10^2+30^2=18^2+26^2=10^3.$$
إذن المجموع هو \(2+1+2+2=7\). حالات المربعات تأتي من مبرهنة مجموع مربعين، والحالة التكعيبية تأتي من استرجاع الحل من القواسم والمميز، ولا يظهر أي إسهام من \(e\ge 4\) تحت \(1000\).
تنفذ نسخ C++ وPython وJava الفكرة الحسابية نفسها. تبدأ أولًا بتوليد جميع القوى التامة \(c^f\le 10^{18}\) مع \(f\ge 3\)، مع الاحتفاظ بكل وصف منفرد \((c,f)\)، وفي الوقت نفسه تخزن لكل قيمة \(N\) مجموعة الأسس التي تنتجها.
بعد ذلك تبني الشيفرة غربالًا لأصغر عامل أولي حتى أكبر أساس ظهر في الفهرس. يستخدم فرع \(e=2\) هذا الغربال لتحليل الأساسات بسرعة ثم يطبق مبرهنة مجموع مربعين. أما فرع \(e=3\) فيعدد قواسم القوة التامة، ويعيد بناء الأزواج المحتملة \((a,b)\)، ويخزن عدد تمثيلات مجموع المكعبين لكل قيمة عددية حتى لا يعيد الحساب عند التكرار.
وعندما \(e\ge 4\)، تحسب الشيفرة جدول القوى \(e\)-ية مسبقًا، ثم تمسح المجال \(a<b\)، وتطبق تقليم الفردية والزوجية عند الأسس الزوجية، ثم تستشير فهرس القوى التامة لكل مجموع. نسخة C++ توزع الحلقات الخارجية الكبيرة على عدة عمال؛ نسخة Python تنفذ المنطق نفسه بشكل تسلسلي؛ ونسخة Java تفوض إلى النواة الحسابية نفسها.
إذا كتبنا
$$M=\sum_{f=3}^{\lfloor \log_2 n\rfloor}\left\lfloor n^{1/f}\right\rfloor,$$
فإن بناء فهرس القوى التامة يكلف \(O(M)\) زمنًا، ويهيمن عليه مستوى المكعبات، لذلك يكون سلوكه العام من رتبة \(O(n^{1/3})\). أما غربال أصغر عامل أولي حتى أكبر أساس فيحتاج إلى \(O(n^{1/3}\log\log n)\) زمنًا و\(O(n^{1/3})\) ذاكرة.
فرع \(e=2\) يصبح شبه خطي في عدد عناصر الفهرس بعد بناء الغربال. فرع \(e=3\) تعتمد كلفته على تعداد القواسم للقوى التامة التي تمر عبر المرشح \(3\nmid f\)، لكن التخزين المؤقت يجعل القيم المتكررة رخيصة. أما المسح المباشر المسيطر فهو
$$\sum_{e=4}^{\lfloor \log_2 n\rfloor} O\!\left(n^{2/e}\right),$$
وأكبر مساهمة فيه تأتي من \(e=4\). عمليًا، فإن المعالجة الخاصة للحالتين \(e=2\) و\(e=3\)، مع تقليم الزوجية، وجدول البحث عن القوى التامة، وتقسيم العمل على التوازي، تجعل الحساب الكامل عند \(n=10^{18}\) ممكنًا.