For fixed integers \(n>1\) and \(e>1\), a mirror power sequence is defined by
$$a_{i+1}=\min(a_i^e,\,n-a_i^e),\qquad a_i>1.$$
For each \(n\), let \(C(n)\) be the number of infinite sequences obtained by allowing every exponent \(e>1\). The target function is
$$D(N)=\sum_{n=2}^{N} C(n).$$
The key point is that different admissible starting values count as different sequences, even when they eventually fall into the same cycle.
The implementation does not simulate sequences term by term. Instead, it classifies every infinite sequence by a smallest cycle value, an exponent \(e\), and a cycle length \(L\).
All terms satisfy \(2\le a_i\le n-2\), so an infinite sequence must eventually become periodic. Take the periodic part and let \(a\) be its smallest value.
From that smallest value, the power branch must be chosen repeatedly until the cycle closes; otherwise the sequence would immediately drop below \(a\), contradicting minimality. Therefore the periodic core has the shape
$$a \to a^e \to a^{e^2} \to \cdots \to a^{e^{L-1}} \to a,$$
for some integer \(L\ge 1\). The final return to \(a\) happens through the mirror branch, so
$$n-a^{e^L}=a,$$
hence every infinite mirror power sequence is governed by
$$\boxed{n=a+a^{e^L}},\qquad a>1,\ e>1,\ L\ge 1.$$
Conversely, once this identity holds, the displayed cycle is valid, so the characterization is exact.
Write
$$p=e^L.$$
For a fixed combined exponent \(p\), define
$$B_p(N)=\max\{a\ge 1:\ a+a^p\le N\}.$$
Then every admissible base for that \(p\) lies in
$$2\le a\le B_p(N).$$
The smallest possible base is \(a=2\), so we must have
$$2+2^p\le N.$$
Therefore only
$$2\le p\le P:=\left\lfloor \log_2(N-2)\right\rfloor$$
can contribute. This is why the implementations only need a very short exponent table even when \(N=10^{18}\).
For a fixed choice of \(a\), \(e\), and \(L\), the cycle itself contributes \(L\) different starts:
$$a,\ a^e,\ a^{e^2},\ \dots,\ a^{e^{L-1}}.$$
There can be more starts before the cycle begins. If \(a=b^e\), then starting from \(b\) reaches \(a\) in one step. If \(a=c^{e^2}\), then starting from \(c\) or \(c^e\) also eventually reaches the same cycle, and so on.
Define \(\rho_e(a)\) as the number of values in the integer \(e\)-root chain ending at \(a\). Equivalently, \(\rho_e(a)\) is \(1\) plus the number of times we can repeatedly take an exact integer \(e\)-th root while staying above \(1\).
Then one fixed triple \((a,e,L)\) contributes
$$\rho_e(a)+(L-1)$$
distinct sequences: \(\rho_e(a)\) starts feeding into the first cycle node \(a\), and the remaining \(L-1\) starts are the other points on the cycle.
If \(a\) is not a perfect \(e\)-th power, then \(\rho_e(a)=1\), so the contribution is exactly \(L\). If \(a=16\) and \(e=2\), then the root chain is \(2\to 4\to 16\), so \(\rho_2(16)=3\).
For a fixed exponent \(e\), define
$$S_e(A)=\sum_{a=2}^{A}\rho_e(a).$$
The quantity \(\rho_e(a)\) counts whether \(a\) is an \(e\)-th power, an \(e^2\)-th power, an \(e^3\)-th power, and so on. So we can sum by root depth instead of by base:
$$S_e(A)=(A-1)+\left(\left\lfloor A^{1/e}\right\rfloor-1\right)+\left(\left\lfloor A^{1/e^2}\right\rfloor-1\right)+\left(\left\lfloor A^{1/e^3}\right\rfloor-1\right)+\cdots.$$
The series stops as soon as \(\lfloor A^{1/e^k}\rfloor<2\). This identity is exactly what the implementations evaluate with repeated integer-root computations.
The case \(L=1\) means \(p=e\). For that layer, the total contribution is simply
$$\sum_{p=2}^{P} S_p\bigl(B_p(N)\bigr).$$
For \(L\ge 2\), each pair \((e,L)\) with \(e^L\le P\) contributes
$$\sum_{a=2}^{B_{e^L}(N)} \bigl(\rho_e(a)+(L-1)\bigr)=(L-1)\bigl(B_{e^L}(N)-1\bigr)+S_e\bigl(B_{e^L}(N)\bigr).$$
Hence
$$\boxed{D(N)=\sum_{p=2}^{P} S_p\bigl(B_p(N)\bigr)+\sum_{e=2}^{P}\ \sum_{\substack{L\ge 2\\ e^L\le P}}\left((L-1)\bigl(B_{e^L}(N)-1\bigr)+S_e\bigl(B_{e^L}(N)\bigr)\right).}$$
This is the counting formula implemented in all three language versions.
Here
$$P=\left\lfloor \log_2(98)\right\rfloor=6.$$
The base bounds are
$$B_2=9,\quad B_3=4,\quad B_4=3,\quad B_5=2,\quad B_6=2.$$
Now compute the \(L=1\) layer:
$$S_2(9)=8+2=10,$$
because among \(2,\dots,9\), the extra square roots come from \(4\) and \(9\). Also
$$S_3(4)=3,\qquad S_4(3)=2,\qquad S_5(2)=1,\qquad S_6(2)=1.$$
So the subtotal for \(L=1\) is
$$10+3+2+1+1=17.$$
For \(L\ge 2\), the only possibility is \(e=2\), \(L=2\), because \(2^2=4\le 6\) but \(2^3=8>6\). Its contribution is
$$ (2-1)(B_4-1)+S_2(B_4)=1\cdot 2+S_2(3)=2+2=4.$$
Therefore
$$D(100)=17+4=21,$$
which matches the implementation checkpoint.
The C++, Python, and Java implementations follow the same plan. First they compute \(P=\lfloor\log_2(N-2)\rfloor\). Then, for every \(2\le p\le P\), they find \(B_p(N)\) with a monotone binary search on \(a\), using overflow-safe power comparisons to test whether \(a+a^p\le N\).
Next they evaluate the root-chain sum \(S_e(A)\) by repeatedly taking integer \(e\)-th, \(e^2\)-th, \(e^3\)-th roots, again via binary search. The \(L=1\) contribution is added first. After that, they enumerate every \(e\) and every power \(e^L\) with \(L\ge 2\), and add the term
$$ (L-1)\bigl(B_{e^L}(N)-1\bigr)+S_e\bigl(B_{e^L}(N)\bigr). $$
No explicit sequence simulation is needed anywhere; the entire computation is reduced to safe integer arithmetic, binary search, and short exponent loops.
Let \(P=\lfloor\log_2(N-2)\rfloor\). There are only \(O(P)\) relevant combined exponents, and only \(O(P)\) pairs \((e,L)\) with \(e^L\le P\). Each boundary search or integer-root search is a binary search over \(a\), and each midpoint test uses a bounded-length power computation of size at most \(P\). A safe upper bound is therefore \(O(P^3\log N)\) time, while memory usage is \(O(P)\). For the actual target \(N=10^{18}\), one has \(P\le 59\), so the method is easily fast enough.
Für feste ganze Zahlen \(n>1\) und \(e>1\) ist eine Mirror-Power-Sequenz durch
$$a_{i+1}=\min(a_i^e,\,n-a_i^e),\qquad a_i>1$$
definiert. Für jedes \(n\) bezeichne \(C(n)\) die Anzahl aller unendlichen Folgen, wenn man über sämtliche Exponenten \(e>1\) summiert. Gesucht ist
$$D(N)=\sum_{n=2}^{N} C(n).$$
Wichtig ist: Verschiedene zulässige Startwerte zählen als verschiedene Folgen, auch wenn sie später in denselben Zyklus laufen.
Die Implementierung simuliert die Rekursion nicht direkt. Stattdessen klassifiziert sie jede unendliche Folge über einen kleinsten Zykluswert, einen Exponenten \(e\) und eine Zykluslänge \(L\).
Alle Terme liegen zwischen \(2\) und \(n-2\). Deshalb muss eine unendliche Folge irgendwann periodisch werden. Sei \(a\) der kleinste Wert im periodischen Teil.
Von diesem kleinsten Wert aus muss mehrfach der Potenz-Zweig gewählt werden; sonst fiele die Folge sofort unter \(a\), was der Minimalität widerspräche. Der periodische Kern hat also die Form
$$a \to a^e \to a^{e^2} \to \cdots \to a^{e^{L-1}} \to a$$
mit einem \(L\ge 1\). Der letzte Rücksprung nach \(a\) benutzt den Spiegel-Zweig und erfüllt
$$n-a^{e^L}=a.$$
Damit gilt für jede unendliche Mirror-Power-Sequenz
$$\boxed{n=a+a^{e^L}},\qquad a>1,\ e>1,\ L\ge 1.$$
Umgekehrt erzeugt genau diese Gleichung den angegebenen Zyklus, also ist die Charakterisierung vollständig.
Setze
$$p=e^L.$$
Für einen festen kombinierten Exponenten \(p\) definieren wir
$$B_p(N)=\max\{a\ge 1:\ a+a^p\le N\}.$$
Dann liegen alle zulässigen Basen für dieses \(p\) im Bereich
$$2\le a\le B_p(N).$$
Die kleinste mögliche Basis ist \(2\). Also muss
$$2+2^p\le N$$
gelten. Folglich können nur
$$2\le p\le P:=\left\lfloor \log_2(N-2)\right\rfloor$$
überhaupt beitragen. Genau deshalb genügt selbst für \(N=10^{18}\) eine sehr kurze Exponentenliste.
Für feste Werte \(a\), \(e\) und \(L\) liefert der Zyklus selbst bereits \(L\) verschiedene Starts:
$$a,\ a^e,\ a^{e^2},\ \dots,\ a^{e^{L-1}}.$$
Es kann aber zusätzliche Starts vor dem Zyklus geben. Ist \(a=b^e\), dann erreicht ein Start bei \(b\) den Wert \(a\) nach einem Schritt. Ist \(a=c^{e^2}\), dann führen auch Starts bei \(c\) oder \(c^e\) in denselben Zyklus.
Sei \(\rho_e(a)\) die Anzahl der Werte in der ganzzahligen \(e\)-Wurzelkette, die bei \(a\) endet. Anders gesagt: \(\rho_e(a)\) ist \(1\) plus die Anzahl exakter ganzzahliger \(e\)-ter Wurzeln, die man wiederholt ziehen kann, ohne \(\le 1\) zu werden.
Dann trägt ein festes Tripel \((a,e,L)\)
$$\rho_e(a)+(L-1)$$
verschiedene Folgen bei: \(\rho_e(a)\) Starts, die in den ersten Zykluswert \(a\) hineinlaufen, und \(L-1\) weitere Starts an den übrigen Zykluspunkten.
Ist \(a\) keine perfekte \(e\)-te Potenz, so ist \(\rho_e(a)=1\) und der Beitrag ist genau \(L\). Bei \(a=16\) und \(e=2\) lautet die Wurzelkette \(2\to 4\to 16\), also \(\rho_2(16)=3\).
Für einen festen Exponenten \(e\) definieren wir
$$S_e(A)=\sum_{a=2}^{A}\rho_e(a).$$
Die Größe \(\rho_e(a)\) prüft, ob \(a\) eine \(e\)-te, \(e^2\)-te, \(e^3\)-te Potenz usw. ist. Daher kann man nach Wurzeltiefe summieren:
$$S_e(A)=(A-1)+\left(\left\lfloor A^{1/e}\right\rfloor-1\right)+\left(\left\lfloor A^{1/e^2}\right\rfloor-1\right)+\left(\left\lfloor A^{1/e^3}\right\rfloor-1\right)+\cdots.$$
Die Reihe endet, sobald \(\lfloor A^{1/e^k}\rfloor<2\) wird. Genau diese Identität werten die Implementierungen durch wiederholte ganzzahlige Wurzelsuchen aus.
Der Fall \(L=1\) bedeutet \(p=e\). Seine Gesamtzahl ist
$$\sum_{p=2}^{P} S_p\bigl(B_p(N)\bigr).$$
Für \(L\ge 2\) trägt jedes Paar \((e,L)\) mit \(e^L\le P\) bei:
$$\sum_{a=2}^{B_{e^L}(N)} \bigl(\rho_e(a)+(L-1)\bigr)=(L-1)\bigl(B_{e^L}(N)-1\bigr)+S_e\bigl(B_{e^L}(N)\bigr).$$
Also gilt insgesamt
$$\boxed{D(N)=\sum_{p=2}^{P} S_p\bigl(B_p(N)\bigr)+\sum_{e=2}^{P}\ \sum_{\substack{L\ge 2\\ e^L\le P}}\left((L-1)\bigl(B_{e^L}(N)-1\bigr)+S_e\bigl(B_{e^L}(N)\bigr)\right).}$$
Genau diese Zählformel steckt in allen drei Implementierungen.
Hier ist
$$P=\left\lfloor \log_2(98)\right\rfloor=6.$$
Die Basisschranken lauten
$$B_2=9,\quad B_3=4,\quad B_4=3,\quad B_5=2,\quad B_6=2.$$
Für die Ebene \(L=1\) erhält man
$$S_2(9)=8+2=10,$$
weil unter \(2,\dots,9\) die zusätzlichen Quadratwurzel-Beiträge von \(4\) und \(9\) kommen. Außerdem
$$S_3(4)=3,\qquad S_4(3)=2,\qquad S_5(2)=1,\qquad S_6(2)=1.$$
Damit ergibt sich als Zwischensumme
$$10+3+2+1+1=17.$$
Für \(L\ge 2\) gibt es nur \(e=2\), \(L=2\), denn \(2^2=4\le 6\), aber \(2^3=8>6\). Der Beitrag ist
$$ (2-1)(B_4-1)+S_2(B_4)=1\cdot 2+S_2(3)=2+2=4.$$
Also
$$D(100)=17+4=21,$$
genau wie im Kontrollwert der Implementierung.
Die C++-, Python- und Java-Implementierungen folgen demselben Schema. Zuerst berechnen sie \(P=\lfloor\log_2(N-2)\rfloor\). Dann bestimmen sie für jedes \(2\le p\le P\) die Schranke \(B_p(N)\) per monotoner Binärsuche über \(a\), wobei Potenzen überlaufssicher geprüft werden.
Anschließend berechnen sie die Wurzelkettensumme \(S_e(A)\), indem sie wiederholt ganzzahlige \(e\)-te, \(e^2\)-te, \(e^3\)-te Wurzeln per Binärsuche auswerten. Zuerst wird die Ebene \(L=1\) addiert. Danach laufen sie über alle \(e\) und alle Potenzen \(e^L\) mit \(L\ge 2\) und addieren jeweils
$$ (L-1)\bigl(B_{e^L}(N)-1\bigr)+S_e\bigl(B_{e^L}(N)\bigr). $$
Explizite Folgensimulation ist nirgends nötig; alles reduziert sich auf sichere Ganzzahlarithmetik, Binärsuche und kurze Exponentenschleifen.
Mit \(P=\lfloor\log_2(N-2)\rfloor\) gibt es nur \(O(P)\) relevante kombinierte Exponenten und nur \(O(P)\) Paare \((e,L)\) mit \(e^L\le P\). Jede Schranken- oder Wurzelsuche ist eine Binärsuche über \(a\), und jeder Mittelpunkttest benötigt eine Potenzberechnung der Länge höchstens \(P\). Eine sichere obere Schranke ist daher \(O(P^3\log N)\) Zeit bei \(O(P)\) Speicher. Für das eigentliche Ziel \(N=10^{18}\) gilt \(P\le 59\), also ist das Verfahren mehr als schnell genug.
Sabit \(n>1\) ve \(e>1\) için bir mirror power sequence şu yinelemeyle tanımlanır:
$$a_{i+1}=\min(a_i^e,\,n-a_i^e),\qquad a_i>1.$$
Her \(n\) için \(C(n)\), tüm \(e>1\) değerleri üzerinden elde edilen sonsuz dizilerin sayısı olsun. Aranan toplam
$$D(N)=\sum_{n=2}^{N} C(n)$$
şeklindedir. Burada önemli nokta şudur: Aynı çevrime sonradan girseler bile farklı geçerli başlangıç değerleri farklı diziler olarak sayılır.
Uygulama, diziyi terim terim simüle etmek yerine her sonsuz diziyi en küçük çevrim değeri, üs \(e\) ve çevrim uzunluğu \(L\) ile sınıflandırır.
Tüm terimler \(2\) ile \(n-2\) arasındadır. Bu yüzden sonsuz bir dizi sonunda periyodik olmak zorundadır. Periyodik bölümdeki en küçük değeri \(a\) ile gösterelim.
Bu en küçük değerden çıkarken tekrar tekrar kuvvet dalı seçilmek zorundadır; aksi halde dizi hemen \(a\)'nın altına iner ve minimalite bozulur. Dolayısıyla periyodik çekirdek
$$a \to a^e \to a^{e^2} \to \cdots \to a^{e^{L-1}} \to a$$
şeklindedir. Son adımda \(a\)'ya dönüş ayna dalından geldiği için
$$n-a^{e^L}=a$$
olmalıdır. Böylece her sonsuz mirror power sequence için
$$\boxed{n=a+a^{e^L}},\qquad a>1,\ e>1,\ L\ge 1$$
eşitliğini elde ederiz. Tersine, bu eşitlik sağlandığında yukarıdaki çevrim gerçekten oluşur; yani karakterizasyon tamdır.
Şu gösterimi yapalım:
$$p=e^L.$$
Sabit bir birleşik üs \(p\) için
$$B_p(N)=\max\{a\ge 1:\ a+a^p\le N\}$$
tanımını yapalım. O zaman bu \(p\) için bütün geçerli tabanlar
$$2\le a\le B_p(N)$$
aralığındadır. En küçük olası taban \(2\) olduğundan
$$2+2^p\le N$$
gerekir. Demek ki yalnızca
$$2\le p\le P:=\left\lfloor \log_2(N-2)\right\rfloor$$
değerleri katkı yapabilir. \(N=10^{18}\) için bile gerekli üs listesi bu yüzden çok kısadır.
Sabit \(a\), \(e\) ve \(L\) için çevrimin kendisi zaten \(L\) farklı başlangıç verir:
$$a,\ a^e,\ a^{e^2},\ \dots,\ a^{e^{L-1}}.$$
Çevrim başlamadan önce ek başlangıçlar da olabilir. Eğer \(a=b^e\) ise \(b\)'den başlamak bir adımda \(a\)'ya ulaşır. Eğer \(a=c^{e^2}\) ise \(c\) veya \(c^e\) ile başlamak da aynı çevrime ulaşır.
\(\rho_e(a)\), \(a\)'da sonlanan tam sayı \(e\)-kök zincirindeki değer sayısı olsun. Başka bir deyişle, \(\rho_e(a)\), \(1\)'in üstünde kalarak tam sayı \(e\)-inci kök işlemini kaç kez art arda uygulayabildiğimizin bir fazlasıdır.
Buna göre sabit bir \((a,e,L)\) üçlüsünün katkısı
$$\rho_e(a)+(L-1)$$
adet farklı dizidir: \(\rho_e(a)\) tanesi ilk çevrim düğümü olan \(a\)'ya akar, kalan \(L-1\) tanesi ise çevrimin diğer noktalarından başlar.
Eğer \(a\), tam bir \(e\)-inci kuvvet değilse \(\rho_e(a)=1\) olur ve katkı tam olarak \(L\)'dir. Örneğin \(a=16\) ve \(e=2\) için kök zinciri \(2\to 4\to 16\) olduğundan \(\rho_2(16)=3\).
Sabit bir \(e\) için
$$S_e(A)=\sum_{a=2}^{A}\rho_e(a)$$
olsun. \(\rho_e(a)\), \(a\)'nın tam \(e\)-inci, \(e^2\)-inci, \(e^3\)-üncü kuvvet olup olmadığını sayar. Bu yüzden toplamı tabanlara göre değil kök derinliğine göre yazabiliriz:
$$S_e(A)=(A-1)+\left(\left\lfloor A^{1/e}\right\rfloor-1\right)+\left(\left\lfloor A^{1/e^2}\right\rfloor-1\right)+\left(\left\lfloor A^{1/e^3}\right\rfloor-1\right)+\cdots.$$
\(\lfloor A^{1/e^k}\rfloor<2\) olduğunda seri durur. Uygulamadaki tekrar eden tam sayı kök hesapları tam olarak bu özdeşliği değerlendirir.
\(L=1\) durumu \(p=e\) anlamına gelir. Bu katmanın toplamı
$$\sum_{p=2}^{P} S_p\bigl(B_p(N)\bigr)$$
olur. \(L\ge 2\) için, \(e^L\le P\) koşulunu sağlayan her \((e,L)\) çifti şu kadar katkı verir:
$$\sum_{a=2}^{B_{e^L}(N)} \bigl(\rho_e(a)+(L-1)\bigr)=(L-1)\bigl(B_{e^L}(N)-1\bigr)+S_e\bigl(B_{e^L}(N)\bigr).$$
Dolayısıyla
$$\boxed{D(N)=\sum_{p=2}^{P} S_p\bigl(B_p(N)\bigr)+\sum_{e=2}^{P}\ \sum_{\substack{L\ge 2\\ e^L\le P}}\left((L-1)\bigl(B_{e^L}(N)-1\bigr)+S_e\bigl(B_{e^L}(N)\bigr)\right).}$$
Üç dildeki uygulamalar tam olarak bu sayma formülünü kullanır.
Burada
$$P=\left\lfloor \log_2(98)\right\rfloor=6$$
olur. Taban sınırları
$$B_2=9,\quad B_3=4,\quad B_4=3,\quad B_5=2,\quad B_6=2$$
şeklindedir. Önce \(L=1\) katmanını hesaplayalım:
$$S_2(9)=8+2=10,$$
çünkü \(2,\dots,9\) aralığında kare kök zincirinden ek katkı alan sayılar \(4\) ve \(9\)'dur. Ayrıca
$$S_3(4)=3,\qquad S_4(3)=2,\qquad S_5(2)=1,\qquad S_6(2)=1.$$
Böylece ara toplam
$$10+3+2+1+1=17$$
olur. \(L\ge 2\) için tek olasılık \(e=2\), \(L=2\)'dir; çünkü \(2^2=4\le 6\), ama \(2^3=8>6\). Katkı
$$ (2-1)(B_4-1)+S_2(B_4)=1\cdot 2+S_2(3)=2+2=4$$
çıkar. Sonuç olarak
$$D(100)=17+4=21,$$
ve bu değer uygulamadaki kontrol sonucuyla aynıdır.
C++, Python ve Java uygulamaları aynı planı izler. Önce \(P=\lfloor\log_2(N-2)\rfloor\) hesaplanır. Sonra her \(2\le p\le P\) için \(B_p(N)\) değeri, taşmayı güvenli biçimde kontrol eden kuvvet karşılaştırmalarıyla monoton bir ikili arama üzerinden bulunur.
Daha sonra \(S_e(A)\) toplamı, art arda tam sayı \(e\)-inci, \(e^2\)-inci, \(e^3\)-üncü kökler alınarak yine ikili aramayla hesaplanır. İlk olarak \(L=1\) katmanı eklenir. Ardından tüm \(e\) değerleri ve \(L\ge 2\) için bütün \(e^L\) kuvvetleri dolaşılıp
$$ (L-1)\bigl(B_{e^L}(N)-1\bigr)+S_e\bigl(B_{e^L}(N)\bigr) $$
terimi toplanır. Hiçbir yerde açık dizi simülasyonu yapılmaz; tüm işlem güvenli tam sayı aritmetiği, ikili arama ve kısa üs döngülerine indirgenmiştir.
\(P=\lfloor\log_2(N-2)\rfloor\) olsun. İlgili birleşik üs sayısı yalnızca \(O(P)\), \(e^L\le P\) koşulunu sağlayan \((e,L)\) çiftlerinin sayısı da yine \(O(P)\)'dir. Her sınır veya kök araması bir ikili aramadır; her orta nokta testi ise uzunluğu en fazla \(P\) olan bir kuvvet hesabı içerir. Dolayısıyla güvenli bir üst sınır \(O(P^3\log N)\) zamandır; bellek kullanımı ise \(O(P)\)'dir. Hedef değer \(N=10^{18}\) için \(P\le 59\) olduğundan yöntem fazlasıyla hızlıdır.
Para enteros fijos \(n>1\) y \(e>1\), una mirror power sequence está definida por
$$a_{i+1}=\min(a_i^e,\,n-a_i^e),\qquad a_i>1.$$
Para cada \(n\), sea \(C(n)\) el número de secuencias infinitas obtenidas al considerar todos los exponentes \(e>1\). La cantidad pedida es
$$D(N)=\sum_{n=2}^{N} C(n).$$
Un detalle importante es que distintos valores iniciales válidos cuentan como secuencias distintas, aunque más tarde entren en el mismo ciclo.
La implementación no simula la recurrencia paso a paso. En su lugar, clasifica cada secuencia infinita por un valor mínimo del ciclo, un exponente \(e\) y una longitud de ciclo \(L\).
Todos los términos satisfacen \(2\le a_i\le n-2\). Por eso, cualquier secuencia infinita acaba siendo periódica. Tomemos la parte periódica y llamemos \(a\) a su menor valor.
Desde ese valor mínimo, la rama de potencia debe repetirse varias veces; si no, la sucesión caería inmediatamente por debajo de \(a\), contradiciendo la minimalidad. Así, el núcleo periódico tiene la forma
$$a \to a^e \to a^{e^2} \to \cdots \to a^{e^{L-1}} \to a$$
para algún \(L\ge 1\). El último regreso a \(a\) usa la rama espejo, de modo que
$$n-a^{e^L}=a.$$
Por tanto, toda secuencia infinita queda descrita por
$$\boxed{n=a+a^{e^L}},\qquad a>1,\ e>1,\ L\ge 1.$$
Y a la inversa, cuando esta identidad se cumple, el ciclo mostrado es válido. Esa es la caracterización fundamental usada por el programa.
Escribamos
$$p=e^L.$$
Para un exponente combinado fijo \(p\), definimos
$$B_p(N)=\max\{a\ge 1:\ a+a^p\le N\}.$$
Entonces todas las bases válidas para ese \(p\) cumplen
$$2\le a\le B_p(N).$$
La base mínima posible es \(2\), así que necesariamente
$$2+2^p\le N.$$
De aquí se deduce que solo pueden contribuir los exponentes
$$2\le p\le P:=\left\lfloor \log_2(N-2)\right\rfloor.$$
Por eso, incluso cuando \(N=10^{18}\), el rango real de exponentes sigue siendo muy pequeño.
Para un triple fijo \((a,e,L)\), el propio ciclo aporta ya \(L\) inicios distintos:
$$a,\ a^e,\ a^{e^2},\ \dots,\ a^{e^{L-1}}.$$
Puede haber además inicios anteriores al ciclo. Si \(a=b^e\), empezar en \(b\) llega a \(a\) en un solo paso. Si \(a=c^{e^2}\), entonces empezar en \(c\) o en \(c^e\) también termina entrando en el mismo ciclo.
Definamos \(\rho_e(a)\) como el número de valores de la cadena de raíces enteras \(e\)-ésimas que termina en \(a\). Equivale a \(1\) más el número de veces que podemos tomar una raíz entera exacta \(e\)-ésima sin bajar hasta \(1\) o menos.
Entonces un triple fijo \((a,e,L)\) contribuye con
$$\rho_e(a)+(L-1)$$
secuencias distintas: \(\rho_e(a)\) que alimentan el primer nodo del ciclo, y las otras \(L-1\) que empiezan en los demás puntos del ciclo.
Si \(a\) no es una potencia \(e\)-ésima perfecta, entonces \(\rho_e(a)=1\) y la contribución es exactamente \(L\). Por ejemplo, si \(a=16\) y \(e=2\), la cadena de raíces es \(2\to 4\to 16\), así que \(\rho_2(16)=3\).
Para un exponente fijo \(e\), definimos
$$S_e(A)=\sum_{a=2}^{A}\rho_e(a).$$
La función \(\rho_e(a)\) cuenta si \(a\) es una potencia \(e\)-ésima, \(e^2\)-ésima, \(e^3\)-ésima, etcétera. Por eso conviene sumar por profundidad de raíz:
$$S_e(A)=(A-1)+\left(\left\lfloor A^{1/e}\right\rfloor-1\right)+\left(\left\lfloor A^{1/e^2}\right\rfloor-1\right)+\left(\left\lfloor A^{1/e^3}\right\rfloor-1\right)+\cdots.$$
La serie se detiene cuando \(\lfloor A^{1/e^k}\rfloor<2\). Esa es exactamente la identidad que evalúan las implementaciones mediante búsquedas binarias de raíces enteras.
El caso \(L=1\) equivale a \(p=e\). Su contribución total es
$$\sum_{p=2}^{P} S_p\bigl(B_p(N)\bigr).$$
Para \(L\ge 2\), cada par \((e,L)\) con \(e^L\le P\) aporta
$$\sum_{a=2}^{B_{e^L}(N)} \bigl(\rho_e(a)+(L-1)\bigr)=(L-1)\bigl(B_{e^L}(N)-1\bigr)+S_e\bigl(B_{e^L}(N)\bigr).$$
En consecuencia,
$$\boxed{D(N)=\sum_{p=2}^{P} S_p\bigl(B_p(N)\bigr)+\sum_{e=2}^{P}\ \sum_{\substack{L\ge 2\\ e^L\le P}}\left((L-1)\bigl(B_{e^L}(N)-1\bigr)+S_e\bigl(B_{e^L}(N)\bigr)\right).}$$
Esa es la fórmula de conteo implementada en C++, Python y Java.
Aquí
$$P=\left\lfloor \log_2(98)\right\rfloor=6.$$
Los límites de base son
$$B_2=9,\quad B_3=4,\quad B_4=3,\quad B_5=2,\quad B_6=2.$$
Primero calculamos la capa \(L=1\):
$$S_2(9)=8+2=10,$$
porque entre \(2\) y \(9\) los aportes extra por raíces cuadradas vienen de \(4\) y \(9\). Además,
$$S_3(4)=3,\qquad S_4(3)=2,\qquad S_5(2)=1,\qquad S_6(2)=1.$$
La suma parcial es entonces
$$10+3+2+1+1=17.$$
Para \(L\ge 2\), la única posibilidad es \(e=2\), \(L=2\), ya que \(2^2=4\le 6\) pero \(2^3=8>6\). Su contribución vale
$$ (2-1)(B_4-1)+S_2(B_4)=1\cdot 2+S_2(3)=2+2=4.$$
Por tanto,
$$D(100)=17+4=21,$$
en perfecto acuerdo con el valor de comprobación de la implementación.
Las implementaciones en C++, Python y Java siguen el mismo esquema. Primero calculan \(P=\lfloor\log_2(N-2)\rfloor\). Después, para cada \(2\le p\le P\), obtienen \(B_p(N)\) mediante una búsqueda binaria monótona sobre \(a\), usando comparaciones de potencias seguras frente a overflow para decidir si \(a+a^p\le N\).
Luego evalúan \(S_e(A)\) tomando sucesivamente raíces enteras \(e\)-ésimas, \(e^2\)-ésimas, \(e^3\)-ésimas, también con búsqueda binaria. Se suma primero la capa \(L=1\). Después se recorren todos los valores de \(e\) y todas las potencias \(e^L\) con \(L\ge 2\), añadiendo en cada caso
$$ (L-1)\bigl(B_{e^L}(N)-1\bigr)+S_e\bigl(B_{e^L}(N)\bigr). $$
No hace falta simular ninguna secuencia explícita; todo se reduce a aritmética entera segura, búsquedas binarias y bucles cortos sobre exponentes.
Sea \(P=\lfloor\log_2(N-2)\rfloor\). Solo hay \(O(P)\) exponentes combinados relevantes y \(O(P)\) pares \((e,L)\) con \(e^L\le P\). Cada búsqueda de límite o de raíz es una búsqueda binaria en \(a\), y cada prueba del punto medio necesita calcular una potencia de longitud a lo sumo \(P\). Una cota superior segura es entonces \(O(P^3\log N)\) en tiempo y \(O(P)\) en memoria. Para el objetivo real \(N=10^{18}\), se tiene \(P\le 59\), así que el método resulta sobradamente rápido.
对固定整数 \(n>1\) 与 \(e>1\)，mirror power sequence 由递推式
$$a_{i+1}=\min(a_i^e,\,n-a_i^e),\qquad a_i>1$$
定义。对每个 \(n\)，令 \(C(n)\) 表示在所有 \(e>1\) 下得到的无限序列总数。目标函数是
$$D(N)=\sum_{n=2}^{N} C(n).$$
这里要特别注意：即使两个起点最后进入同一个循环，只要初始值不同，它们仍然算作不同的序列。
实现并不逐项模拟递推，而是把每一条无限序列归结为三个整数参数：循环中的最小值、指数 \(e\) 与循环长度 \(L\)。
所有项都满足 \(2\le a_i\le n-2\)，因此任何无限序列最终都必须进入周期。设周期部分中的最小值为 \(a\)。
从这个最小值出发，递推必须连续走幂分支；否则下一项会立刻掉到 \(a\) 以下，与“\(a\) 是周期最小值”矛盾。所以周期核心只能是
$$a \to a^e \to a^{e^2} \to \cdots \to a^{e^{L-1}} \to a,$$
其中 \(L\ge 1\)。最后一步回到 \(a\) 时必然走镜像分支，因此满足
$$n-a^{e^L}=a.$$
于是每一条无限 mirror power sequence 都对应于
$$\boxed{n=a+a^{e^L}},\qquad a>1,\ e>1,\ L\ge 1.$$
反过来，只要这个等式成立，上面写出的循环就确实有效。因此，这个参数化不是近似，而是完整刻画。
记
$$p=e^L.$$
对固定的合并指数 \(p\)，定义
$$B_p(N)=\max\{a\ge 1:\ a+a^p\le N\}.$$
那么所有可行的底数都满足
$$2\le a\le B_p(N).$$
由于最小可能底数是 \(2\)，必须有
$$2+2^p\le N.$$
因此真正可能产生贡献的指数只有
$$2\le p\le P:=\left\lfloor \log_2(N-2)\right\rfloor.$$
这也解释了为什么即使 \(N=10^{18}\)，程序实际需要处理的指数种类仍然非常少。
对固定的三元组 \((a,e,L)\)，循环本身已经提供了 \(L\) 个不同起点：
$$a,\ a^e,\ a^{e^2},\ \dots,\ a^{e^{L-1}}.$$
但循环之前还可能存在额外起点。如果 \(a=b^e\)，那么从 \(b\) 出发，一步之后就到达 \(a\)。如果 \(a=c^{e^2}\)，那么从 \(c\) 或 \(c^e\) 出发，也都会最终汇入同一个循环。
定义 \(\rho_e(a)\) 为以 \(a\) 结尾的整数 \(e\) 次根链的长度。也就是说，\(\rho_e(a)\) 等于 \(1\) 加上“在始终大于 \(1\) 的前提下，能够连续取多少次精确整数 \(e\) 次根”。
于是固定三元组 \((a,e,L)\) 的贡献就是
$$\rho_e(a)+(L-1).$$
其中 \(\rho_e(a)\) 对应所有最终先流入循环首节点 \(a\) 的起点，另外 \(L-1\) 对应循环上的其余节点。
如果 \(a\) 不是完全 \(e\) 次幂，那么 \(\rho_e(a)=1\)，此时贡献正好就是 \(L\)。例如 \(a=16\)、\(e=2\) 时，根链是 \(2\to 4\to 16\)，所以 \(\rho_2(16)=3\)。
对固定 \(e\)，定义
$$S_e(A)=\sum_{a=2}^{A}\rho_e(a).$$
\(\rho_e(a)\) 本质上是在统计 \(a\) 是否为完全 \(e\) 次幂、完全 \(e^2\) 次幂、完全 \(e^3\) 次幂，依此类推。因此可以按“根的深度”来改写总和：
$$S_e(A)=(A-1)+\left(\left\lfloor A^{1/e}\right\rfloor-1\right)+\left(\left\lfloor A^{1/e^2}\right\rfloor-1\right)+\left(\left\lfloor A^{1/e^3}\right\rfloor-1\right)+\cdots.$$
当 \(\lfloor A^{1/e^k}\rfloor<2\) 时，这个级数就停止。程序中反复进行的整数开根二分搜索，正是在计算这个表达式。
当 \(L=1\) 时，有 \(p=e\)。这一层的总贡献为
$$\sum_{p=2}^{P} S_p\bigl(B_p(N)\bigr).$$
对 \(L\ge 2\)，每个满足 \(e^L\le P\) 的 \((e,L)\) 都贡献
$$\sum_{a=2}^{B_{e^L}(N)} \bigl(\rho_e(a)+(L-1)\bigr)=(L-1)\bigl(B_{e^L}(N)-1\bigr)+S_e\bigl(B_{e^L}(N)\bigr).$$
因此
$$\boxed{D(N)=\sum_{p=2}^{P} S_p\bigl(B_p(N)\bigr)+\sum_{e=2}^{P}\ \sum_{\substack{L\ge 2\\ e^L\le P}}\left((L-1)\bigl(B_{e^L}(N)-1\bigr)+S_e\bigl(B_{e^L}(N)\bigr)\right).}$$
这就是 C++、Python 和 Java 实现共同遵循的计数公式。
此时
$$P=\left\lfloor \log_2(98)\right\rfloor=6.$$
对应的底数上界为
$$B_2=9,\quad B_3=4,\quad B_4=3,\quad B_5=2,\quad B_6=2.$$
先看 \(L=1\) 这一层：
$$S_2(9)=8+2=10,$$
因为在 \(2\) 到 \(9\) 之间，额外提供平方根链贡献的只有 \(4\) 与 \(9\)。此外还有
$$S_3(4)=3,\qquad S_4(3)=2,\qquad S_5(2)=1,\qquad S_6(2)=1.$$
所以 \(L=1\) 的小计为
$$10+3+2+1+1=17.$$
对 \(L\ge 2\)，唯一可能是 \(e=2\)、\(L=2\)，因为 \(2^2=4\le 6\)，而 \(2^3=8>6\)。这一项的贡献是
$$ (2-1)(B_4-1)+S_2(B_4)=1\cdot 2+S_2(3)=2+2=4.$$
因此
$$D(100)=17+4=21,$$
与实现中的校验值完全一致。
C++、Python 和 Java 三个实现采用同一套流程。首先计算 \(P=\lfloor\log_2(N-2)\rfloor\)。随后对每个 \(2\le p\le P\)，通过单调二分搜索求出 \(B_p(N)\)，并在每次比较时使用防溢出的整数幂判断来测试 \(a+a^p\le N\) 是否成立。
接着，通过反复计算整数 \(e\) 次根、\(e^2\) 次根、\(e^3\) 次根来得到 \(S_e(A)\)，这些开根操作同样使用二分搜索。程序先累加 \(L=1\) 的部分，再枚举所有 \(e\) 和所有满足 \(L\ge 2\) 的幂 \(e^L\)，并加入
$$ (L-1)\bigl(B_{e^L}(N)-1\bigr)+S_e\bigl(B_{e^L}(N)\bigr). $$
整个过程完全不需要显式生成序列本身；它只依赖安全的整数运算、二分搜索以及很短的指数循环。
设 \(P=\lfloor\log_2(N-2)\rfloor\)。相关的合并指数只有 \(O(P)\) 个，满足 \(e^L\le P\) 的参数对 \((e,L)\) 也只有 \(O(P)\) 个。每次边界搜索或开根搜索都是一次关于 \(a\) 的二分搜索，而每个二分中点测试最多只需做长度为 \(P\) 的整数幂计算。因此保守上界可写成 \(O(P^3\log N)\) 时间与 \(O(P)\) 空间。对目标 \(N=10^{18}\) 而言，\(P\le 59\)，所以该方法在实际中非常轻量。
Для фиксированных целых \(n>1\) и \(e>1\) mirror power sequence задаётся правилом
$$a_{i+1}=\min(a_i^e,\,n-a_i^e),\qquad a_i>1.$$
Для каждого \(n\) обозначим через \(C(n)\) число бесконечных последовательностей, если разрешены все показатели \(e>1\). Требуется вычислить
$$D(N)=\sum_{n=2}^{N} C(n).$$
Важно, что разные допустимые начальные значения считаются разными последовательностями, даже если позже они попадают в один и тот же цикл.
Реализация не моделирует рекурсию по членам. Вместо этого каждая бесконечная последовательность описывается минимальным значением в цикле, показателем \(e\) и длиной цикла \(L\).
Все члены лежат между \(2\) и \(n-2\), поэтому бесконечная последовательность обязана со временем стать периодической. Пусть \(a\) — минимальное значение на периодической части.
Из этого минимального значения несколько раз подряд должна выбираться степенная ветвь; иначе следующий член сразу стал бы меньше \(a\), что противоречит минимальности. Значит, периодическое ядро имеет вид
$$a \to a^e \to a^{e^2} \to \cdots \to a^{e^{L-1}} \to a$$
для некоторого \(L\ge 1\). Последний возврат к \(a\) идёт через зеркальную ветвь, поэтому
$$n-a^{e^L}=a.$$
Следовательно, каждая бесконечная mirror power sequence определяется равенством
$$\boxed{n=a+a^{e^L}},\qquad a>1,\ e>1,\ L\ge 1.$$
И наоборот, если это равенство выполнено, указанный цикл действительно существует. Именно это описание лежит в основе всей программы.
Обозначим
$$p=e^L.$$
Для фиксированного составного показателя \(p\) введём
$$B_p(N)=\max\{a\ge 1:\ a+a^p\le N\}.$$
Тогда все допустимые базы для этого \(p\) лежат в диапазоне
$$2\le a\le B_p(N).$$
Минимально возможная база равна \(2\), значит обязательно
$$2+2^p\le N.$$
Отсюда следует, что учитывать нужно только
$$2\le p\le P:=\left\lfloor \log_2(N-2)\right\rfloor.$$
Поэтому даже при \(N=10^{18}\) реальный диапазон показателей остаётся очень маленьким.
Для фиксированных \(a\), \(e\) и \(L\) сам цикл даёт уже \(L\) различных стартов:
$$a,\ a^e,\ a^{e^2},\ \dots,\ a^{e^{L-1}}.$$
Но возможны и дополнительные старты до входа в цикл. Если \(a=b^e\), то старт из \(b\) приводит к \(a\) за один шаг. Если \(a=c^{e^2}\), то старт из \(c\) или \(c^e\) также в итоге попадает в тот же цикл.
Обозначим через \(\rho_e(a)\) длину целочисленной цепочки \(e\)-х корней, оканчивающейся в \(a\). Иначе говоря, это \(1\) плюс число раз, сколько можно подряд брать точный целый \(e\)-й корень, оставаясь выше \(1\).
Тогда вклад одного фиксированного тройного параметра равен
$$\rho_e(a)+(L-1).$$
\(\rho_e(a)\) соответствует всем стартам, которые сначала входят в первый узел цикла \(a\), а ещё \(L-1\) дают остальные точки цикла.
Если \(a\) не является точной \(e\)-й степенью, то \(\rho_e(a)=1\), и вклад равен ровно \(L\). Например, при \(a=16\) и \(e=2\) цепочка корней имеет вид \(2\to 4\to 16\), поэтому \(\rho_2(16)=3\).
Для фиксированного \(e\) определим
$$S_e(A)=\sum_{a=2}^{A}\rho_e(a).$$
Величина \(\rho_e(a)\) проверяет, является ли \(a\) точной \(e\)-й, \(e^2\)-й, \(e^3\)-й степенью и так далее. Поэтому сумму удобно переписать по глубине корня:
$$S_e(A)=(A-1)+\left(\left\lfloor A^{1/e}\right\rfloor-1\right)+\left(\left\lfloor A^{1/e^2}\right\rfloor-1\right)+\left(\left\lfloor A^{1/e^3}\right\rfloor-1\right)+\cdots.$$
Ряд обрывается, когда \(\lfloor A^{1/e^k}\rfloor<2\). Именно эту формулу реализация вычисляет через повторяющийся поиск целого корня.
Случай \(L=1\) означает \(p=e\). Его суммарный вклад равен
$$\sum_{p=2}^{P} S_p\bigl(B_p(N)\bigr).$$
Для \(L\ge 2\) каждая пара \((e,L)\) с условием \(e^L\le P\) даёт вклад
$$\sum_{a=2}^{B_{e^L}(N)} \bigl(\rho_e(a)+(L-1)\bigr)=(L-1)\bigl(B_{e^L}(N)-1\bigr)+S_e\bigl(B_{e^L}(N)\bigr).$$
Следовательно,
$$\boxed{D(N)=\sum_{p=2}^{P} S_p\bigl(B_p(N)\bigr)+\sum_{e=2}^{P}\ \sum_{\substack{L\ge 2\\ e^L\le P}}\left((L-1)\bigl(B_{e^L}(N)-1\bigr)+S_e\bigl(B_{e^L}(N)\bigr)\right).}$$
Именно эта формула используется во всех трёх реализациях.
Здесь
$$P=\left\lfloor \log_2(98)\right\rfloor=6.$$
Границы по базе таковы:
$$B_2=9,\quad B_3=4,\quad B_4=3,\quad B_5=2,\quad B_6=2.$$
Сначала слой \(L=1\):
$$S_2(9)=8+2=10,$$
поскольку среди чисел от \(2\) до \(9\) дополнительные вклады по квадратным корням дают только \(4\) и \(9\). Кроме того,
$$S_3(4)=3,\qquad S_4(3)=2,\qquad S_5(2)=1,\qquad S_6(2)=1.$$
Итак, промежуточная сумма равна
$$10+3+2+1+1=17.$$
Для \(L\ge 2\) возможен только вариант \(e=2\), \(L=2\), потому что \(2^2=4\le 6\), а \(2^3=8>6\). Его вклад равен
$$ (2-1)(B_4-1)+S_2(B_4)=1\cdot 2+S_2(3)=2+2=4.$$
Следовательно,
$$D(100)=17+4=21,$$
что совпадает с контрольным значением в реализации.
Реализации на C++, Python и Java используют один и тот же план. Сначала вычисляется \(P=\lfloor\log_2(N-2)\rfloor\). Затем для каждого \(2\le p\le P\) через монотонный бинарный поиск по \(a\) находится значение \(B_p(N)\), причём сравнения степеней выполнены безопасно по отношению к переполнению.
После этого вычисляется сумма \(S_e(A)\): программа последовательно ищет целые \(e\)-е, \(e^2\)-е, \(e^3\)-и корни, снова при помощи бинарного поиска. Сначала добавляется слой \(L=1\). Затем перебираются все \(e\) и все степени \(e^L\) с \(L\ge 2\), и каждый раз прибавляется выражение
$$ (L-1)\bigl(B_{e^L}(N)-1\bigr)+S_e\bigl(B_{e^L}(N)\bigr). $$
Явная симуляция последовательностей нигде не нужна; вся задача сведена к безопасной целочисленной арифметике, бинарному поиску и коротким циклам по показателям.
Пусть \(P=\lfloor\log_2(N-2)\rfloor\). Тогда существует только \(O(P)\) значимых составных показателей и только \(O(P)\) пар \((e,L)\), удовлетворяющих \(e^L\le P\). Каждый поиск границы или целого корня является бинарным поиском по \(a\), а каждая проверка середины требует вычислить степень длины не более \(P\). Поэтому надёжная верхняя оценка равна \(O(P^3\log N)\) по времени и \(O(P)\) по памяти. Для реального целевого значения \(N=10^{18}\) имеем \(P\le 59\), так что алгоритм получается очень лёгким.
لعددين صحيحين ثابتين \(n>1\) و\(e>1\)، تُعرَّف mirror power sequence بالعلاقة
$$a_{i+1}=\min(a_i^e,\,n-a_i^e),\qquad a_i>1.$$
ولكل \(n\)، نرمز بـ \(C(n)\) إلى عدد المتتاليات اللانهائية الناتجة عند السماح بجميع القيم \(e>1\). والمطلوب هو
$$D(N)=\sum_{n=2}^{N} C(n).$$
والنقطة المهمة أن قيم البداية المختلفة تُعد متتاليات مختلفة، حتى لو دخلت لاحقًا في الدورة نفسها.
التنفيذ لا يحاكي المتتالية حدًا بعد حد، بل يصنّف كل متتالية لانهائية بواسطة أصغر قيمة في الدورة، والأس \(e\)، وطول الدورة \(L\).
جميع الحدود تقع بين \(2\) و\(n-2\)، ولذلك فكل متتالية لانهائية لا بد أن تصبح دورية في النهاية. لنأخذ الجزء الدوري، ولتكن \(a\) أصغر قيمة تظهر فيه.
انطلاقًا من هذه القيمة الصغرى يجب أن يُختار فرع القوة عدة مرات متتالية؛ وإلا لهبط الحد التالي مباشرة تحت \(a\)، وهذا يناقض كونها الأصغر على الدورة. لذلك يكون اللب الدوري على الصورة
$$a \to a^e \to a^{e^2} \to \cdots \to a^{e^{L-1}} \to a$$
لبعض \(L\ge 1\). والعودة الأخيرة إلى \(a\) تتم عبر الفرع المرآتي، وبالتالي
$$n-a^{e^L}=a.$$
إذن كل mirror power sequence لانهائية تُوصف بالهوية
$$\boxed{n=a+a^{e^L}},\qquad a>1,\ e>1,\ L\ge 1.$$
وبالعكس، إذا تحققت هذه الهوية فإن الدورة المعروضة تكون صحيحة فعلًا. هذه هي الفكرة المركزية التي تعتمد عليها الحلول الثلاثة.
لنكتب
$$p=e^L.$$
ولأس مركب ثابت \(p\) نعرّف
$$B_p(N)=\max\{a\ge 1:\ a+a^p\le N\}.$$
عندئذٍ كل قاعدة صالحة لهذا \(p\) تحقق
$$2\le a\le B_p(N).$$
وأصغر قاعدة ممكنة هي \(2\)، لذلك لا بد من
$$2+2^p\le N.$$
ومن ثم فإن القيم الوحيدة الممكنة هي
$$2\le p\le P:=\left\lfloor \log_2(N-2)\right\rfloor.$$
ولهذا السبب يبقى عدد الأسس الفعلية صغيرًا جدًا حتى عندما يكون \(N=10^{18}\).
عند تثبيت \(a\) و\(e\) و\(L\)، فإن الدورة نفسها تعطي \(L\) بدايات مختلفة:
$$a,\ a^e,\ a^{e^2},\ \dots,\ a^{e^{L-1}}.$$
وقد توجد بدايات إضافية قبل الدخول إلى الدورة. فإذا كان \(a=b^e\)، فإن البدء من \(b\) يصل إلى \(a\) في خطوة واحدة. وإذا كان \(a=c^{e^2}\)، فإن البدء من \(c\) أو من \(c^e\) يصل في النهاية إلى الدورة نفسها.
لنرمز بـ \(\rho_e(a)\) إلى عدد القيم في سلسلة الجذور الصحيحة من الرتبة \(e\) التي تنتهي عند \(a\). وبصياغة أخرى، \(\rho_e(a)\) يساوي \(1\) مضافًا إليه عدد المرات التي يمكن فيها أخذ جذر صحيح من الرتبة \(e\) بشكل متكرر مع البقاء أكبر من \(1\).
إذن مساهمة الثلاثية الثابتة \((a,e,L)\) هي
$$\rho_e(a)+(L-1).$$
\(\rho_e(a)\) تمثل جميع البدايات التي تنتهي أولًا إلى العقدة الأولى في الدورة، أما \(L-1\) الباقية فتمثل نقاط البداية الأخرى على الدورة نفسها.
إذا لم يكن \(a\) قوة \(e\)-ية تامة، فإن \(\rho_e(a)=1\)، وعندها تكون المساهمة مساوية تمامًا لـ \(L\). مثال ذلك: عندما \(a=16\) و\(e=2\)، تكون سلسلة الجذور \(2\to 4\to 16\)، ومن ثم \(\rho_2(16)=3\).
لأس ثابت \(e\)، نعرّف
$$S_e(A)=\sum_{a=2}^{A}\rho_e(a).$$
القيمة \(\rho_e(a)\) تختبر ما إذا كان \(a\) قوة تامة من الرتبة \(e\) أو \(e^2\) أو \(e^3\) وهكذا. لذلك يمكن إعادة كتابة المجموع بحسب عمق الجذر:
$$S_e(A)=(A-1)+\left(\left\lfloor A^{1/e}\right\rfloor-1\right)+\left(\left\lfloor A^{1/e^2}\right\rfloor-1\right)+\left(\left\lfloor A^{1/e^3}\right\rfloor-1\right)+\cdots.$$
ويتوقف هذا الجمع حين تصبح \(\lfloor A^{1/e^k}\rfloor<2\). وهذا بالضبط ما تحسبه الحلول عبر عمليات متكررة لاستخراج الجذر الصحيح باستخدام البحث الثنائي.
الحالة \(L=1\) تعني أن \(p=e\). ومساهمتها الكلية هي
$$\sum_{p=2}^{P} S_p\bigl(B_p(N)\bigr).$$
أما عندما \(L\ge 2\)، فإن كل زوج \((e,L)\) يحقق \(e^L\le P\) يضيف
$$\sum_{a=2}^{B_{e^L}(N)} \bigl(\rho_e(a)+(L-1)\bigr)=(L-1)\bigl(B_{e^L}(N)-1\bigr)+S_e\bigl(B_{e^L}(N)\bigr).$$
وعليه نحصل على
$$\boxed{D(N)=\sum_{p=2}^{P} S_p\bigl(B_p(N)\bigr)+\sum_{e=2}^{P}\ \sum_{\substack{L\ge 2\\ e^L\le P}}\left((L-1)\bigl(B_{e^L}(N)-1\bigr)+S_e\bigl(B_{e^L}(N)\bigr)\right).}$$
وهذه هي صيغة العد التي تنفذها نسخ C++ وPython وJava.
لدينا هنا
$$P=\left\lfloor \log_2(98)\right\rfloor=6.$$
وحدود القواعد تساوي
$$B_2=9,\quad B_3=4,\quad B_4=3,\quad B_5=2,\quad B_6=2.$$
لنبدأ بطبقة \(L=1\):
$$S_2(9)=8+2=10,$$
لأن العددين \(4\) و\(9\) فقط بين \(2\) و\(9\) يعطيان مساهمة إضافية من سلاسل الجذور التربيعية. كذلك
$$S_3(4)=3,\qquad S_4(3)=2,\qquad S_5(2)=1,\qquad S_6(2)=1.$$
إذن المجموع الجزئي هو
$$10+3+2+1+1=17.$$
وبالنسبة إلى \(L\ge 2\)، فالاحتمال الوحيد هو \(e=2\) و\(L=2\)، لأن \(2^2=4\le 6\) بينما \(2^3=8>6\). ومساهمته
$$ (2-1)(B_4-1)+S_2(B_4)=1\cdot 2+S_2(3)=2+2=4.$$
ومن ثم
$$D(100)=17+4=21,$$
وهو نفس مقدار التحقق الذي تعطيه التنفيذات.
التنفيذات في C++ وPython وJava تتبع الخطة نفسها. أولًا يُحسب \(P=\lfloor\log_2(N-2)\rfloor\). بعد ذلك، ولكل \(2\le p\le P\)، يُستخرج الحد \(B_p(N)\) بواسطة بحث ثنائي رتيب على \(a\)، مع مقارنات قوى آمنة ضد تجاوز السعة للتحقق من شرط \(a+a^p\le N\).
ثم يُحسب المجموع \(S_e(A)\) عبر أخذ الجذور الصحيحة من الرتبة \(e\)، ثم \(e^2\)، ثم \(e^3\) على التوالي، وكل ذلك أيضًا بواسطة البحث الثنائي. تُضاف أولًا مساهمة \(L=1\). وبعدها تُعدّد جميع القيم \(e\) وجميع القوى \(e^L\) مع \(L\ge 2\)، ويُضاف في كل مرة المقدار
$$ (L-1)\bigl(B_{e^L}(N)-1\bigr)+S_e\bigl(B_{e^L}(N)\bigr). $$
ولا توجد أي حاجة لمحاكاة المتتاليات صراحة؛ فالحساب كله يتحول إلى حسابات صحيحة آمنة، وبحث ثنائي، وحلقات قصيرة على الأسس.
إذا وضعنا \(P=\lfloor\log_2(N-2)\rfloor\)، فهناك فقط \(O(P)\) أسس مركبة ذات صلة، وفقط \(O(P)\) أزواج \((e,L)\) تحقق \(e^L\le P\). كل بحث عن حد أو جذر صحيح هو بحث ثنائي على \(a\)، وكل اختبار في منتصف البحث يحتاج إلى حساب قوة بطول لا يتجاوز \(P\). لذا فإن حدًا علويًا آمنًا هو \(O(P^3\log N)\) زمنًا و\(O(P)\) ذاكرة. وبالنسبة إلى الهدف الفعلي \(N=10^{18}\)، لدينا \(P\le 59\)، ولذلك تكون الطريقة عملية جدًا.