Problem 188 asks for the last eight digits of the tetration
$$1777 \uparrow\uparrow 1855 = 1777^{1777^{.^{.^{1777}}}}$$
where the exponent tower has height \(1855\). Writing down the exponent is hopeless: even the third level is already astronomically large. The task is therefore not to evaluate the tower itself, but to compute its residue modulo \(10^8\).
The implementations solve the problem by replacing one enormous exponent tower with a short chain of smaller modular subproblems. The crucial tool is Euler's theorem, but for this specific input the modulus \(10^8\) has such a simple prime-power structure that the entire reduction can be written very explicitly.
Let
$$T_h = 1777 \uparrow\uparrow h,$$
and let \(R(h,m)\) denote \(T_h \bmod m\). Then
$$R(1,m)=1777 \bmod m,$$
and for \(h \ge 2\),
$$T_h = 1777^{T_{h-1}}.$$
If \(\gcd(1777,m)=1\), Euler's theorem gives
$$1777^x \equiv 1777^{\,x \bmod \varphi(m)} \pmod m,$$
so only the exponent modulo \(\varphi(m)\) is needed. That turns the tower into the recurrence
$$R(h,m)=1777^{\,R(h-1,\varphi(m))} \bmod m,$$
provided the modulus at that level is coprime to \(1777\). This is the core recurrence used by all three implementations.
The modulus is
$$10^8 = 2^8 \cdot 5^8.$$
For numbers of the form \(2^a5^b\) with \(a,b \ge 1\), Euler's totient function is
$$\varphi(2^a5^b)=2^a5^b\left(1-\frac12\right)\left(1-\frac15\right)=2^{a+1}5^{b-1}.$$
Starting from \(10^8\), repeated totients therefore give the explicit chain
$$100000000 \to 40000000 \to 16000000 \to 6400000 \to 2560000 \to 1024000 \to 409600 \to 163840 \to 65536 \to 32768 \to \cdots \to 1.$$
Two facts matter here. First, after eight totients the factor \(5^b\) disappears and only powers of \(2\) remain. Second, after only 24 totient steps the modulus has already fallen to \(1\). So a tower of height \(1855\) does not create \(1855\) genuinely different subproblems; only the first 25 modulus levels matter.
The base \(1777\) is divisible by neither \(2\) nor \(5\). Every modulus in the chain above is of the form \(2^a5^b\), so
$$\gcd(1777,m_i)=1$$
for every modulus \(m_i\) that appears during the recursion. That means the clean coprime recurrence applies at every level of the actual Project Euler input:
$$R(1855,10^8)=1777^{\,R(1854,40000000)} \bmod 10^8,$$
$$R(1854,40000000)=1777^{\,R(1853,16000000)} \bmod 40000000,$$
and so on, until the modulus becomes \(1\), at which point the recursive value is automatically \(0\). The algorithm never needs the full exponent \(T_{h-1}\); it only needs its residue modulo the next totient.
The checkpoint used by the implementations is small enough to show the mechanism completely. Since
$$100 \to \varphi(100)=40 \to \varphi(40)=16,$$
we compute from the top of the chain downward:
$$3 \uparrow\uparrow 1 \equiv 3 \pmod{16},$$
$$3 \uparrow\uparrow 2 = 3^3 \equiv 27 \pmod{40},$$
$$3 \uparrow\uparrow 3 = 3^{27} \equiv 87 \pmod{100}.$$
This is exactly the same recursion as the real problem, just with much smaller numbers. The large Euler 188 tower is solved by repeating the same descent along the totient chain of \(10^8\).
The implementation first needs two standard primitives. One computes \(\varphi(m)\) by factoring the current modulus with trial division and applying the product formula for Euler's totient. The other computes \(a^e \bmod m\) by binary modular exponentiation, so the cost grows only logarithmically with the exponent size instead of linearly.
The C++, Python, and Java implementations then evaluate the tetration residue recursively. If the modulus is \(1\), the residue is immediately \(0\). If the height is \(1\), the result is simply \(1777 \bmod m\). Otherwise the code descends once to modulus \(\varphi(m)\), obtains the smaller residue needed for the exponent, and raises \(1777\) to that exponent modulo the current modulus.
The implementations also include a standard safeguard for non-coprime cases: after the recursive call, they add one totient period before modular exponentiation whenever the base and modulus are not coprime. That branch makes the routine more generally usable, but for Problem 188 it never fires, because every modulus encountered is still coprime to \(1777\).
The three versions differ only in low-level mechanics. The Python implementation uses the language's built-in modular power with an explicit modulus argument. The Java implementation delegates modular exponentiation to its arbitrary-precision integer library. The C++ implementation performs modular multiplication in a wider integer type before reducing modulo \(m\), which keeps the routine safe even if larger inputs are supplied from the command line. Mathematically, however, all three versions execute the same totient-chain recursion.
If \(m_0=10^8\) and \(m_{i+1}=\varphi(m_i)\), let \(L\) be the first index with \(m_L=1\). For this problem, \(L=24\), so the recursion has only about two dozen meaningful levels, not \(1855\). Memory usage is therefore \(O(L)\), which is tiny in practice.
At level \(i\), the code factors \(m_i\) by trial division to obtain \(\varphi(m_i)\), then performs one modular exponentiation whose cost is \(O(\log m_i)\) modular multiplications because the exponent is already reduced modulo \(m_{i+1}\). A clean way to summarize the running time is
$$O\!\left(\sum_{i=0}^{L-1}\bigl(\sqrt{m_i}+\log m_i\bigr)\right).$$
Since the moduli collapse rapidly from \(10^8\) to \(1\), this is easily fast enough for the given input.
Gesucht sind die letzten acht Ziffern der Tetration
$$1777 \uparrow\uparrow 1855 = 1777^{1777^{.^{.^{1777}}}}$$
mit Turmhöhe \(1855\). Den Exponententurm direkt auszuwerten ist unmöglich; schon nach wenigen Ebenen sind die Zahlen unvorstellbar groß. Man muss also nicht den Turm selbst berechnen, sondern seinen Rest modulo \(10^8\).
Die Lösung ersetzt einen gigantischen Exponententurm durch eine kurze Kette kleinerer Modulprobleme. Das zentrale Werkzeug ist der Satz von Euler. Für diese konkrete Aufgabe ist außerdem entscheidend, dass \(10^8\) eine sehr einfache Primfaktorzerlegung besitzt und sich die Totientenkette daher vollständig explizit beschreiben lässt.
Setze
$$T_h = 1777 \uparrow\uparrow h,$$
und bezeichne mit \(R(h,m)\) den Rest \(T_h \bmod m\). Dann gilt
$$R(1,m)=1777 \bmod m,$$
und für \(h \ge 2\)
$$T_h = 1777^{T_{h-1}}.$$
Falls \(\gcd(1777,m)=1\), folgt aus dem Satz von Euler
$$1777^x \equiv 1777^{\,x \bmod \varphi(m)} \pmod m,$$
also genügt der Exponent modulo \(\varphi(m)\). Damit entsteht die Rekursion
$$R(h,m)=1777^{\,R(h-1,\varphi(m))} \bmod m,$$
und genau diese Beziehung berechnen die Implementierungen.
Der Modulus ist
$$10^8 = 2^8 \cdot 5^8.$$
Für Zahlen der Form \(2^a5^b\) mit \(a,b \ge 1\) ist
$$\varphi(2^a5^b)=2^a5^b\left(1-\frac12\right)\left(1-\frac15\right)=2^{a+1}5^{b-1}.$$
Daraus ergibt sich sofort die explizite Kette
$$100000000 \to 40000000 \to 16000000 \to 6400000 \to 2560000 \to 1024000 \to 409600 \to 163840 \to 65536 \to 32768 \to \cdots \to 1.$$
Wichtig sind zwei Beobachtungen. Nach acht Anwendungen von \(\varphi\) verschwindet der Faktor \(5^b\), danach bleiben nur noch Zweierpotenzen übrig. Und schon nach 24 Totientenschritten ist der Modulus gleich \(1\). Obwohl der Turm Höhe \(1855\) besitzt, entstehen also nur 25 relevante Modulebenen.
Die Basis \(1777\) ist weder durch \(2\) noch durch \(5\) teilbar. Jeder Modulus in der obigen Kette hat die Form \(2^a5^b\). Also gilt für jede Rekursionsebene
$$\gcd(1777,m_i)=1.$$
Damit ist die saubere koprime Rekursion für die konkrete Euler-188-Eingabe überall anwendbar:
$$R(1855,10^8)=1777^{\,R(1854,40000000)} \bmod 10^8,$$
$$R(1854,40000000)=1777^{\,R(1853,16000000)} \bmod 40000000,$$
usw., bis der Modulus \(1\) erreicht ist. Ab diesem Punkt ist der rekursive Rest automatisch \(0\). Man braucht also niemals den vollen Exponenten \(T_{h-1}\), sondern nur seinen Rest modulo des nächsten Totientenwerts.
Der eingebaute Kontrollfall ist klein genug, um den Mechanismus vollständig zu zeigen. Es gilt
$$100 \to \varphi(100)=40 \to \varphi(40)=16.$$
Nun von unten nach oben:
$$3 \uparrow\uparrow 1 \equiv 3 \pmod{16},$$
$$3 \uparrow\uparrow 2 = 3^3 \equiv 27 \pmod{40},$$
$$3 \uparrow\uparrow 3 = 3^{27} \equiv 87 \pmod{100}.$$
Genau dieselbe Idee wird bei Problem 188 verwendet, nur mit der längeren Totientenkette von \(10^8\).
Zuerst werden zwei Standardbausteine benötigt. Der eine berechnet \(\varphi(m)\), indem der aktuelle Modulus per Trial Division faktorisiert und anschließend die Produktformel der Totientfunktion angewendet wird. Der andere berechnet \(a^e \bmod m\) mit binärer modularer Exponentiation, sodass die Laufzeit nur logarithmisch mit dem Exponenten wächst.
Die C++-, Python- und Java-Implementierungen werten den Rest der Tetration dann rekursiv aus. Ist der Modulus \(1\), wird sofort \(0\) zurückgegeben. Ist die Höhe \(1\), so ist das Ergebnis einfach \(1777 \bmod m\). Andernfalls steigt der Code genau eine Ebene in der Totientenkette ab, berechnet dort den kleineren Exponentenrest und potenziert anschließend \(1777\) modulo des aktuellen Modulus.
Zusätzlich enthalten die Implementierungen eine allgemeine Sicherheitskorrektur für den nicht-koprimen Fall: Wenn Basis und Modulus keinen ggT \(1\) haben, wird nach dem rekursiven Aufruf noch eine Totientenperiode zum Exponenten addiert. Für Problem 188 wird dieser Zweig allerdings nie benutzt, weil jeder auftretende Modulus zu \(1777\) teilerfremd bleibt.
Die drei Fassungen unterscheiden sich nur in der technischen Umsetzung. Python verwendet die eingebaute modulare Potenzfunktion mit explizitem Modulusargument. Java nutzt dafür seine Bibliothek für Ganzzahlen beliebiger Größe. C++ führt die modulare Multiplikation zunächst in einem breiteren Ganzzahltyp aus und reduziert erst danach modulo \(m\). Mathematisch berechnen jedoch alle drei Programme dieselbe Totientenrekursion.
Sei \(m_0=10^8\) und \(m_{i+1}=\varphi(m_i)\). Bezeichne mit \(L\) den ersten Index mit \(m_L=1\). In dieser Aufgabe ist \(L=24\), also hat die Rekursion nur rund zwei Dutzend sinnvolle Ebenen und nicht \(1855\). Der Speicherverbrauch ist deshalb \(O(L)\) und praktisch vernachlässigbar.
Auf Ebene \(i\) wird \(m_i\) per Trial Division faktorisiert, um \(\varphi(m_i)\) zu bestimmen, und danach eine modulare Potenzierung ausgeführt. Da der Exponent bereits modulo \(m_{i+1}\) reduziert ist, kostet diese Potenzierung \(O(\log m_i)\) modulare Multiplikationen. Eine passende Gesamtschätzung lautet
$$O\!\left(\sum_{i=0}^{L-1}\bigl(\sqrt{m_i}+\log m_i\bigr)\right).$$
Weil die Moduli extrem schnell von \(10^8\) auf \(1\) schrumpfen, ist das für die konkreten Eingaben problemlos schnell genug.
Problem 188, şu tetration ifadesinin son sekiz basamağını ister:
$$1777 \uparrow\uparrow 1855 = 1777^{1777^{.^{.^{1777}}}}.$$
Burada üs kulesinin yüksekliği \(1855\)'tir. Bu kuleyi doğrudan hesaplamak imkansızdır; daha üçüncü veya dördüncü seviyede sayılar fiziksel olarak yazılamayacak kadar büyür. Dolayısıyla amaç kuleyi açıkça üretmek değil, onu \(10^8\) modunda değerlendirmektir.
Çözüm, tek bir dev üs kulesini birbiriyle bağlantılı küçük modüler problemlere parçalar. Temel araç Euler teoremidir. Fakat bu problemde asıl avantaj, modülün \(10^8=2^8\cdot5^8\) biçiminde çok düzenli olmasıdır; bu sayede totient zinciri tamamen açık biçimde yazılabilir.
$$T_h = 1777 \uparrow\uparrow h$$
olsun ve \(R(h,m)\), \(T_h\)'nin \(m\) modundaki kalanı olsun. O zaman
$$R(1,m)=1777 \bmod m,$$
ve \(h \ge 2\) için
$$T_h = 1777^{T_{h-1}}.$$
Eğer \(\gcd(1777,m)=1\) ise Euler teoreminden
$$1777^x \equiv 1777^{\,x \bmod \varphi(m)} \pmod m$$
elde edilir. Yani tam üst değeri değil, yalnızca \(\varphi(m)\) modundaki kalanı gerekir. Böylece ana yineleme
$$R(h,m)=1777^{\,R(h-1,\varphi(m))} \bmod m$$
şekline iner. Üç çözümün de yaptığı hesap tam olarak budur.
Başlangıç modülü
$$10^8 = 2^8 \cdot 5^8$$
olduğundan, \(a,b \ge 1\) için
$$\varphi(2^a5^b)=2^a5^b\left(1-\frac12\right)\left(1-\frac15\right)=2^{a+1}5^{b-1}$$
formülünü kullanabiliriz. Bu da şu açık zinciri verir:
$$100000000 \to 40000000 \to 16000000 \to 6400000 \to 2560000 \to 1024000 \to 409600 \to 163840 \to 65536 \to 32768 \to \cdots \to 1.$$
Buradan iki önemli sonuç çıkar. Sekiz kez \(\varphi\) uygulandıktan sonra \(5\) çarpanı tamamen yok olur ve yalnızca \(2\)'nin kuvvetleri kalır. Ayrıca sadece 24 totient adımında modül \(1\)'e düşer. Bu yüzden yükseklik \(1855\) olsa bile gerçekten farklı olan alt problemlerin sayısı yalnızca 25 civarındadır.
\(1777\), ne \(2\)'ye ne de \(5\)'e bölünür. Zincirde ortaya çıkan her modül \(2^a5^b\) biçimindedir. Dolayısıyla her seviyede
$$\gcd(1777,m_i)=1$$
olur. Böylece gerçek Euler 188 girdisi için yineleme her adımda doğrudan geçerlidir:
$$R(1855,10^8)=1777^{\,R(1854,40000000)} \bmod 10^8,$$
$$R(1854,40000000)=1777^{\,R(1853,16000000)} \bmod 40000000,$$
ve zincir böyle devam eder. Modül \(1\) olduğunda özyineleme otomatik olarak \(0\) döndürür. Yani algoritma hiçbir aşamada \(T_{h-1}\)'in tamamını istemez; yalnızca bir sonraki totient modundaki kalanı yeterlidir.
Uygulamalardaki kontrol örneği yöntemi çok net gösterir. Önce totient zinciri:
$$100 \to \varphi(100)=40 \to \varphi(40)=16.$$
Sonra yukarıdan aşağı değil, küçük modülden büyük modüle doğru açarız:
$$3 \uparrow\uparrow 1 \equiv 3 \pmod{16},$$
$$3 \uparrow\uparrow 2 = 3^3 \equiv 27 \pmod{40},$$
$$3 \uparrow\uparrow 3 = 3^{27} \equiv 87 \pmod{100}.$$
Problem 188'de yapılan işlem de aynıdır; yalnızca kullanılan totient zinciri daha uzundur ve başlangıç modülü \(10^8\)'dir.
Önce iki standart bileşen gerekir. Birincisi, mevcut modülü asal çarpanlarına ayırarak \(\varphi(m)\) hesaplar. İkincisi, \(a^e \bmod m\) hesabını ikili üs alma ile yapar; böylece üs çok büyük olsa bile maliyet doğrusal değil logaritmik olur.
C++, Python ve Java uygulamaları daha sonra tetration kalanı için aynı özyinelemeyi uygular. Modül \(1\) ise sonuç hemen \(0\)'dır. Yükseklik \(1\) ise sonuç doğrudan \(1777 \bmod m\) olur. Aksi halde kod bir kez \(\varphi(m)\) modülüne iner, oradaki daha küçük üst kalanı hesaplar ve \(1777\)'yi bu üs ile mevcut modül altında kuvvetlendirir.
Uygulamalar ayrıca, taban ile modül aralarında asal değilse kullanılan genel bir güvenlik düzeltmesi de içerir: özyinelemeden dönen üs değerine bir adet totient periyodu eklenir. Bu ayrıntı yordamı daha genel hale getirir; fakat Problem 188'de hiçbir zaman devreye girmez, çünkü zincirdeki tüm modüller \(1777\) ile aralarında asaldır.
Fark yalnızca düşük seviyeli araçlardadır. Python sürümü yerleşik modüler üs alma işlemini açık bir modül argümanıyla kullanır. Java sürümü modüler üs alma işini keyfi büyüklükte tamsayılar için olan standart kütüphanesine bırakır. C++ sürümü ise modüler çarpımı daha geniş bir tamsayı türünde yapıp sonra mod alır. Matematiksel akış ise üçünde de aynı totient-zinciri özyinelemesidir.
\(m_0=10^8\) ve \(m_{i+1}=\varphi(m_i)\) olsun. \(m_L=1\) yapan ilk indeks \(L\) ile gösterilsin. Bu problemde \(L=24\)'tür. Dolayısıyla çağrı derinliği \(1855\) değil, pratikte yalnızca birkaç düzine seviyedir. Bellek tüketimi de bu yüzden \(O(L)\) kadardır.
Her seviyede mevcut modül trial division ile çarpanlara ayrılır ve ardından bir modüler üs alma yapılır. Üs değeri zaten bir sonraki modüle göre indirgenmiş olduğundan modüler üs alma maliyeti \(O(\log m_i)\) çarpımdır. Toplam süre
$$O\!\left(\sum_{i=0}^{L-1}\bigl(\sqrt{m_i}+\log m_i\bigr)\right)$$
şeklinde özetlenebilir. Modüller \(10^8\)'den \(1\)'e çok hızlı düştüğü için bu maliyet verilen girdi için rahatlıkla küçüktür.
El problema 188 pide las últimas ocho cifras de la tetración
$$1777 \uparrow\uparrow 1855 = 1777^{1777^{.^{.^{1777}}}}$$
con altura \(1855\). No se puede expandir esa torre de exponentes de manera directa: incluso muy arriba en la torre aparecen números imposibles de representar. La meta real es calcular su residuo módulo \(10^8\).
La idea consiste en sustituir una sola torre gigantesca por una cadena corta de problemas modulares más pequeños. El ingrediente central es el teorema de Euler, pero en este ejercicio también importa mucho que el módulo \(10^8\) tiene una descomposición en primos extremadamente regular.
Definamos
$$T_h = 1777 \uparrow\uparrow h,$$
y sea \(R(h,m)=T_h \bmod m\). Entonces
$$R(1,m)=1777 \bmod m,$$
y para \(h \ge 2\)
$$T_h = 1777^{T_{h-1}}.$$
Si \(\gcd(1777,m)=1\), el teorema de Euler permite reducir el exponente:
$$1777^x \equiv 1777^{\,x \bmod \varphi(m)} \pmod m.$$
Por lo tanto basta conocer el exponente módulo \(\varphi(m)\), y aparece la recurrencia
$$R(h,m)=1777^{\,R(h-1,\varphi(m))} \bmod m.$$
Ésta es la relación matemática que siguen exactamente las tres implementaciones.
El módulo inicial es
$$10^8 = 2^8 \cdot 5^8.$$
Para cualquier número de la forma \(2^a5^b\) con \(a,b \ge 1\),
$$\varphi(2^a5^b)=2^a5^b\left(1-\frac12\right)\left(1-\frac15\right)=2^{a+1}5^{b-1}.$$
Aplicando esa fórmula repetidamente se obtiene la cadena explícita
$$100000000 \to 40000000 \to 16000000 \to 6400000 \to 2560000 \to 1024000 \to 409600 \to 163840 \to 65536 \to 32768 \to \cdots \to 1.$$
De aquí salen dos observaciones importantes. Después de ocho aplicaciones de \(\varphi\), el factor \(5^b\) ya desapareció y sólo quedan potencias de \(2\). Además, tras 24 pasos el módulo se vuelve \(1\). Eso significa que una torre de altura \(1855\) se reduce en la práctica a unas pocas decenas de niveles útiles.
El número \(1777\) no es divisible ni por \(2\) ni por \(5\). Como todos los módulos de la cadena son de la forma \(2^a5^b\), en cada nivel vale
$$\gcd(1777,m_i)=1.$$
Por eso la recurrencia coprima se aplica sin excepciones en la entrada real del problema:
$$R(1855,10^8)=1777^{\,R(1854,40000000)} \bmod 10^8,$$
$$R(1854,40000000)=1777^{\,R(1853,16000000)} \bmod 40000000,$$
y así sucesivamente hasta que el módulo se convierte en \(1\), caso en el que el valor recursivo pasa automáticamente a ser \(0\). Nunca hace falta conocer el exponente completo \(T_{h-1}\); sólo su residuo módulo el siguiente totiente.
El control incorporado en las implementaciones ilustra el método completo. La cadena de totientes es
$$100 \to \varphi(100)=40 \to \varphi(40)=16.$$
Ahora se reconstruye de abajo hacia arriba:
$$3 \uparrow\uparrow 1 \equiv 3 \pmod{16},$$
$$3 \uparrow\uparrow 2 = 3^3 \equiv 27 \pmod{40},$$
$$3 \uparrow\uparrow 3 = 3^{27} \equiv 87 \pmod{100}.$$
El problema 188 usa exactamente la misma estrategia, sólo que sobre la cadena de totientes de \(10^8\).
La implementación necesita primero dos rutinas elementales. Una calcula \(\varphi(m)\) factorizando el módulo actual por división de prueba y aplicando la fórmula multiplicativa de la función totiente. La otra calcula \(a^e \bmod m\) mediante exponenciación modular binaria, lo que evita recorrer el exponente término a término.
Las implementaciones en C++, Python y Java evalúan después el residuo de la tetración de forma recursiva. Si el módulo vale \(1\), el resultado es \(0\) inmediatamente. Si la altura vale \(1\), el resultado es \(1777 \bmod m\). En cualquier otro caso se baja una vez a \(\varphi(m)\), se obtiene allí el residuo que hace falta para el exponente y se calcula \(1777^{e} \bmod m\) con ese valor reducido.
Además, las implementaciones incluyen una protección general para el caso no coprimo: cuando base y módulo no son coprimos, añaden un periodo de longitud \(\varphi(m)\) al exponente antes de elevar. Esa rama no interviene en el caso real de Problem 188, pero vuelve la rutina válida para una familia algo más amplia de entradas.
La matemática es la misma en los tres lenguajes; sólo cambia la herramienta concreta. Python usa la operación modular integrada con un argumento explícito para el módulo. Java delega la potenciación modular en su biblioteca de enteros de precisión arbitraria. C++ realiza la multiplicación modular en un tipo entero más ancho antes de reducir. En todos los casos, el algoritmo esencial es la misma recursión sobre la cadena de totientes.
Sea \(m_0=10^8\) y \(m_{i+1}=\varphi(m_i)\). Si \(L\) es el primer índice con \(m_L=1\), entonces aquí \(L=24\). Por eso la profundidad efectiva de la recursión no se acerca a \(1855\); en realidad sólo hay unas dos docenas de niveles útiles. El consumo de memoria es \(O(L)\).
En el nivel \(i\), el programa factoriza \(m_i\) por división de prueba para obtener \(\varphi(m_i)\) y después realiza una exponenciación modular cuyo costo es \(O(\log m_i)\) multiplicaciones modulares, porque el exponente ya ha sido reducido. Una cota resumida es
$$O\!\left(\sum_{i=0}^{L-1}\bigl(\sqrt{m_i}+\log m_i\bigr)\right).$$
Como los módulos descienden con mucha rapidez desde \(10^8\) hasta \(1\), el tiempo total es muy pequeño para la entrada pedida.
题目要求求出超幂
$$1777 \uparrow\uparrow 1855 = 1777^{1777^{.^{.^{1777}}}}$$
的最后八位，也就是它对 \(10^8\) 取模的结果。这里的指数塔高达 \(1855\) 层，显然不可能把整个数真正写出来，更不可能直接按普通整数运算去求值。真正可行的路线，是把“巨大指数塔”改写成一串较小模数上的递归余数问题。
这道题的关键并不是“如何算出完整的指数”，而是“在模意义下，指数到底需要知道多少”。实现所依据的核心工具是欧拉定理；而对本题来说，模数 \(10^8\) 的质因数结构又让整个递推链条变得非常整齐。
记
$$T_h = 1777 \uparrow\uparrow h,$$
并记 \(R(h,m)=T_h \bmod m\)。那么最底层有
$$R(1,m)=1777 \bmod m,$$
而当 \(h \ge 2\) 时，
$$T_h = 1777^{T_{h-1}}.$$
如果 \(\gcd(1777,m)=1\)，那么欧拉定理告诉我们
$$1777^x \equiv 1777^{\,x \bmod \varphi(m)} \pmod m.$$
这句话的意义非常重要：为了得到 \(1777^x \bmod m\)，并不需要知道完整的 \(x\)，只需要知道 \(x\) 对 \(\varphi(m)\) 的余数。因此可以把问题递归地改写成
$$R(h,m)=1777^{\,R(h-1,\varphi(m))} \bmod m.$$
三种语言的实现本质上都在执行这条递推式。
本题的模数是
$$10^8 = 2^8 \cdot 5^8.$$
对于形如 \(2^a5^b\) 且 \(a,b \ge 1\) 的数，有
$$\varphi(2^a5^b)=2^a5^b\left(1-\frac12\right)\left(1-\frac15\right)=2^{a+1}5^{b-1}.$$
所以从 \(10^8\) 开始不断取欧拉函数，会得到一条非常规整的链：
$$100000000 \to 40000000 \to 16000000 \to 6400000 \to 2560000 \to 1024000 \to 409600 \to 163840 \to 65536 \to 32768 \to \cdots \to 1.$$
这条链揭示了两个事实。第一，经过 8 次取 \(\varphi\) 以后，所有 \(5\) 的因子都会消失，后面只剩下 \(2\) 的幂。第二，只要 24 次左右，模数就已经降到 \(1\)。因此虽然原题的高度是 \(1855\)，真正需要处理的不同模数层数其实只有二十多层。
\(1777\) 既不被 \(2\) 整除，也不被 \(5\) 整除。而上面的每一个模数都可以写成 \(2^a5^b\) 的形式，所以对递归过程中出现的每一个 \(m_i\)，都有
$$\gcd(1777,m_i)=1.$$
这意味着本题从头到尾都处在“底数与模数互素”的理想情形，递推式可以毫无例外地直接使用：
$$R(1855,10^8)=1777^{\,R(1854,40000000)} \bmod 10^8,$$
$$R(1854,40000000)=1777^{\,R(1853,16000000)} \bmod 40000000,$$
然后继续沿着欧拉函数链往下走。当模数最终变成 \(1\) 时，递归值自动变成 \(0\)，再向上回代即可。换句话说，算法从来不需要知道完整的 \(1777 \uparrow\uparrow 1854\) 是多少，只需要知道它在更小模数下的余数。
实现里自带了一个很小的检验例子，它恰好能完整展示这个思路。先看欧拉函数链：
$$100 \to \varphi(100)=40 \to \varphi(40)=16.$$
接下来从最小模数那一层开始往回算：
$$3 \uparrow\uparrow 1 \equiv 3 \pmod{16},$$
$$3 \uparrow\uparrow 2 = 3^3 \equiv 27 \pmod{40},$$
$$3 \uparrow\uparrow 3 = 3^{27} \equiv 87 \pmod{100}.$$
本题的计算流程完全相同，只是把 \(100 \to 40 \to 16\) 换成了 \(10^8\) 对应的更长 totient 链。
实现先准备两个基础工具。第一个工具通过试除分解当前模数，并据此计算 \(\varphi(m)\)。第二个工具负责快速计算 \(a^e \bmod m\)：它使用二进制快速幂，因此即使指数很大，所需乘法次数也只与指数的二进制位数成正比。
C++、Python 和 Java 版本都采用相同的递归结构。如果模数已经是 \(1\)，结果立刻就是 \(0\)。如果高度是 \(1\)，结果就是 \(1777 \bmod m\)。否则就先递归到更小的模数 \(\varphi(m)\)，得到上一层指数所需的余数，再在当前模数下做一次模幂运算。
实现里还保留了一个更一般的非互素保护分支：当底数与模数不互素时，会在递归得到的指数上额外加上一个 \(\varphi(m)\) 周期，再做模幂。这让程序对更一般的输入也稳健。不过在 Problem 188 的真实参数下，这个分支始终不会触发，因为整个模数链都与 \(1777\) 互素。
三份实现的数学内容完全一致，只是底层工具不同。Python 直接使用语言内置的模幂运算，并显式给出模数参数。Java 把模幂运算交给其任意精度整数库。C++ 则在更宽的整数类型中完成乘法后再取模，以避免更大输入下的中间乘积风险。无论具体写法如何，核心算法都是同一条 totient 递归链。
设 \(m_0=10^8\)，并定义 \(m_{i+1}=\varphi(m_i)\)。令 \(L\) 为满足 \(m_L=1\) 的最小下标。对本题而言，\(L=24\)。因此递归的有效深度只有二十多层，而不是表面上的 \(1855\) 层，空间复杂度也只是 \(O(L)\)。
在第 \(i\) 层，程序需要通过试除来求 \(\varphi(m_i)\)，然后做一次模幂运算。由于指数已经被压缩到模 \(m_{i+1}\) 的范围内，模幂部分只需要 \(O(\log m_i)\) 次模乘。可以把总时间写成
$$O\!\left(\sum_{i=0}^{L-1}\bigl(\sqrt{m_i}+\log m_i\bigr)\right).$$
因为模数从 \(10^8\) 很快降到 \(1\)，这个代价对于题目给定输入非常小。
В задаче требуется найти последние восемь цифр тетрации
$$1777 \uparrow\uparrow 1855 = 1777^{1777^{.^{.^{1777}}}}$$
то есть вычислить это число по модулю \(10^8\). Высота башни равна \(1855\), поэтому прямое вычисление бессмысленно: уже на очень малой высоте показатель становится чудовищно большим. Нужен способ работать только с остатками.
Вместо одной гигантской башни степеней решение строит короткую цепочку более маленьких модульных задач. Главный инструмент здесь - теорема Эйлера. Для этой конкретной задачи особенно удобно то, что модуль \(10^8\) имеет очень регулярный вид \(2^8\cdot5^8\), поэтому вся цепочка \(\varphi\) выписывается явно.
Обозначим
$$T_h = 1777 \uparrow\uparrow h,$$
а через \(R(h,m)\) обозначим остаток \(T_h \bmod m\). Тогда
$$R(1,m)=1777 \bmod m,$$
и при \(h \ge 2\)
$$T_h = 1777^{T_{h-1}}.$$
Если \(\gcd(1777,m)=1\), теорема Эйлера даёт
$$1777^x \equiv 1777^{\,x \bmod \varphi(m)} \pmod m.$$
Значит, полный показатель не нужен; достаточно знать его остаток по модулю \(\varphi(m)\). Отсюда возникает рекурсия
$$R(h,m)=1777^{\,R(h-1,\varphi(m))} \bmod m.$$
Именно эту формулу и реализуют все три программы.
Начальный модуль равен
$$10^8 = 2^8 \cdot 5^8.$$
Для чисел вида \(2^a5^b\), где \(a,b \ge 1\), имеем
$$\varphi(2^a5^b)=2^a5^b\left(1-\frac12\right)\left(1-\frac15\right)=2^{a+1}5^{b-1}.$$
Поэтому последовательные значения \(\varphi\) образуют явную цепочку
$$100000000 \to 40000000 \to 16000000 \to 6400000 \to 2560000 \to 1024000 \to 409600 \to 163840 \to 65536 \to 32768 \to \cdots \to 1.$$
Здесь важны два факта. После восьми применений \(\varphi\) множитель \(5\) исчезает, и дальше остаются только степени двойки. А уже через 24 шага модуль становится равен \(1\). Поэтому, несмотря на высоту \(1855\), реально значимых уровней рекурсии всего около двух десятков.
Число \(1777\) не делится ни на \(2\), ни на \(5\). Каждый модуль в цепочке имеет вид \(2^a5^b\), следовательно, на каждом уровне выполняется
$$\gcd(1777,m_i)=1.$$
Значит, для реального входа задачи можно на каждом шаге без поправок писать
$$R(1855,10^8)=1777^{\,R(1854,40000000)} \bmod 10^8,$$
$$R(1854,40000000)=1777^{\,R(1853,16000000)} \bmod 40000000,$$
и так далее, пока модуль не дойдёт до \(1\). После этого рекурсивное значение автоматически становится равным \(0\), и вычисление разворачивается обратно вверх. Полный показатель \(T_{h-1}\) нигде не нужен; нужен только остаток по следующему модулю в цепочке.
Контрольный пример в коде достаточно мал, чтобы весь механизм можно было увидеть целиком. Сначала строим цепочку
$$100 \to \varphi(100)=40 \to \varphi(40)=16.$$
Теперь поднимаемся обратно:
$$3 \uparrow\uparrow 1 \equiv 3 \pmod{16},$$
$$3 \uparrow\uparrow 2 = 3^3 \equiv 27 \pmod{40},$$
$$3 \uparrow\uparrow 3 = 3^{27} \equiv 87 \pmod{100}.$$
В задаче 188 применяется точно та же идея, только цепочка \(\varphi\) начинается с \(10^8\) и заметно длиннее.
Сначала реализации используют две стандартные процедуры. Первая находит \(\varphi(m)\), раскладывая текущий модуль на простые множители методом пробного деления и применяя мультипликативную формулу для функции Эйлера. Вторая вычисляет \(a^e \bmod m\) бинарным быстрым возведением в степень, так что число шагов растёт логарифмически по величине показателя.
Далее реализации на C++, Python и Java одинаково спускаются по цепочке \(\varphi\). Если модуль уже равен \(1\), ответ сразу \(0\). Если высота равна \(1\), ответом становится \(1777 \bmod m\). Во всех остальных случаях программа сначала рекурсивно вычисляет нужный остаток по модулю \(\varphi(m)\), а затем возводит \(1777\) в найденную степень по текущему модулю.
В код также включена стандартная страховка для случая, когда база и модуль не взаимно просты: к рекурсивно найденному показателю добавляется один период длины \(\varphi(m)\) перед модульным возведением в степень. Для Problem 188 эта ветка не используется, потому что все возникающие модули взаимно просты с \(1777\).
Математика полностью совпадает, различается только низкоуровневая техника. Python использует встроенное модульное возведение в степень с явным аргументом модуля. Java поручает модульную степень своей библиотеке целых чисел произвольной точности. C++ умножает в более широком целочисленном типе и только затем берёт остаток. Но все три реализации считают одну и ту же тотьентную рекурсию.
Пусть \(m_0=10^8\), а \(m_{i+1}=\varphi(m_i)\). Обозначим через \(L\) первый индекс, для которого \(m_L=1\). В этой задаче \(L=24\). Следовательно, эффективная глубина рекурсии составляет всего несколько десятков уровней, а не \(1855\). Память равна \(O(L)\).
На уровне \(i\) программа сначала находит \(\varphi(m_i)\) пробным делением, а затем выполняет одно модульное возведение в степень. Поскольку показатель уже сокращён по модулю \(m_{i+1}\), стоимость второй части составляет \(O(\log m_i)\) модульных умножений. Совокупную оценку удобно записать так:
$$O\!\left(\sum_{i=0}^{L-1}\bigl(\sqrt{m_i}+\log m_i\bigr)\right).$$
Из-за того, что модули очень быстро падают от \(10^8\) к \(1\), этого более чем достаточно для заданного входа.
تطلب المسألة 188 إيجاد آخر ثمانية أرقام من التتريشن
$$1777 \uparrow\uparrow 1855 = 1777^{1777^{.^{.^{1777}}}}$$
أي حساب قيمة هذا البرج الهائل من الأسس بترديد \(10^8\). ارتفاع البرج هو \(1855\)، ولذلك فالتقييم المباشر مستحيل عمليًا؛ فحتى الطبقات الأولى تنتج أعدادًا أكبر بكثير من أي تمثيل صريح معقول. المطلوب إذن هو العمل بالمخلفات فقط.
الفكرة الأساسية هي استبدال برج أسس واحد بالغ الضخامة بسلسلة قصيرة من مسائل معيارية أصغر. الأداة الرئيسية هي مبرهنة أويلر، لكن ما يجعل هذه المسألة مريحة نسبيًا هو أن المودول \(10^8\) يملك تحليلاً أوليًا منتظمًا جدًا، ولهذا يمكن كتابة سلسلة \(\varphi\) بالكامل بصورة واضحة.
لنكتب
$$T_h = 1777 \uparrow\uparrow h,$$
ولنرمز بـ \(R(h,m)\) إلى الباقي \(T_h \bmod m\). عندئذ
$$R(1,m)=1777 \bmod m,$$
ولكل \(h \ge 2\) لدينا
$$T_h = 1777^{T_{h-1}}.$$
إذا كان \(\gcd(1777,m)=1\)، فإن مبرهنة أويلر تعطي
$$1777^x \equiv 1777^{\,x \bmod \varphi(m)} \pmod m.$$
وهذا يعني أننا لا نحتاج إلى معرفة الأس الكامل، بل يكفي معرفة باقيه modulo \(\varphi(m)\). ومن ثم نحصل على العلاقة التكرارية
$$R(h,m)=1777^{\,R(h-1,\varphi(m))} \bmod m.$$
وهذه هي الصيغة الرياضية التي تعتمد عليها جميع التطبيقات.
المودول الابتدائي هو
$$10^8 = 2^8 \cdot 5^8.$$
ولأي عدد من الشكل \(2^a5^b\) حيث \(a,b \ge 1\)، نحصل على
$$\varphi(2^a5^b)=2^a5^b\left(1-\frac12\right)\left(1-\frac15\right)=2^{a+1}5^{b-1}.$$
لذلك فإن التكرار المتتالي لدالة أويلر يعطي السلسلة الصريحة
$$100000000 \to 40000000 \to 16000000 \to 6400000 \to 2560000 \to 1024000 \to 409600 \to 163840 \to 65536 \to 32768 \to \cdots \to 1.$$
ومن هذه السلسلة نقرأ حقيقتين مهمتين. بعد ثماني تطبيقات لـ \(\varphi\) يختفي عامل \(5\) تمامًا وتبقى فقط قوى العدد \(2\). وبعد 24 خطوة تقريبًا يصبح المودول مساويًا لـ \(1\). لذا فمع أن ارتفاع البرج \(1855\)، فإن عدد المستويات المعيارية المختلفة التي نحتاجها فعليًا صغير جدًا.
العدد \(1777\) غير قابل للقسمة لا على \(2\) ولا على \(5\). وكل مودول يظهر في السلسلة السابقة له الصورة \(2^a5^b\). لذلك يتحقق في كل مستوى
$$\gcd(1777,m_i)=1.$$
وبالتالي يمكن استعمال علاقة الاختزال النظيفة في جميع مستويات المسألة الفعلية:
$$R(1855,10^8)=1777^{\,R(1854,40000000)} \bmod 10^8,$$
$$R(1854,40000000)=1777^{\,R(1853,16000000)} \bmod 40000000,$$
ثم نستمر هكذا حتى يصل المودول إلى \(1\)، وعندها تصبح القيمة التكرارية تلقائيًا \(0\). أي إن الخوارزمية لا تحتاج أبدًا إلى معرفة القيمة الكاملة لـ \(1777 \uparrow\uparrow 1854\)، بل تحتاج فقط إلى باقيها بالنسبة إلى المودول الأصغر التالي.
يتضمن التنفيذ نقطة تحقق صغيرة توضّح الفكرة كاملة. سلسلة أويلر هنا هي
$$100 \to \varphi(100)=40 \to \varphi(40)=16.$$
ثم نعيد البناء من الأسفل إلى الأعلى:
$$3 \uparrow\uparrow 1 \equiv 3 \pmod{16},$$
$$3 \uparrow\uparrow 2 = 3^3 \equiv 27 \pmod{40},$$
$$3 \uparrow\uparrow 3 = 3^{27} \equiv 87 \pmod{100}.$$
وهذه هي الآلية نفسها المستعملة في Problem 188، لكن مع السلسلة الأطول الخاصة بالمودول \(10^8\).
تحتاج الشيفرة أولاً إلى أداتين معياريتين. الأداة الأولى تحسب \(\varphi(m)\) عبر تحليل المودول الحالي بالقسمة التجريبية ثم تطبيق الصيغة الضربية لدالة أويلر. والأداة الثانية تنفذ \(a^e \bmod m\) بخوارزمية الأس السريع الثنائي، بحيث ينمو عدد الضربات المطلوبة لوغاريتميًا مع حجم الأس.
بعد ذلك تنفذ تطبيقات C++ وPython وJava البنية التكرارية نفسها. إذا كان المودول يساوي \(1\)، فالنتيجة مباشرة هي \(0\). وإذا كان الارتفاع يساوي \(1\)، فالنتيجة ببساطة \(1777 \bmod m\). وفي غير ذلك من الحالات تنزل الشيفرة خطوة واحدة إلى \(\varphi(m)\)، وتحصل هناك على الباقي اللازم للأس، ثم ترفع \(1777\) إلى تلك القوة modulo المودول الحالي.
وتحتوي التطبيقات أيضًا على حماية عامة للحالات غير المتوافقة نسبيًا: إذا لم تكن القاعدة والمودول متباينين أوليًا، تُضاف دورة واحدة بطول \(\varphi(m)\) إلى الأس قبل تنفيذ القوة المعيارية. هذا الفرع يجعل الروتين أكثر عمومية، لكنه لا يُستعمل في Problem 188 لأن جميع المودولات في السلسلة تبقى متباينة أوليًا مع \(1777\).
المحتوى الرياضي واحد في اللغات الثلاث، والاختلاف فقط في الوسائل العملية. Python تستعمل عملية القوة المعيارية المدمجة مع تمرير المودول صراحةً. Java تعتمد على مكتبتها الخاصة بالأعداد الصحيحة ذات الدقة الاعتباطية من أجل القوة المعيارية. أما C++ فتجري الضرب في نوع عددي أوسع قبل أخذ الباقي، وهذا يزيد الأمان مع المدخلات الأكبر. لكن الخوارزمية في الجوهر هي نفسها: نزول على سلسلة \(\varphi\) ثم صعود بالحساب المعياري.
لنعرّف \(m_0=10^8\) و\(m_{i+1}=\varphi(m_i)\)، ولْيكن \(L\) أول فهرس يحقق \(m_L=1\). في هذه المسألة نجد أن \(L=24\). لذلك فعمق التكرار الفعلي لا يقترب من \(1855\)، بل يقتصر على بضع وعشرين طبقة فقط، ومن ثم يكون استهلاك الذاكرة \(O(L)\).
في المستوى \(i\)، تحسب الشيفرة \(\varphi(m_i)\) بالقسمة التجريبية، ثم تنفذ قوة معيارية واحدة. وبما أن الأس قد اختُزل مسبقًا إلى مودول أصغر، فإن تكلفة هذه الخطوة هي \(O(\log m_i)\) ضربات معيارية. ويمكن تلخيص الزمن الكلي بالصيغة
$$O\!\left(\sum_{i=0}^{L-1}\bigl(\sqrt{m_i}+\log m_i\bigr)\right).$$
وبما أن المودولات تنخفض بسرعة كبيرة من \(10^8\) إلى \(1\)، فإن هذا التعقيد صغير جدًا بالنسبة إلى مدخلات المسألة.