The implementations ultimately evaluate the stabilized residue of the tower \(2, 2^2, 2^{2^2}, \dots\) modulo \(10^{15}\), and then report that residue shifted by \(3\):
$$T(10^{15}) - 3 \pmod{10^{15}}.$$
Here \(T(m)\) denotes the eventual residue of a sufficiently tall tower of 2s modulo \(m\). The main difficulty is that powers of 2 behave very differently on the odd part of the modulus and on its power-of-two part, so the computation separates those two pieces and handles them in different ways.
Define the finite tower by \(a_1 = 2\) and \(a_{n+1} = 2^{a_n}\). For each modulus \(m\), the residues \(a_n \bmod m\) stabilize for large \(n\); call the stable residue \(T(m)\). The implementations compute \(T(m)\) by descending through the odd part of the modulus via Euler's totient function.
Once the residues stabilize, one more exponentiation produces the same class again, so the limit satisfies
$$T(m) \equiv 2^{T(m)} \pmod{m}.$$
This identity is not used as a brute-force equation solver. Its real purpose is to show that a very tall tower can be reconstructed from the behavior of its exponent modulo a smaller modulus.
Write
$$m = 2^s q, \qquad q \text{ odd}.$$
For a sufficiently tall tower, the outermost value is \(2^E\) with an exponent \(E\) much larger than \(s\), so the residue is automatically divisible by \(2^s\). Therefore
$$T(m) \equiv 0 \pmod{2^s}.$$
That means the residue can be written as
$$T(m) \equiv 2^s u \pmod{m}$$
for some class \(u \pmod{q}\). The problem is now reduced to finding this odd-part factor \(u\).
Because \(q\) is odd, \(\gcd(2,q)=1\), so Euler's theorem applies:
$$2^{k+\varphi(q)} \equiv 2^k \pmod{q}.$$
Thus the exponent only matters modulo \(\varphi(q)\). But that exponent is again a very tall tower of 2s, so its stable residue modulo \(\varphi(q)\) is exactly \(T(\varphi(q))\). Hence, modulo \(q\),
$$T(m) \equiv 2^{T(\varphi(q))} \pmod{q}.$$
Substituting \(T(m) \equiv 2^s u\) gives
$$2^s u \equiv 2^{T(\varphi(q))} \pmod{q}.$$
Since 2 is invertible modulo the odd number \(q\), we may divide by \(2^s\):
$$u \equiv 2^{T(\varphi(q)) - s} \pmod{q}.$$
If \(T(\varphi(q)) \ge s\), this is an ordinary modular power. If \(T(\varphi(q)) \lt s\), the exponent becomes negative, so we interpret it as
$$2^{-r} \equiv (2^{-1})^r \pmod{q}.$$
This is why the implementations explicitly compute the modular inverse of 2 on the odd modulus whenever the corrected exponent is negative.
Once \(u\) is known, the stabilized tower value is simply
$$T(m) \equiv 2^s u \pmod{m}.$$
For pure powers of two we have \(q=1\), so the answer is \(T(2^s)=0\). Otherwise the recursion continues with the strictly smaller modulus \(\varphi(q)\), which quickly reaches the base case
$$T(1)=0.$$
Take \(m = 40 = 2^3 \cdot 5\). Then \(s=3\), \(q=5\), and
$$\varphi(q) = \varphi(5) = 4.$$
Because \(4\) is a power of two, a tall enough tower is divisible by \(4\), so
$$T(4)=0.$$
Therefore
$$u \equiv 2^{T(4)-3} = 2^{-3} \pmod{5}.$$
The inverse of \(2\) modulo \(5\) is \(3\), so
$$u \equiv 3^3 \equiv 27 \equiv 2 \pmod{5}.$$
Hence
$$T(40) \equiv 2^3 \cdot 2 = 16 \pmod{40}.$$
A direct check confirms the fixed-point relation:
$$2^{16} = 65536 \equiv 16 \pmod{40}.$$
The C++, Python, and Java implementations all follow the same recursion. They memoize the stabilized residue for each modulus appearing on the totient chain, starting from the base value \(T(1)=0\). For the current modulus they remove all factors of 2, compute the odd part \(q\), factor \(q\) to obtain \(\varphi(q)\), recurse to find \(T(\varphi(q))\), and then correct the exponent by subtracting the number of removed factors of 2.
The odd-part contribution is evaluated as a modular power of 2. When the corrected exponent is negative, the implementation first finds the modular inverse of 2 modulo \(q\) with the extended Euclidean algorithm and then raises that inverse to the needed positive power. Finally it restores the factor \(2^s\), reduces modulo the original modulus, and after the top-level call at \(10^{15}\) it subtracts \(3\) modulo \(10^{15}\).
Let \(m_0 = m\), and at level \(i\) write \(m_i = 2^{s_i} q_i\) with \(q_i\) odd. The recursion then moves to \(m_{i+1} = \varphi(q_i)\) until it reaches 1. The depth is the length of this chain. At each level, the direct implementation computes \(\varphi(q_i)\) by trial division up to \(\sqrt{q_i}\), and performs one modular exponentiation costing \(O(\log q_i)\) modular multiplications. Therefore the running time is
$$O\left(\sum_i \sqrt{q_i} + \sum_i \log q_i\right),$$
while the memo table stores one residue per chain value, so the memory use is \(O(k)\), where \(k\) is the chain length. For the actual target modulus the chain shrinks very quickly, so the practical runtime is small.
Die Implementierungen berechnen letztlich den stabilen Restwert des Turms \(2, 2^2, 2^{2^2}, \dots\) modulo \(10^{15}\) und geben danach diesen Restwert um \(3\) verschoben aus:
$$T(10^{15}) - 3 \pmod{10^{15}}.$$
Dabei bezeichnet \(T(m)\) den endgültigen Rest eines hinreichend hohen Zweier-Potenzturms modulo \(m\). Die Schwierigkeit besteht darin, dass sich Zweierpotenzen auf dem ungeraden Teil des Moduls ganz anders verhalten als auf seinem Zweierpotenz-Anteil, weshalb die Rechnung diese beiden Strukturen getrennt behandelt.
Definiere den endlichen Turm durch \(a_1 = 2\) und \(a_{n+1} = 2^{a_n}\). Für jedes Modul \(m\) stabilisieren sich die Reste \(a_n \bmod m\) für große \(n\); diesen stabilen Rest nennen wir \(T(m)\). Die Implementierungen berechnen \(T(m)\), indem sie entlang der Eulerschen Phi-Funktion auf den ungeraden Anteil des Moduls hinabsteigen.
Sobald sich die Reste stabilisiert haben, liefert eine weitere Potenzierung wieder denselben Rest. Daher gilt
$$T(m) \equiv 2^{T(m)} \pmod{m}.$$
Diese Identität wird nicht als rohe Fixpunktgleichung gelöst. Sie zeigt vielmehr, dass sich ein sehr hoher Turm aus dem Verhalten seines Exponenten modulo eines kleineren Moduls rekonstruieren lässt.
Schreibe
$$m = 2^s q, \qquad q \text{ ungerade}.$$
Für einen hinreichend hohen Turm ist der äußerste Wert \(2^E\) mit einem Exponenten \(E\), der viel größer als \(s\) ist. Deshalb ist der Rest automatisch durch \(2^s\) teilbar:
$$T(m) \equiv 0 \pmod{2^s}.$$
Also kann man den Rest in der Form
$$T(m) \equiv 2^s u \pmod{m}$$
schreiben, wobei \(u\) eine Restklasse modulo \(q\) ist. Das Problem reduziert sich damit auf die Bestimmung dieses ungeraden Faktors \(u\).
Da \(q\) ungerade ist, gilt \(\gcd(2,q)=1\), also können wir Eulers Satz anwenden:
$$2^{k+\varphi(q)} \equiv 2^k \pmod{q}.$$
Der Exponent zählt also nur modulo \(\varphi(q)\). Dieser Exponent ist aber selbst wieder ein sehr hoher Zweier-Turm, und sein stabiler Rest modulo \(\varphi(q)\) ist genau \(T(\varphi(q))\). Daher gilt modulo \(q\)
$$T(m) \equiv 2^{T(\varphi(q))} \pmod{q}.$$
Setzt man \(T(m) \equiv 2^s u\) ein, erhält man
$$2^s u \equiv 2^{T(\varphi(q))} \pmod{q}.$$
Weil 2 modulo der ungeraden Zahl \(q\) invertierbar ist, dürfen wir durch \(2^s\) teilen:
$$u \equiv 2^{T(\varphi(q)) - s} \pmod{q}.$$
Ist \(T(\varphi(q)) \ge s\), handelt es sich um eine gewöhnliche modulare Potenz. Ist dagegen \(T(\varphi(q)) \lt s\), wird der Exponent negativ, und wir interpretieren
$$2^{-r} \equiv (2^{-1})^r \pmod{q}.$$
Genau deshalb berechnen die Implementierungen bei negativem korrigiertem Exponenten explizit das modulare Inverse von 2 auf dem ungeraden Modul.
Sobald \(u\) feststeht, ist der stabile Turmrest einfach
$$T(m) \equiv 2^s u \pmod{m}.$$
Für reine Zweierpotenzen ist \(q=1\), also gilt sofort \(T(2^s)=0\). Andernfalls setzt sich die Rekursion mit dem echt kleineren Modul \(\varphi(q)\) fort und erreicht schnell den Basisfall
$$T(1)=0.$$
Nimm \(m = 40 = 2^3 \cdot 5\). Dann sind \(s=3\), \(q=5\) und
$$\varphi(q) = \varphi(5) = 4.$$
Da \(4\) eine Zweierpotenz ist, ist ein genügend hoher Turm durch \(4\) teilbar, also
$$T(4)=0.$$
Damit folgt
$$u \equiv 2^{T(4)-3} = 2^{-3} \pmod{5}.$$
Das Inverse von \(2\) modulo \(5\) ist \(3\). Also
$$u \equiv 3^3 \equiv 27 \equiv 2 \pmod{5}.$$
Folglich
$$T(40) \equiv 2^3 \cdot 2 = 16 \pmod{40}.$$
Eine direkte Kontrolle bestätigt die Fixpunktbeziehung:
$$2^{16} = 65536 \equiv 16 \pmod{40}.$$
Die C++-, Python- und Java-Implementierungen folgen derselben Rekursion. Sie merken sich für jedes Modul auf der Phi-Kette den bereits berechneten stabilen Rest und starten mit dem Basiswert \(T(1)=0\). Für das aktuelle Modul entfernen sie zunächst alle Zweierfaktoren, bestimmen den ungeraden Anteil \(q\), faktorisieren \(q\) zur Berechnung von \(\varphi(q)\), rufen die Rekursion für \(T(\varphi(q))\) auf und korrigieren den Exponenten anschließend um die Anzahl der entfernten Zweierfaktoren.
Der Beitrag des ungeraden Teils wird dann als modulare Zweierpotenz berechnet. Ist der korrigierte Exponent negativ, bestimmt die Implementierung zuerst mit dem erweiterten euklidischen Algorithmus das modulare Inverse von 2 modulo \(q\) und potenziert anschließend dieses Inverse. Zum Schluss wird der Faktor \(2^s\) wieder eingesetzt, modulo des ursprünglichen Moduls reduziert und nach dem Aufruf für \(10^{15}\) noch \(3\) modulo \(10^{15}\) subtrahiert.
Sei \(m_0 = m\), und schreibe auf Ebene \(i\) den Wert als \(m_i = 2^{s_i} q_i\) mit ungeradem \(q_i\). Die Rekursion geht dann zu \(m_{i+1} = \varphi(q_i)\) weiter, bis 1 erreicht ist. Die Tiefe ist also die Länge dieser Kette. Auf jeder Ebene berechnet die direkte Implementierung \(\varphi(q_i)\) per Probedivision bis \(\sqrt{q_i}\) und führt eine modulare Potenzierung mit Kosten von \(O(\log q_i)\) modularen Multiplikationen aus. Damit beträgt die Laufzeit
$$O\left(\sum_i \sqrt{q_i} + \sum_i \log q_i\right),$$
während die Memoisierung nur einen Rest pro Kettenwert speichert und daher \(O(k)\) Speicher benötigt, wobei \(k\) die Kettenlänge ist. Für das konkrete Zielmodul schrumpft die Kette sehr schnell, daher ist die praktische Laufzeit klein.
İmplementasyonlar sonunda \(2, 2^2, 2^{2^2}, \dots\) kule dizisinin \(10^{15}\) modundaki kararlı kalıntısını hesaplıyor ve sonra bu değerden \(3\) çıkarılmış hali veriliyor:
$$T(10^{15}) - 3 \pmod{10^{15}}.$$
Burada \(T(m)\), yeterince yüksek bir 2 kuvvet kulesinin \(m\) modundaki sonunda sabitlenen değeridir. Asıl zorluk, 2 kuvvetlerinin modülün tek kısmında ve \(2\) kuvveti kısmında farklı davranmasıdır; bu yüzden çözüm modülü iki parçaya ayırır ve her parçayı ayrı ele alır.
Sonlu kuleyi \(a_1 = 2\) ve \(a_{n+1} = 2^{a_n}\) ile tanımlayalım. Her \(m\) modülü için \(a_n \bmod m\) kalıntıları büyük \(n\) değerlerinde sabitlenir; bu kararlı değere \(T(m)\) diyelim. İmplementasyonlar \(T(m)\) değerini, modülün tek kısmı üzerinden Euler phi fonksiyonuna doğru inen bir rekürsiyonla hesaplar.
Kalıntılar sabitlendikten sonra bir kat daha üs almak aynı sınıfı yeniden üretir. Bu yüzden limit değer
$$T(m) \equiv 2^{T(m)} \pmod{m}$$
eşitliğini sağlar. Bu denklem kaba kuvvetle çözülmez; önemli olan, çok yüksek bir kulenin daha küçük bir modül altındaki üs davranışından yeniden kurulabilmesidir.
Şöyle yazalım:
$$m = 2^s q, \qquad q \text{ tek}.$$
Yeterince yüksek kulede dıştaki terim \(2^E\) biçimindedir ve \(E\) değeri \(s\)'den çok büyüktür. Dolayısıyla kalıntı otomatik olarak \(2^s\) ile bölünür:
$$T(m) \equiv 0 \pmod{2^s}.$$
Bu nedenle kalıntıyı
$$T(m) \equiv 2^s u \pmod{m}$$
şeklinde yazabiliriz. Burada \(u\), \(q\) modunda bir sınıftır. Problem artık bu tek-parça katsayısı \(u\)'yu bulmaya indirgenmiştir.
\(q\) tek olduğundan \(\gcd(2,q)=1\) ve Euler teoremi geçerlidir:
$$2^{k+\varphi(q)} \equiv 2^k \pmod{q}.$$
Yani üs yalnızca \(\varphi(q)\) modunda önemlidir. Fakat bu üs de yine çok yüksek bir 2 kulesidir; dolayısıyla \(\varphi(q)\) modundaki kararlı kalıntısı tam olarak \(T(\varphi(q))\) olur. Bu yüzden \(q\) modunda
$$T(m) \equiv 2^{T(\varphi(q))} \pmod{q}$$
yazabiliriz. \(T(m) \equiv 2^s u\) yerine koyunca
$$2^s u \equiv 2^{T(\varphi(q))} \pmod{q}$$
elde edilir.
2 sayısı tek olan \(q\) modunda terslenebilir olduğundan \(2^s\) ile bölebiliriz:
$$u \equiv 2^{T(\varphi(q)) - s} \pmod{q}.$$
Eğer \(T(\varphi(q)) \ge s\) ise bu sıradan bir modüler üs alma işlemidir. Eğer \(T(\varphi(q)) \lt s\) ise üs negatif olur ve bunu
$$2^{-r} \equiv (2^{-1})^r \pmod{q}$$
şeklinde yorumlarız. Bu nedenle implementasyon, düzeltilmiş üs negatif olduğunda tek modül üzerinde 2'nin modüler tersini açıkça hesaplar.
\(u\) bulunduğunda kararlı kule değeri doğrudan
$$T(m) \equiv 2^s u \pmod{m}$$
olur. Saf \(2\) kuvvetleri için \(q=1\) olduğundan cevap hemen \(T(2^s)=0\) gelir. Diğer durumlarda rekürsiyon daha küçük olan \(\varphi(q)\) modülüne iner ve hızla temel duruma ulaşır:
$$T(1)=0.$$
\(m = 40 = 2^3 \cdot 5\) alalım. Burada \(s=3\), \(q=5\) ve
$$\varphi(q) = \varphi(5) = 4.$$
\(4\) bir \(2\) kuvveti olduğundan yeterince yüksek kule \(4\) ile bölünür; yani
$$T(4)=0.$$
Böylece
$$u \equiv 2^{T(4)-3} = 2^{-3} \pmod{5}$$
olur. \(2\)'nin \(5\) modundaki tersi \(3\) olduğundan
$$u \equiv 3^3 \equiv 27 \equiv 2 \pmod{5}.$$
Sonuç olarak
$$T(40) \equiv 2^3 \cdot 2 = 16 \pmod{40}.$$
Doğrudan kontrol de sabit nokta özelliğini doğrular:
$$2^{16} = 65536 \equiv 16 \pmod{40}.$$
C++, Python ve Java implementasyonları aynı rekürsiyonu izler. Phi zincirinde görülen her modül için kararlı kalıntı belleğe alınır ve başlangıç noktası olarak \(T(1)=0\) kullanılır. Güncel modül için önce bütün \(2\) çarpanları ayrılır, tek kısım \(q\) bulunur, \(q\) çarpanlara ayrılarak \(\varphi(q)\) hesaplanır, ardından \(T(\varphi(q))\) için rekürsif çağrı yapılır ve son olarak üs, çıkarılan \(2\) çarpanlarının sayısı kadar düzeltilir.
Tek-parça katkısı daha sonra modüler 2 üssü olarak hesaplanır. Düzeltilmiş üs negatifse, implementasyon önce genişletilmiş Öklid algoritması ile \(q\) modunda 2'nin modüler tersini bulur ve sonra bu tersi gerekli pozitif kuvvete yükseltir. En sonda \(2^s\) katsayısı geri eklenir, sonuç ilk modül altında indirgenir ve \(10^{15}\) için tepe çağrısından sonra \(10^{15}\) modunda \(3\) çıkarılır.
\(m_0 = m\) olsun ve her seviyede \(m_i = 2^{s_i} q_i\) biçiminde, \(q_i\) tek olacak şekilde yazalım. Rekürsiyon \(m_{i+1} = \varphi(q_i)\) modülüne geçerek 1'e kadar iner. Derinlik bu zincirin uzunluğudur. Her seviyede doğrudan implementasyon \(\varphi(q_i)\) hesabı için \(\sqrt{q_i}\)'ye kadar deneme bölmesi yapar ve ayrıca \(O(\log q_i)\) modüler çarpım maliyetli bir üs alma uygular. Dolayısıyla çalışma süresi
$$O\left(\sum_i \sqrt{q_i} + \sum_i \log q_i\right)$$
olur. Bellek tarafında ise memo tablosu zincirdeki her değer için tek bir kalıntı tuttuğundan kullanım \(O(k)\)'dir; burada \(k\) zincir uzunluğudur. Gerçek hedef modülde zincir çok hızlı küçüldüğü için pratik çalışma süresi düşüktür.
Las implementaciones calculan al final el residuo estabilizado de la torre \(2, 2^2, 2^{2^2}, \dots\) módulo \(10^{15}\), y después publican ese residuo desplazado en \(3\):
$$T(10^{15}) - 3 \pmod{10^{15}}.$$
Aquí \(T(m)\) representa el residuo final de una torre de doses suficientemente alta módulo \(m\). La dificultad central es que las potencias de 2 se comportan de manera distinta en la parte impar del módulo y en su parte potencia de 2, así que el método separa ambos componentes y los trata por separado.
Definimos la torre finita por \(a_1 = 2\) y \(a_{n+1} = 2^{a_n}\). Para cada módulo \(m\), los residuos \(a_n \bmod m\) terminan estabilizándose cuando \(n\) es grande; llamemos \(T(m)\) a ese residuo estable. Las implementaciones calculan \(T(m)\) descendiendo por la cadena de Euler sobre la parte impar del módulo.
Cuando los residuos ya se estabilizaron, una potenciación más produce la misma clase otra vez, de modo que
$$T(m) \equiv 2^{T(m)} \pmod{m}.$$
La identidad no se usa para buscar un punto fijo por fuerza bruta. Lo que aporta es una forma de reconstruir una torre muy alta a partir del comportamiento de su exponente bajo un módulo más pequeño.
Escribimos
$$m = 2^s q, \qquad q \text{ impar}.$$
En una torre suficientemente alta, el término exterior es \(2^E\) con un exponente \(E\) mucho mayor que \(s\), así que el residuo queda automáticamente dividido por \(2^s\):
$$T(m) \equiv 0 \pmod{2^s}.$$
Por lo tanto el residuo puede escribirse como
$$T(m) \equiv 2^s u \pmod{m}$$
para cierta clase \(u \pmod{q}\). El problema pasa a ser determinar ese factor correspondiente a la parte impar.
Como \(q\) es impar, \(\gcd(2,q)=1\), y podemos usar el teorema de Euler:
$$2^{k+\varphi(q)} \equiv 2^k \pmod{q}.$$
Eso significa que el exponente solo importa módulo \(\varphi(q)\). Pero ese exponente es otra vez una torre muy alta de doses, así que su residuo estable módulo \(\varphi(q)\) es justamente \(T(\varphi(q))\). En consecuencia, módulo \(q\),
$$T(m) \equiv 2^{T(\varphi(q))} \pmod{q}.$$
Al sustituir \(T(m) \equiv 2^s u\), obtenemos
$$2^s u \equiv 2^{T(\varphi(q))} \pmod{q}.$$
Puesto que 2 es invertible módulo el número impar \(q\), podemos dividir por \(2^s\):
$$u \equiv 2^{T(\varphi(q)) - s} \pmod{q}.$$
Si \(T(\varphi(q)) \ge s\), se trata de una potencia modular ordinaria. Si \(T(\varphi(q)) \lt s\), el exponente es negativo, y entonces interpretamos
$$2^{-r} \equiv (2^{-1})^r \pmod{q}.$$
Por eso las implementaciones calculan explícitamente el inverso modular de 2 sobre el módulo impar cuando el exponente corregido resulta negativo.
Una vez conocido \(u\), el valor estabilizado de la torre es
$$T(m) \equiv 2^s u \pmod{m}.$$
Para potencias puras de 2 se tiene \(q=1\), de modo que inmediatamente \(T(2^s)=0\). En los demás casos la recursión continúa con el módulo estrictamente menor \(\varphi(q)\) y alcanza con rapidez el caso base
$$T(1)=0.$$
Tomemos \(m = 40 = 2^3 \cdot 5\). Entonces \(s=3\), \(q=5\), y
$$\varphi(q) = \varphi(5) = 4.$$
Como \(4\) es una potencia de 2, una torre suficientemente alta es divisible por \(4\), así que
$$T(4)=0.$$
Por lo tanto
$$u \equiv 2^{T(4)-3} = 2^{-3} \pmod{5}.$$
El inverso de \(2\) módulo \(5\) es \(3\), luego
$$u \equiv 3^3 \equiv 27 \equiv 2 \pmod{5}.$$
En consecuencia,
$$T(40) \equiv 2^3 \cdot 2 = 16 \pmod{40}.$$
Una comprobación directa confirma la relación de punto fijo:
$$2^{16} = 65536 \equiv 16 \pmod{40}.$$
Las implementaciones en C++, Python y Java siguen la misma recursión. Guardan en memoria el residuo estabilizado de cada módulo que aparece en la cadena de la función phi, partiendo del valor base \(T(1)=0\). Para el módulo actual eliminan todos los factores de 2, obtienen la parte impar \(q\), factorizan \(q\) para calcular \(\varphi(q)\), llaman recursivamente para obtener \(T(\varphi(q))\) y corrigen el exponente restando el número de factores de 2 que se habían retirado.
Después calculan la contribución de la parte impar como una potencia modular de 2. Si el exponente corregido es negativo, la implementación obtiene primero el inverso modular de 2 módulo \(q\) mediante el algoritmo extendido de Euclides y luego eleva ese inverso a la potencia positiva necesaria. Al final vuelve a insertar el factor \(2^s\), reduce módulo el valor original y, tras la llamada superior para \(10^{15}\), resta \(3\) módulo \(10^{15}\).
Sea \(m_0 = m\), y en el nivel \(i\) escribamos \(m_i = 2^{s_i} q_i\) con \(q_i\) impar. La recursión avanza a \(m_{i+1} = \varphi(q_i)\) hasta llegar a 1. La profundidad es, por tanto, la longitud de esa cadena. En cada nivel, la implementación directa calcula \(\varphi(q_i)\) por división de prueba hasta \(\sqrt{q_i}\), y realiza una exponenciación modular con costo \(O(\log q_i)\) multiplicaciones modulares. Por ello, el tiempo total es
$$O\left(\sum_i \sqrt{q_i} + \sum_i \log q_i\right),$$
mientras que la tabla de memoización guarda un solo residuo por valor de la cadena, de modo que el uso de memoria es \(O(k)\), donde \(k\) es la longitud de la cadena. Para el módulo objetivo real la cadena decrece muy rápido, así que el tiempo práctico es pequeño.
这些实现最终计算的是幂塔 \(2, 2^2, 2^{2^2}, \dots\) 在模 \(10^{15}\) 下的稳定剩余类，然后再把该结果减去 \(3\)：
$$T(10^{15}) - 3 \pmod{10^{15}}.$$
这里 \(T(m)\) 表示足够高的 2 幂塔在模 \(m\) 下最终稳定下来的值。真正的难点在于：2 的幂在模数的奇数部分上可以利用欧拉函数降幂，而在 \(2\) 的幂因子部分上则表现为最终必然被高次 \(2\) 整除，因此必须把这两部分拆开处理。
先定义有限幂塔：\(a_1 = 2\)，\(a_{n+1} = 2^{a_n}\)。对每个模数 \(m\)，当 \(n\) 足够大时，\(a_n \bmod m\) 会稳定下来；把这个稳定值记为 \(T(m)\)。实现的核心就是沿着模数奇数部分的欧拉函数链递归地求出 \(T(m)\)。
一旦余数序列已经稳定，再往上多加一层指数不会改变最终的剩余类，所以极限值满足
$$T(m) \equiv 2^{T(m)} \pmod{m}.$$
这并不是说程序去直接求解这个固定点方程，而是说明“很高的幂塔”可以通过更小模数下的指数信息来重建。
写成
$$m = 2^s q, \qquad q \text{ 为奇数}.$$
对于足够高的幂塔，最外层一定形如 \(2^E\)，而指数 \(E\) 会远大于 \(s\)。因此最终结果必然被 \(2^s\) 整除，也就是
$$T(m) \equiv 0 \pmod{2^s}.$$
于是可以把结果写成
$$T(m) \equiv 2^s u \pmod{m},$$
其中 \(u\) 是模 \(q\) 的某个剩余类。这样问题就被压缩成“如何求出奇数部分对应的因子 \(u\)”。
因为 \(q\) 为奇数，所以 \(\gcd(2,q)=1\)，可以使用欧拉定理：
$$2^{k+\varphi(q)} \equiv 2^k \pmod{q}.$$
这说明在模 \(q\) 下，指数只需要知道模 \(\varphi(q)\) 的值即可。而最外层 2 上面的那个指数，本身又是一个很高的 2 幂塔，所以它在模 \(\varphi(q)\) 下的稳定值正是 \(T(\varphi(q))\)。因此在模 \(q\) 下有
$$T(m) \equiv 2^{T(\varphi(q))} \pmod{q}.$$
再代入 \(T(m) \equiv 2^s u\)，得到
$$2^s u \equiv 2^{T(\varphi(q))} \pmod{q}.$$
由于 2 在奇数模 \(q\) 下可逆，可以把上式除以 \(2^s\)：
$$u \equiv 2^{T(\varphi(q)) - s} \pmod{q}.$$
如果 \(T(\varphi(q)) \ge s\)，这只是普通的模幂运算。如果 \(T(\varphi(q)) \lt s\)，指数就会变成负数，此时应解释为
$$2^{-r} \equiv (2^{-1})^r \pmod{q}.$$
这正是实现里必须显式计算“模 \(q\) 下 2 的乘法逆元”的原因：只有这样才能正确处理修正后指数为负的情况。
一旦 \(u\) 已知，稳定幂塔值就重新写成
$$T(m) \equiv 2^s u \pmod{m}.$$
如果模数本身就是纯粹的 \(2\) 的幂，那么 \(q=1\)，答案立刻就是 \(T(2^s)=0\)。否则递归继续进入严格更小的模数 \(\varphi(q)\)，并很快到达基例
$$T(1)=0.$$
取 \(m = 40 = 2^3 \cdot 5\)。此时 \(s=3\)、\(q=5\)，并且
$$\varphi(q) = \varphi(5) = 4.$$
因为 \(4\) 是 \(2\) 的幂，所以足够高的幂塔一定被 \(4\) 整除，从而
$$T(4)=0.$$
于是
$$u \equiv 2^{T(4)-3} = 2^{-3} \pmod{5}.$$
而 \(2\) 在模 \(5\) 下的逆元是 \(3\)，因此
$$u \equiv 3^3 \equiv 27 \equiv 2 \pmod{5}.$$
所以
$$T(40) \equiv 2^3 \cdot 2 = 16 \pmod{40}.$$
直接验算可见固定点关系确实成立：
$$2^{16} = 65536 \equiv 16 \pmod{40}.$$
C++、Python 和 Java 三个实现遵循完全相同的递归结构。它们会对欧拉函数链上出现过的每个模数缓存对应的稳定值，起点是基例 \(T(1)=0\)。对当前模数，程序先剥离所有的 2 因子，得到奇数部分 \(q\)，再通过分解 \(q\) 来计算 \(\varphi(q)\)，递归求出 \(T(\varphi(q))\)，然后把指数减去剥离出去的 2 因子个数。
接下来，奇数部分的贡献通过“2 的模幂”来求。如果修正后的指数是负数，实现就先用扩展欧几里得算法求出 2 在模 \(q\) 下的逆元，再把该逆元提升到相应的正幂。最后把 \(2^s\) 因子乘回去，在原模数下取模；在顶层模数 \(10^{15}\) 上得到稳定值以后，再额外减去 \(3\) 并对 \(10^{15}\) 取模。
设 \(m_0 = m\)，并在第 \(i\) 层写成 \(m_i = 2^{s_i} q_i\)，其中 \(q_i\) 为奇数。递归随后进入 \(m_{i+1} = \varphi(q_i)\)，直到到达 1 为止。递归深度就是这条链的长度。对每一层，直接实现都会通过试除到 \(\sqrt{q_i}\) 来计算 \(\varphi(q_i)\)，并执行一次模幂运算，代价为 \(O(\log q_i)\) 次模乘。因此总时间复杂度可写为
$$O\left(\sum_i \sqrt{q_i} + \sum_i \log q_i\right),$$
而缓存表只为链上的每个模数存一个稳定值，所以空间复杂度是 \(O(k)\)，其中 \(k\) 是链长。对于本题目标模数，这条链缩小得很快，因此实际运行时间很小。
Реализации в итоге вычисляют стабилизированный остаток башни \(2, 2^2, 2^{2^2}, \dots\) по модулю \(10^{15}\), а затем вычитают из него \(3\):
$$T(10^{15}) - 3 \pmod{10^{15}}.$$
Здесь \(T(m)\) означает конечный остаток достаточно высокой башни степеней двойки по модулю \(m\). Главная трудность в том, что степени двойки по-разному ведут себя на нечётной части модуля и на его степени двойки, поэтому решение сначала разделяет эти два случая, а потом аккуратно собирает ответ.
Определим конечную башню как \(a_1 = 2\) и \(a_{n+1} = 2^{a_n}\). Для каждого модуля \(m\) остатки \(a_n \bmod m\) при больших \(n\) стабилизируются; этот устойчивый остаток обозначим через \(T(m)\). Реализации вычисляют \(T(m)\) рекурсией по функции Эйлера, двигаясь по нечётной части модуля.
После стабилизации остатков ещё одно возведение в степень возвращает тот же самый класс, поэтому выполняется
$$T(m) \equiv 2^{T(m)} \pmod{m}.$$
Эта формула нужна не для прямого перебора фиксированной точки, а для понимания того, как высокий степенной столб восстанавливается из поведения показателя по меньшему модулю.
Пусть
$$m = 2^s q, \qquad q \text{ нечётно}.$$
Для достаточно высокой башни внешний член имеет вид \(2^E\), причём показатель \(E\) намного больше \(s\). Значит, итоговый остаток автоматически делится на \(2^s\):
$$T(m) \equiv 0 \pmod{2^s}.$$
Следовательно, можно записать
$$T(m) \equiv 2^s u \pmod{m}$$
для некоторого класса \(u \pmod{q}\). Вся задача сводится к нахождению этого нечётного множителя \(u\).
Так как \(q\) нечётно, \(\gcd(2,q)=1\), и можно применить теорему Эйлера:
$$2^{k+\varphi(q)} \equiv 2^k \pmod{q}.$$
Значит, показатель важен только по модулю \(\varphi(q)\). Но этот показатель сам является очень высокой башней двоек, поэтому его устойчивый остаток по модулю \(\varphi(q)\) равен \(T(\varphi(q))\). Следовательно, по модулю \(q\)
$$T(m) \equiv 2^{T(\varphi(q))} \pmod{q}.$$
Подставляя \(T(m) \equiv 2^s u\), получаем
$$2^s u \equiv 2^{T(\varphi(q))} \pmod{q}.$$
Поскольку 2 обратима по нечётному модулю \(q\), можно разделить на \(2^s\):
$$u \equiv 2^{T(\varphi(q)) - s} \pmod{q}.$$
Если \(T(\varphi(q)) \ge s\), это обычная модульная степень. Если же \(T(\varphi(q)) \lt s\), показатель становится отрицательным, и тогда надо понимать
$$2^{-r} \equiv (2^{-1})^r \pmod{q}.$$
Именно поэтому реализации явно вычисляют обратный элемент к 2 по модулю \(q\), когда скорректированный показатель отрицателен.
Когда \(u\) найден, устойчивое значение башни равно
$$T(m) \equiv 2^s u \pmod{m}.$$
Для чистых степеней двойки имеем \(q=1\), поэтому сразу \(T(2^s)=0\). В остальных случаях рекурсия переходит к строго меньшему модулю \(\varphi(q)\) и быстро доходит до базового случая
$$T(1)=0.$$
Возьмём \(m = 40 = 2^3 \cdot 5\). Тогда \(s=3\), \(q=5\), и
$$\varphi(q) = \varphi(5) = 4.$$
Поскольку \(4\) является степенью двойки, достаточно высокая башня делится на \(4\), то есть
$$T(4)=0.$$
Отсюда
$$u \equiv 2^{T(4)-3} = 2^{-3} \pmod{5}.$$
Обратный элемент к \(2\) по модулю \(5\) равен \(3\), следовательно
$$u \equiv 3^3 \equiv 27 \equiv 2 \pmod{5}.$$
Значит,
$$T(40) \equiv 2^3 \cdot 2 = 16 \pmod{40}.$$
Прямая проверка подтверждает фиксированную точку:
$$2^{16} = 65536 \equiv 16 \pmod{40}.$$
Реализации на C++, Python и Java используют одну и ту же рекурсию. Они запоминают устойчивый остаток для каждого модуля, встреченного на цепочке функции Эйлера, начиная с базового значения \(T(1)=0\). Для текущего модуля программа сначала убирает все множители 2, получает нечётную часть \(q\), раскладывает \(q\) на множители для вычисления \(\varphi(q)\), рекурсивно находит \(T(\varphi(q))\), а затем корректирует показатель, вычитая число снятых двоек.
После этого вклад нечётной части считается как модульная степень двойки. Если исправленный показатель отрицателен, реализация сперва находит обратный элемент к 2 по модулю \(q\) с помощью расширенного алгоритма Евклида, а затем возводит этот обратный элемент в нужную положительную степень. В конце фактор \(2^s\) возвращается обратно, результат берётся по исходному модулю, и после верхнего вызова для \(10^{15}\) дополнительно вычитается \(3\) по модулю \(10^{15}\).
Пусть \(m_0 = m\), и на уровне \(i\) имеем разложение \(m_i = 2^{s_i} q_i\), где \(q_i\) нечётно. Рекурсия переходит к \(m_{i+1} = \varphi(q_i)\), пока не дойдёт до 1. Глубина рекурсии равна длине этой цепочки. На каждом уровне прямая реализация вычисляет \(\varphi(q_i)\) перебором делителей до \(\sqrt{q_i}\) и выполняет одну модульную экспоненту стоимостью \(O(\log q_i)\) модульных умножений. Следовательно, общее время равно
$$O\left(\sum_i \sqrt{q_i} + \sum_i \log q_i\right),$$
а таблица запоминания хранит только один остаток на каждое значение в цепочке, так что память составляет \(O(k)\), где \(k\) - длина цепочки. Для реального целевого модуля эта цепочка убывает очень быстро, поэтому практическое время работы мало.
تحسب هذه الحلول في النهاية الباقي المستقر للبرج \(2, 2^2, 2^{2^2}, \dots\) تحت المعيار \(10^{15}\)، ثم تُرجع هذا الباقي بعد طرح \(3\):
$$T(10^{15}) - 3 \pmod{10^{15}}.$$
الرمز \(T(m)\) يعني الباقي النهائي لبرج طويل بما يكفي من القوى ذات الأساس 2 عند الأخذ بترديد \(m\). الصعوبة الأساسية هي أن قوى 2 تتصرف بطريقة مختلفة على الجزء الفردي من المعيار مقارنة بجزء قوة الاثنين، لذلك يفصل الحل بين الجزأين ويعالجهما بأسلوبين متكاملين.
نعرّف البرج المنتهي بالعلاقة \(a_1 = 2\) و \(a_{n+1} = 2^{a_n}\). ولكل معيار \(m\)، فإن البواقي \(a_n \bmod m\) تستقر عندما يكبر \(n\)، ولنسَمِّ هذه القيمة المستقرة \(T(m)\). تقوم الحلول بحساب \(T(m)\) عن طريق عودية تنزل على سلسلة دالة أويلر المرتبطة بالجزء الفردي من المعيار.
بعد أن تستقر البواقي، فإن إضافة طبقة أسية جديدة لا تغيّر الفئة النهائية، ولذلك تحقق القيمة المستقرة
$$T(m) \equiv 2^{T(m)} \pmod{m}.$$
هذه العلاقة لا تُستخدم كحل مباشر لمعادلة نقطة ثابتة، بل كطريقة لفهم كيف يمكن إعادة بناء برج عال جداً من سلوك الأس تحت معيار أصغر.
نكتب
$$m = 2^s q.$$
حيث \(q\) عدد فردي.
عندما يكون البرج عالياً بما يكفي، فإن الحد الخارجي يكون على صورة \(2^E\) مع أس \(E\) أكبر بكثير من \(s\)، ولذلك يكون الناتج قابلاً للقسمة على \(2^s\) تلقائياً:
$$T(m) \equiv 0 \pmod{2^s}.$$
ومن ثم يمكن كتابة الباقي على الصورة
$$T(m) \equiv 2^s u \pmod{m},$$
حيث \(u\) فئة باقية بترديد \(q\). وهكذا ينحصر العمل في إيجاد هذا العامل المرتبط بالجزء الفردي.
بما أن \(q\) فردي، فإن \(\gcd(2,q)=1\)، ولذلك تنطبق مبرهنة أويلر:
$$2^{k+\varphi(q)} \equiv 2^k \pmod{q}.$$
هذا يعني أن الأس لا يهم إلا بترديد \(\varphi(q)\). لكن هذا الأس نفسه هو أيضاً برج عال من القوى ذات الأساس 2، ومن ثم فإن قيمته المستقرة بترديد \(\varphi(q)\) هي بالضبط \(T(\varphi(q))\). لذلك نحصل بترديد \(q\) على
$$T(m) \equiv 2^{T(\varphi(q))} \pmod{q}.$$
وبالتعويض عن \(T(m) \equiv 2^s u\) ينتج
$$2^s u \equiv 2^{T(\varphi(q))} \pmod{q}.$$
لأن 2 قابلة للعكس بترديد العدد الفردي \(q\)، يمكن القسمة على \(2^s\):
$$u \equiv 2^{T(\varphi(q)) - s} \pmod{q}.$$
إذا كان \(T(\varphi(q)) \ge s\) فهذه قوة معيارية عادية. أما إذا كان \(T(\varphi(q)) \lt s\)، فإن الأس يصبح سالباً، ونفسره على أنه
$$2^{-r} \equiv (2^{-1})^r \pmod{q}.$$
ولهذا السبب بالضبط تحسب الحلول معكوس 2 المعياري على الجزء الفردي عندما يكون الأس المصحح سالباً.
بعد معرفة \(u\)، تصبح قيمة البرج المستقرة
$$T(m) \equiv 2^s u \pmod{m}.$$
إذا كان المعيار قوة خالصة للعدد 2، فلدينا \(q=1\)، وعندها يكون الجواب مباشرة \(T(2^s)=0\). وفي غير ذلك تستمر العودية مع المعيار الأصغر تماماً \(\varphi(q)\) حتى تصل سريعاً إلى الحالة الأساسية
$$T(1)=0.$$
لنأخذ \(m = 40 = 2^3 \cdot 5\). عندئذٍ \(s=3\) و \(q=5\) و
$$\varphi(q) = \varphi(5) = 4.$$
وبما أن \(4\) قوة للعدد 2، فإن برجاً عالياً بما يكفي يكون قابلاً للقسمة على \(4\)، وبالتالي
$$T(4)=0.$$
إذن
$$u \equiv 2^{T(4)-3} = 2^{-3} \pmod{5}.$$
ومعكوس \(2\) بترديد \(5\) هو \(3\)، لذا
$$u \equiv 3^3 \equiv 27 \equiv 2 \pmod{5}.$$
ومن ثم
$$T(40) \equiv 2^3 \cdot 2 = 16 \pmod{40}.$$
والتحقق المباشر يؤكد علاقة النقطة الثابتة:
$$2^{16} = 65536 \equiv 16 \pmod{40}.$$
تتبع تطبيقات C++ وPython وJava العودية نفسها تماماً. فهي تحتفظ في الذاكرة بالقيمة المستقرة لكل معيار يظهر على سلسلة دالة أويلر، بدءاً من القيمة الأساسية \(T(1)=0\). عند معالجة معيار معيّن، تزيل جميع عوامل 2 أولاً، ثم تحدد الجزء الفردي \(q\)، وتفككه لحساب \(\varphi(q)\)، ثم تستدعي العودية لإيجاد \(T(\varphi(q))\)، وبعد ذلك تُصحح الأس بطرح عدد عوامل 2 التي أُزيلت.
بعد ذلك يُحسب أثر الجزء الفردي على صورة قوة معيارية للعدد 2. وإذا كان الأس المصحح سالباً، فإن التنفيذ يحسب أولاً معكوس 2 بترديد \(q\) باستخدام خوارزمية إقليدس الموسعة، ثم يرفع هذا المعكوس إلى القوة الموجبة المطلوبة. وفي النهاية يعيد إدخال العامل \(2^s\)، ويأخذ الناتج بترديد المعيار الأصلي، وبعد الاستدعاء الأعلى عند \(10^{15}\) يطرح \(3\) بترديد \(10^{15}\).
لنكتب \(m_0 = m\)، وعلى المستوى \(i\) نعبّر عنه بالشكل \(m_i = 2^{s_i} q_i\) حيث \(q_i\) فردي. بعد ذلك تنتقل العودية إلى \(m_{i+1} = \varphi(q_i)\) حتى تصل إلى 1. عمق العودية هو طول هذه السلسلة. في كل مستوى، يحسب التنفيذ المباشر \(\varphi(q_i)\) بالقسمة التجريبية حتى \(\sqrt{q_i}\)، وينفذ أيضاً عملية أس معيارية بتكلفة \(O(\log q_i)\) من الضربات المعيارية. لذلك يكون الزمن الكلي
$$O\left(\sum_i \sqrt{q_i} + \sum_i \log q_i\right),$$
بينما يخزّن جدول الحفظ قيمة واحدة فقط لكل عنصر في السلسلة، ولذلك يكون استهلاك الذاكرة \(O(k)\)، حيث \(k\) هو طول السلسلة. بالنسبة إلى المعيار الفعلي في هذه المسألة، تتناقص السلسلة بسرعة كبيرة، ولذلك يكون الزمن العملي صغيراً.