For the weak Goodstein sequence starting from \(n\), write the current value in base \(b\), keep the same digit string, reinterpret it in base \(b+1\), subtract \(1\), and then increase the base. If \(g_0(n)=n\), then \(G(n)\) is the least step count for which the iterated process reaches \(0\). The program computes
$$\sum_{n=1}^{15} G(n) \pmod{10^9}.$$
If the current base is \(b\) and
$$x=\sum_{i=0}^{k} d_i b^i,\qquad 0\le d_i \lt b,$$
then one weak Goodstein step replaces \(x\) by
$$T_b(x)=\sum_{i=0}^{k} d_i (b+1)^i - 1.$$
So the sequence is
$$g_{t+1}(n)=T_{t+2}(g_t(n)),\qquad g_0(n)=n,$$
because the starting base is \(2\), then \(3\), then \(4\), and so on.
The implementations compute \(G(n)\) exactly for \(0 \le n \lt 8\) by direct simulation. The checkpoint values are
$$G(0)=0,\quad G(1)=1,\quad G(2)=3,\quad G(3)=5,\quad G(4)=21,\quad G(5)=61,\quad G(6)=381,\quad G(7)=2045.$$
In particular, the code verifies
$$\sum_{n=1}^{7} G(n)=2517.$$
These exact values are the only non-modular inputs needed for the larger cases \(8 \le n \le 15\).
For \(8 \le n \le 15\), write
$$n=8+r=2^3+r,\qquad 0\le r\lt 8.$$
Let
$$t=G(r).$$
The lower three binary positions evolve exactly like the weak Goodstein sequence for \(r\), while the leading binary digit at position \(3\) stays above that lower part. After those \(t\) steps, the tail has vanished, the current base is \(t+2\), and the state is the pure cube
$$g_t(n)=(t+2)^3.$$
So the whole problem reduces to counting how many steps remain from a number of the form \(b^3\) when the current base is \(b\), with
$$b=t+2.$$
Now consider a state whose current base is \(b\) and whose value is \(a b^2\), so its base-\(b\) digits are \(a,0,0\). The local digit dynamics produce a clean block length:
$$Q(b)=(b+1)\left(2^{b+1}-1\right).$$
A direct digit chase shows that one such square block lowers the leading coefficient by \(1\) and replaces the base by
$$b'=(b+1)2^{b+1}-1.$$
In other words, from the state \(a b^2\) in base \(b\), after exactly \(Q(b)\) further steps the process reaches
$$ (a-1)(b')^2 $$
in base \(b'\). For \(a=1\) this means termination; for \(a=2\) it means one square layer has been removed.
The reason for the closed form is that the lower two digits behave like a carry chain whose countdown lengths are
$$ (b+1),\ 2(b+1),\ 4(b+1),\ \dots,\ 2^b(b+1), $$
and summing this geometric progression gives \(Q(b)\).
Starting from \(b^3\) in base \(b\), the first square block converts the cube into a square with coefficient \(b\): after \(Q(b)\) steps the process reaches
$$b\,(b_1)^2,\qquad b_1=(b+1)2^{b+1}-1.$$
Each additional square block removes one more unit from that leading coefficient. It is convenient to write
$$s_0=b+1,\qquad s_{i+1}=s_i 2^{s_i},\qquad b_i=s_i-1.$$
Then
$$Q(b_i)=s_i\left(2^{s_i}-1\right),$$
and the total number of remaining steps from \(b^3\) is
$$F_3(b)=\sum_{i=0}^{b} s_i\left(2^{s_i}-1\right).$$
Returning to \(n=8+r\), with \(t=G(r)\) and \(b=t+2\), the program uses
$$H(s_0,m)=\sum_{i=0}^{m} s_i\left(2^{s_i}-1\right),\qquad s_{i+1}=s_i 2^{s_i},$$
where
$$s_0=t+3,\qquad m=t+2.$$
Therefore
$$G(n)\equiv t + H(t+3,t+2)\pmod{10^9},\qquad n\ge 8,$$
which is exactly the formula implemented by compute_g_mod.
The recurrence \(s_{i+1}=s_i 2^{s_i}\) explodes immediately. The solver never forms these integers explicitly after the small exact phase. Instead it computes everything modulo
$$10^9=2^9\cdot 5^9.$$
For a modulus of the form \(2^a 5^b\), the \(2\)-power part of \(2^s\) is simple: if \(s\ge a\), then
$$2^s\equiv 0 \pmod{2^a}.$$
For the \(5\)-power part, \(2\) is coprime to \(5\), so Euler's theorem gives period
$$\varphi(5^b)=4\cdot 5^{b-1}.$$
That is why the code builds the modulus chain
$$10^9,\ 4\cdot 5^8,\ 4\cdot 5^7,\ \dots,\ 20,\ 4,$$
and stores the current \(s_i\) modulo every entry in that chain. To recover \(2^{s_i}\bmod 2^a5^b\), it computes the residue modulo \(5^b\) from \(s_i \bmod 4\cdot 5^{b-1}\), computes the residue modulo \(2^a\) from the exact small value when needed, and combines the two pieces with the Chinese remainder theorem. This is the job of pow2_mod_composite.
Here \(r=0\), so \(t=G(0)=0\). Hence
$$b=t+2=2,\qquad s_0=t+3=3,\qquad m=t+2=2.$$
The first block length is
$$s_0(2^{s_0}-1)=3(8-1)=21.$$
After these \(21\) steps, the sequence has become \(2\cdot 23^2\) in base \(23\).
Next,
$$s_1=s_0 2^{s_0}=24,$$
so the second block length is
$$s_1(2^{s_1}-1)=24(2^{24}-1)=402653160.$$
After this block, the state is \(402653183^2\) in base \(402653183\).
Finally,
$$s_2=s_1 2^{s_1}=402653184,$$
and the last block \(s_2(2^{s_2}-1)\) is astronomically large. The modular engine evaluates the total directly and the implementations verify the checkpoint
$$H(3,2)\equiv 722374141 \pmod{10^9}.$$
All three solution files follow the same structure. goodstein_small simulates the process exactly for \(n \lt 8\). compute_g_mod uses those anchor values, applies the reduction \(n=8+r\), and then calls compute_h_mod.
compute_h_mod iterates through the block sum \(H(s_0,m)\) while keeping only residues for the modulus chain. build_mod_chain precomputes the CRT data, and pow2_mod_composite is the core routine that reconstructs \(2^{s_i}\) modulo each composite modulus. The final solve function sums \(G(n)\) for \(1\le n\le 15\) modulo \(10^9\).
The exact simulation phase is tiny because it only evaluates \(G(n)\) for \(n=1,\dots,7\), and the largest checkpoint is \(G(7)=2045\). In the modular phase, each call to compute_h_mod performs \(m+1\) updates across a fixed chain of length \(10\), so its cost is \(O(mL)\) with \(L=10\), and its memory use is \(O(L)\).
For this problem, \(m=t+2\) and \(t\in\{0,G(1),\dots,G(7)\}\), so even the largest case has \(m=2047\). In practice the whole computation is constant-scale and the modular arithmetic dominates the runtime.
Für die schwache Goodstein-Folge mit Startwert \(n\) schreibt man den aktuellen Wert in Basis \(b\), interpretiert dieselbe Ziffernfolge in Basis \(b+1\), subtrahiert \(1\) und erhöht dann die Basis. Mit \(g_0(n)=n\) sei \(G(n)\) die kleinste Schrittzahl, nach der der Prozess \(0\) erreicht. Das Programm berechnet
$$\sum_{n=1}^{15} G(n) \pmod{10^9}.$$
Ist die aktuelle Basis \(b\) und
$$x=\sum_{i=0}^{k} d_i b^i,\qquad 0\le d_i \lt b,$$
dann ersetzt ein Schritt \(x\) durch
$$T_b(x)=\sum_{i=0}^{k} d_i (b+1)^i - 1.$$
Damit gilt
$$g_{t+1}(n)=T_{t+2}(g_t(n)),\qquad g_0(n)=n,$$
weil die Folge mit Basis \(2\) startet und danach die Basen \(3,4,5,\dots\) verwendet.
Die Implementierungen berechnen \(G(n)\) für \(0 \le n \lt 8\) exakt per Simulation. Die verwendeten Kontrollwerte sind
$$G(0)=0,\quad G(1)=1,\quad G(2)=3,\quad G(3)=5,\quad G(4)=21,\quad G(5)=61,\quad G(6)=381,\quad G(7)=2045.$$
Insbesondere überprüft der Code
$$\sum_{n=1}^{7} G(n)=2517.$$
Diese Werte reichen aus, um alle größeren Fälle \(8 \le n \le 15\) auf eine modulare Berechnung zurückzuführen.
Für \(8 \le n \le 15\) schreiben wir
$$n=8+r=2^3+r,\qquad 0\le r\lt 8.$$
Sei
$$t=G(r).$$
Die unteren drei Binärstellen entwickeln sich dann genau wie die schwache Goodstein-Folge von \(r\), während die führende Binärziffer an Position \(3\) darüber stehen bleibt. Nach genau \(t\) Schritten ist der untere Teil verschwunden, die aktuelle Basis ist \(t+2\), und der Zustand lautet
$$g_t(n)=(t+2)^3.$$
Damit ist das Problem auf die Restlaufzeit eines Zustands der Form \(b^3\) in Basis \(b\) reduziert, wobei
$$b=t+2.$$
Betrachte nun einen Zustand mit aktueller Basis \(b\) und Wert \(a b^2\); in Basis \(b\) hat er also die Ziffern \(a,0,0\). Die lokale Zifferndynamik liefert die Blocklänge
$$Q(b)=(b+1)\left(2^{b+1}-1\right).$$
Eine direkte Ziffernverfolgung zeigt: Ein solcher Quadratblock verringert den führenden Koeffizienten um \(1\) und ersetzt die Basis durch
$$b'=(b+1)2^{b+1}-1.$$
Aus dem Zustand \(a b^2\) in Basis \(b\) wird also nach genau \(Q(b)\) weiteren Schritten der Zustand
$$ (a-1)(b')^2 $$
in Basis \(b'\). Für \(a=1\) bedeutet das Terminierung, für \(a=2\) wird genau eine Quadratschicht abgetragen.
Die geschlossene Formel entsteht daraus, dass sich die unteren zwei Ziffern wie eine Carry-Kette verhalten, deren Countdown-Längen
$$ (b+1),\ 2(b+1),\ 4(b+1),\ \dots,\ 2^b(b+1) $$
sind. Die Summe dieser geometrischen Reihe ist genau \(Q(b)\).
Startet man mit \(b^3\) in Basis \(b\), dann macht der erste Quadratblock aus dem Kubus ein Quadrat mit Koeffizient \(b\): Nach \(Q(b)\) Schritten erreicht der Prozess
$$b\,(b_1)^2,\qquad b_1=(b+1)2^{b+1}-1.$$
Jeder weitere Quadratblock entfernt eine weitere Einheit dieses führenden Koeffizienten. Praktisch ist die Schreibweise
$$s_0=b+1,\qquad s_{i+1}=s_i 2^{s_i},\qquad b_i=s_i-1.$$
Dann gilt
$$Q(b_i)=s_i\left(2^{s_i}-1\right),$$
und die gesamte Restlaufzeit von \(b^3\) ist
$$F_3(b)=\sum_{i=0}^{b} s_i\left(2^{s_i}-1\right).$$
Für \(n=8+r\) mit \(t=G(r)\) und \(b=t+2\) verwendet das Programm daher
$$H(s_0,m)=\sum_{i=0}^{m} s_i\left(2^{s_i}-1\right),\qquad s_{i+1}=s_i 2^{s_i},$$
mit
$$s_0=t+3,\qquad m=t+2.$$
Also
$$G(n)\equiv t + H(t+3,t+2)\pmod{10^9},\qquad n\ge 8,$$
und genau diese Formel steckt in compute_g_mod.
Die Rekursion \(s_{i+1}=s_i 2^{s_i}\) wächst sofort auf astronomische Größen. Deshalb erzeugt der Solver diese Zahlen nach der kleinen exakten Phase nie vollständig, sondern rechnet modulo
$$10^9=2^9\cdot 5^9.$$
Für einen Modul der Form \(2^a 5^b\) ist der \(2\)-Potenz-Anteil einfach: Sobald \(s\ge a\), gilt
$$2^s\equiv 0 \pmod{2^a}.$$
Für den \(5\)-Potenz-Anteil ist \(2\) teilerfremd zu \(5\), also liefert der Satz von Euler die Periode
$$\varphi(5^b)=4\cdot 5^{b-1}.$$
Darum baut der Code die Modulkette
$$10^9,\ 4\cdot 5^8,\ 4\cdot 5^7,\ \dots,\ 20,\ 4,$$
und speichert den aktuellen Wert \(s_i\) modulo jedes dieser Einträge. Um \(2^{s_i}\bmod 2^a5^b\) zu rekonstruieren, berechnet er den Rest modulo \(5^b\) aus \(s_i \bmod 4\cdot 5^{b-1}\), den Rest modulo \(2^a\) aus dem exakten kleinen Wert, solange das nötig ist, und setzt beide Teile per chinesischem Restsatz zusammen. Genau das erledigt pow2_mod_composite.
Hier ist \(r=0\), also \(t=G(0)=0\). Damit
$$b=t+2=2,\qquad s_0=t+3=3,\qquad m=t+2=2.$$
Die erste Blocklänge ist
$$s_0(2^{s_0}-1)=3(8-1)=21.$$
Nach diesen \(21\) Schritten ist der Zustand \(2\cdot 23^2\) in Basis \(23\).
Weiter gilt
$$s_1=s_0 2^{s_0}=24,$$
also hat der zweite Block die Länge
$$s_1(2^{s_1}-1)=24(2^{24}-1)=402653160.$$
Danach steht die Folge bei \(402653183^2\) in Basis \(402653183\).
Schließlich ist
$$s_2=s_1 2^{s_1}=402653184,$$
und der letzte Block \(s_2(2^{s_2}-1)\) ist viel zu groß für exakte Auswertung. Die modulare Engine berechnet den Gesamtwert direkt, und alle drei Implementierungen prüfen den Kontrollwert
$$H(3,2)\equiv 722374141 \pmod{10^9}.$$
Alle drei Lösungsdateien haben dieselbe Struktur. goodstein_small simuliert den Prozess exakt für \(n \lt 8\). compute_g_mod verwendet diese Ankerwerte, führt die Reduktion \(n=8+r\) aus und ruft dann compute_h_mod auf.
compute_h_mod iteriert die Blocksumme \(H(s_0,m)\), speichert dabei aber nur die Reste in der Modulkette. build_mod_chain baut die CRT-Daten auf, und pow2_mod_composite rekonstruiert \(2^{s_i}\) modulo jedem zusammengesetzten Modul. solve summiert schließlich \(G(n)\) für \(1\le n\le 15\) modulo \(10^9\).
Die exakte Simulationsphase ist klein, weil nur \(G(n)\) für \(n=1,\dots,7\) berechnet wird und der größte Kontrollwert \(G(7)=2045\) ist. In der modularen Phase führt jeder Aufruf von compute_h_mod genau \(m+1\) Aktualisierungen auf einer festen Kette der Länge \(10\) aus. Die Laufzeit ist daher \(O(mL)\) mit \(L=10\), der Speicherbedarf \(O(L)\).
Hier gilt \(m=t+2\) mit \(t\in\{0,G(1),\dots,G(7)\}\), also im größten Fall \(m=2047\). Praktisch ist die gesamte Rechnung daher sehr klein; die modulare Arithmetik dominiert die Laufzeit.
Zayıf Goodstein dizisinde başlangıç değeri \(n\) alınır; sayı mevcut taban \(b\) ile yazılır, aynı basamak dizisi \(b+1\) tabanında yeniden yorumlanır, \(1\) çıkarılır ve taban artırılır. \(g_0(n)=n\) olmak üzere bu süreç ilk kez \(0\)'a ulaştığında geçen adım sayısı \(G(n)\) ile gösterilir. Programın hesapladığı toplam
$$\sum_{n=1}^{15} G(n) \pmod{10^9}$$
ifadesidir.
Geçerli taban \(b\) ve
$$x=\sum_{i=0}^{k} d_i b^i,\qquad 0\le d_i \lt b$$
olsun. O zaman bir adım
$$T_b(x)=\sum_{i=0}^{k} d_i (b+1)^i - 1$$
dönüşümünü uygular. Dolayısıyla dizi
$$g_{t+1}(n)=T_{t+2}(g_t(n)),\qquad g_0(n)=n$$
şeklindedir; çünkü başlangıç tabanı \(2\)'dir ve sonra \(3,4,5,\dots\) gelir.
Uygulamalar \(0 \le n \lt 8\) için \(G(n)\) değerini doğrudan simülasyonla tam olarak hesaplar. Kontrol değerleri şunlardır:
$$G(0)=0,\quad G(1)=1,\quad G(2)=3,\quad G(3)=5,\quad G(4)=21,\quad G(5)=61,\quad G(6)=381,\quad G(7)=2045.$$
Kod ayrıca
$$\sum_{n=1}^{7} G(n)=2517$$
eşitliğini doğrular. Böylece \(8 \le n \le 15\) aralığındaki tüm daha büyük durumlar bu küçük kesin tabloya bağlanır.
\(8 \le n \le 15\) için
$$n=8+r=2^3+r,\qquad 0\le r\lt 8$$
yazalım. Burada
$$t=G(r)$$
olsun. Alt üç ikilik basamak, tam olarak \(r\)'nin zayıf Goodstein dizisi gibi davranır; üçüncü kuvvetteki en üst ikilik basamak ise bunun üzerinde kalır. Bu alt parça \(t\) adım sonra yok olduğunda, geçerli taban \(t+2\) olur ve elimizde
$$g_t(n)=(t+2)^3$$
durumu kalır. Yani geriye, geçerli tabanı \(b\) olan bir \(b^3\) durumunun kaç adım sürdüğünü bulmak kalır; burada
$$b=t+2.$$
Şimdi geçerli tabanı \(b\) olan ve değeri \(a b^2\) olan bir durumu inceleyelim. Bu sayı taban \(b\)'de \(a,0,0\) basamaklarına sahiptir. Yerel basamak dinamiği şu blok uzunluğunu verir:
$$Q(b)=(b+1)\left(2^{b+1}-1\right).$$
Doğrudan basamak takibi gösterir ki tek bir kare blok, baş katsayıyı \(1\) azaltır ve tabanı
$$b'=(b+1)2^{b+1}-1$$
değerine taşır. Yani taban \(b\)'deki \(a b^2\) durumu, tam olarak \(Q(b)\) adım sonra
$$ (a-1)(b')^2 $$
durumuna dönüşür. \(a=1\) ise süreç biter; \(a=2\) ise bir kare katman eksilmiş olur.
Bu kapalı formun nedeni, alttaki iki basamağın bir ödünç alma zinciri gibi davranması ve sayaç uzunluklarının
$$ (b+1),\ 2(b+1),\ 4(b+1),\ \dots,\ 2^b(b+1) $$
olmasıdır. Bu geometrik serinin toplamı tam olarak \(Q(b)\)'yi verir.
Başlangıç durumu taban \(b\)'de \(b^3\) ise, ilk kare blok bu küpü katsayısı \(b\) olan bir kareye dönüştürür. \(Q(b)\) adımdan sonra süreç
$$b\,(b_1)^2,\qquad b_1=(b+1)2^{b+1}-1$$
durumuna gelir. Sonraki her kare blok bu katsayıdan bir birim daha siler. Bunun için
$$s_0=b+1,\qquad s_{i+1}=s_i 2^{s_i},\qquad b_i=s_i-1$$
yazımı uygundur. O zaman
$$Q(b_i)=s_i\left(2^{s_i}-1\right)$$
olur ve \(b^3\) durumunun toplam kalan süresi
$$F_3(b)=\sum_{i=0}^{b} s_i\left(2^{s_i}-1\right)$$
şeklinde yazılır.
\(n=8+r\) için \(t=G(r)\) ve \(b=t+2\) olduğundan program
$$H(s_0,m)=\sum_{i=0}^{m} s_i\left(2^{s_i}-1\right),\qquad s_{i+1}=s_i 2^{s_i}$$
tanımını kullanır; burada
$$s_0=t+3,\qquad m=t+2.$$
Dolayısıyla
$$G(n)\equiv t + H(t+3,t+2)\pmod{10^9},\qquad n\ge 8$$
ve compute_g_mod fonksiyonunda uygulanan formül tam olarak budur.
\(s_{i+1}=s_i 2^{s_i}\) bağıntısı birkaç adım içinde devasa sayılar üretir. Bu yüzden çözücü, küçük kesin aşamadan sonra bu sayıların tamamını kurmaz; tüm işlemleri
$$10^9=2^9\cdot 5^9$$
modunda yapar. \(2^a5^b\) biçimindeki bir modül için \(2\)-kuvvet kısmı basittir: \(s\ge a\) olduğunda
$$2^s\equiv 0 \pmod{2^a}.$$
\(5\)-kuvvet kısmında ise \(2\) ile \(5\) aralarında asaldır; bu yüzden Euler teoremi periyodu
$$\varphi(5^b)=4\cdot 5^{b-1}$$
olarak verir. Kodun
$$10^9,\ 4\cdot 5^8,\ 4\cdot 5^7,\ \dots,\ 20,\ 4$$
modül zincirini kurmasının nedeni budur. Her aşamada \(s_i\) değeri bu zincirdeki tüm modüllere göre tutulur. Daha sonra \(2^{s_i}\bmod 2^a5^b\) değeri için, önce \(s_i \bmod 4\cdot 5^{b-1}\) yardımıyla \(5\)-kuvvet kalanı bulunur, gerekirse küçük kesin değerle \(2\)-kuvvet kalanı hesaplanır ve iki parça Çin kalan teoremi ile birleştirilir. Bunu yapan çekirdek fonksiyon pow2_mod_composite'tir.
Burada \(r=0\) olduğundan \(t=G(0)=0\). Dolayısıyla
$$b=t+2=2,\qquad s_0=t+3=3,\qquad m=t+2=2.$$
İlk blok uzunluğu
$$s_0(2^{s_0}-1)=3(8-1)=21$$
olur. Bu \(21\) adımın sonunda durum, taban \(23\)'te \(2\cdot 23^2\) haline gelir.
Sonra
$$s_1=s_0 2^{s_0}=24$$
ve ikinci blok uzunluğu
$$s_1(2^{s_1}-1)=24(2^{24}-1)=402653160$$
olur. Bu blok bittiğinde durum, taban \(402653183\)'te \(402653183^2\) olur.
Son olarak
$$s_2=s_1 2^{s_1}=402653184$$
ve \(s_2(2^{s_2}-1)\) terimi artık doğrudan açılmayacak kadar büyüktür. Modüler motor toplamı doğrudan hesaplar ve üç implementasyon da şu kontrolü kullanır:
$$H(3,2)\equiv 722374141 \pmod{10^9}.$$
Üç çözüm dosyası da aynı iskeleti izler. goodstein_small, \(n \lt 8\) için süreci tam olarak simüle eder. compute_g_mod bu küçük tabloyu kullanır, \(n=8+r\) indirgemesini uygular ve ardından compute_h_mod'u çağırır.
compute_h_mod, \(H(s_0,m)\) toplamını iteratif olarak işler ama yalnızca modül zincirindeki kalıntıları saklar. build_mod_chain CRT için gerekli verileri hazırlar; pow2_mod_composite ise her bileşik modülde \(2^{s_i}\) değerini yeniden kurar. Son olarak solve, \(1\le n\le 15\) için tüm \(G(n)\) değerlerini \(10^9\) modunda toplar.
Kesin simülasyon bölümü küçüktür; çünkü yalnızca \(n=1,\dots,7\) için çalışır ve en büyük kontrol değeri \(G(7)=2045\)'tir. Modüler fazda her compute_h_mod çağrısı, uzunluğu \(10\) olan sabit bir zincir üzerinde \(m+1\) güncelleme yapar. Bu yüzden çalışma süresi \(O(mL)\), bellek kullanımı \(O(L)\) olur; burada \(L=10\)'dur.
Bu problemde \(m=t+2\) ve \(t\in\{0,G(1),\dots,G(7)\}\) olduğundan en büyük durum \(m=2047\)'dir. Pratikte toplam iş yükü küçüktür; süreyi asıl belirleyen kısım modüler aritmetiktir.
En la sucesión débil de Goodstein que parte de \(n\), se escribe el valor actual en base \(b\), se conserva la misma cadena de dígitos, se reinterpreta en base \(b+1\), se resta \(1\) y luego se incrementa la base. Si \(g_0(n)=n\), denotamos por \(G(n)\) el menor número de pasos necesario para llegar a \(0\). El programa calcula
$$\sum_{n=1}^{15} G(n) \pmod{10^9}.$$
Si la base actual es \(b\) y
$$x=\sum_{i=0}^{k} d_i b^i,\qquad 0\le d_i \lt b,$$
entonces un paso sustituye \(x\) por
$$T_b(x)=\sum_{i=0}^{k} d_i (b+1)^i - 1.$$
Por tanto, la sucesión cumple
$$g_{t+1}(n)=T_{t+2}(g_t(n)),\qquad g_0(n)=n,$$
porque la base inicial es \(2\) y luego pasa a \(3,4,5,\dots\).
Las implementaciones calculan \(G(n)\) exactamente para \(0 \le n \lt 8\) mediante simulación directa. Los valores de control son
$$G(0)=0,\quad G(1)=1,\quad G(2)=3,\quad G(3)=5,\quad G(4)=21,\quad G(5)=61,\quad G(6)=381,\quad G(7)=2045.$$
Además, el código verifica
$$\sum_{n=1}^{7} G(n)=2517.$$
Estos valores exactos son las únicas entradas no modulares necesarias para los casos grandes \(8 \le n \le 15\).
Para \(8 \le n \le 15\), escribimos
$$n=8+r=2^3+r,\qquad 0\le r\lt 8.$$
Sea
$$t=G(r).$$
Las tres posiciones binarias inferiores evolucionan exactamente como la sucesión débil de Goodstein de \(r\), mientras que el dígito binario principal en la posición \(3\) queda por encima de esa parte inferior. Tras esos \(t\) pasos, la cola ha desaparecido, la base actual es \(t+2\) y el estado es
$$g_t(n)=(t+2)^3.$$
Así, el problema se reduce a contar cuántos pasos quedan desde un estado de la forma \(b^3\) cuando la base actual es \(b\), con
$$b=t+2.$$
Consideremos ahora un estado cuya base actual es \(b\) y cuyo valor es \(a b^2\), es decir, un número con dígitos \(a,0,0\) en base \(b\). La dinámica local de los dígitos produce la longitud de bloque
$$Q(b)=(b+1)\left(2^{b+1}-1\right).$$
Un seguimiento directo de los dígitos muestra que un bloque cuadrático reduce en \(1\) el coeficiente principal y reemplaza la base por
$$b'=(b+1)2^{b+1}-1.$$
En otras palabras, el estado \(a b^2\) en base \(b\) se transforma, después de exactamente \(Q(b)\) pasos adicionales, en
$$ (a-1)(b')^2. $$
Para \(a=1\) eso significa terminación; para \(a=2\) significa que se ha eliminado una capa cuadrática.
La fórmula cerrada aparece porque los dos dígitos inferiores actúan como una cadena de acarreos cuyos tiempos de cuenta atrás son
$$ (b+1),\ 2(b+1),\ 4(b+1),\ \dots,\ 2^b(b+1). $$
Sumando esa progresión geométrica se obtiene precisamente \(Q(b)\).
Si se parte de \(b^3\) en base \(b\), el primer bloque cuadrático convierte el cubo en un cuadrado con coeficiente \(b\). Tras \(Q(b)\) pasos, el proceso llega a
$$b\,(b_1)^2,\qquad b_1=(b+1)2^{b+1}-1.$$
Cada bloque cuadrático adicional elimina una unidad más de ese coeficiente principal. Resulta cómodo escribir
$$s_0=b+1,\qquad s_{i+1}=s_i 2^{s_i},\qquad b_i=s_i-1.$$
Entonces
$$Q(b_i)=s_i\left(2^{s_i}-1\right),$$
y el número total de pasos restantes desde \(b^3\) es
$$F_3(b)=\sum_{i=0}^{b} s_i\left(2^{s_i}-1\right).$$
Volviendo a \(n=8+r\), con \(t=G(r)\) y \(b=t+2\), el programa usa
$$H(s_0,m)=\sum_{i=0}^{m} s_i\left(2^{s_i}-1\right),\qquad s_{i+1}=s_i 2^{s_i},$$
donde
$$s_0=t+3,\qquad m=t+2.$$
Por tanto,
$$G(n)\equiv t + H(t+3,t+2)\pmod{10^9},\qquad n\ge 8,$$
que es exactamente la relación implementada en compute_g_mod.
La recurrencia \(s_{i+1}=s_i 2^{s_i}\) crece de forma inmediata hasta tamaños inmanejables. Por eso el solver no construye esos enteros completos después de la fase exacta pequeña, sino que trabaja todo el tiempo módulo
$$10^9=2^9\cdot 5^9.$$
Para un módulo de la forma \(2^a5^b\), la parte de potencia de \(2\) es sencilla: si \(s\ge a\), entonces
$$2^s\equiv 0 \pmod{2^a}.$$
Para la parte de potencia de \(5\), \(2\) es coprimo con \(5\), así que el teorema de Euler da el período
$$\varphi(5^b)=4\cdot 5^{b-1}.$$
Por eso el código construye la cadena de módulos
$$10^9,\ 4\cdot 5^8,\ 4\cdot 5^7,\ \dots,\ 20,\ 4,$$
y conserva el valor actual \(s_i\) módulo cada entrada de esa cadena. Para reconstruir \(2^{s_i}\bmod 2^a5^b\), calcula primero el residuo módulo \(5^b\) a partir de \(s_i \bmod 4\cdot 5^{b-1}\), calcula el residuo módulo \(2^a\) a partir del valor exacto pequeño cuando es necesario y finalmente une ambas piezas mediante el teorema chino del resto. Esa es la tarea de pow2_mod_composite.
Aquí \(r=0\), de modo que \(t=G(0)=0\). Entonces
$$b=t+2=2,\qquad s_0=t+3=3,\qquad m=t+2=2.$$
La longitud del primer bloque es
$$s_0(2^{s_0}-1)=3(8-1)=21.$$
Tras esos \(21\) pasos, la sucesión se ha convertido en \(2\cdot 23^2\) en base \(23\).
Luego,
$$s_1=s_0 2^{s_0}=24,$$
así que la longitud del segundo bloque es
$$s_1(2^{s_1}-1)=24(2^{24}-1)=402653160.$$
Después de ese bloque, el estado es \(402653183^2\) en base \(402653183\).
Por último,
$$s_2=s_1 2^{s_1}=402653184,$$
y el bloque final \(s_2(2^{s_2}-1)\) es ya enorme. El motor modular evalúa el total de manera directa, y las tres implementaciones verifican el punto de control
$$H(3,2)\equiv 722374141 \pmod{10^9}.$$
Los tres archivos de solución siguen la misma estructura. goodstein_small simula el proceso exactamente para \(n \lt 8\). compute_g_mod usa esos valores ancla, aplica la reducción \(n=8+r\) y luego llama a compute_h_mod.
compute_h_mod recorre la suma de bloques \(H(s_0,m)\) guardando solo residuos para la cadena modular. build_mod_chain prepara los datos del CRT, y pow2_mod_composite reconstruye \(2^{s_i}\) módulo cada módulo compuesto. Finalmente, solve suma \(G(n)\) para \(1\le n\le 15\) módulo \(10^9\).
La fase de simulación exacta es pequeña porque solo evalúa \(G(n)\) para \(n=1,\dots,7\), y el mayor valor de control es \(G(7)=2045\). En la fase modular, cada llamada a compute_h_mod realiza \(m+1\) actualizaciones sobre una cadena fija de longitud \(10\). Por eso su coste es \(O(mL)\) con \(L=10\), y la memoria es \(O(L)\).
En este problema, \(m=t+2\) con \(t\in\{0,G(1),\dots,G(7)\}\), así que incluso el caso mayor tiene \(m=2047\). En la práctica, el tamaño total del cálculo es pequeño y la aritmética modular domina el tiempo de ejecución.
弱 Goodstein 过程从 \(n\) 出发。每一步都把当前值写成基数 \(b\) 的表示，保持同一串数字不变，再把它当作基数 \(b+1\) 的表示来解释，随后减去 \(1\)，并把基数加一。若 \(g_0(n)=n\)，则 \(G(n)\) 表示第一次到达 \(0\) 所需的最小步数。程序要求计算
$$\sum_{n=1}^{15} G(n) \pmod{10^9}.$$
若当前基数为 \(b\)，并且
$$x=\sum_{i=0}^{k} d_i b^i,\qquad 0\le d_i \lt b,$$
则一步变换把 \(x\) 送到
$$T_b(x)=\sum_{i=0}^{k} d_i (b+1)^i - 1.$$
因此整个序列满足
$$g_{t+1}(n)=T_{t+2}(g_t(n)),\qquad g_0(n)=n,$$
因为起始基数是 \(2\)，随后依次变成 \(3,4,5,\dots\)。
三个实现都会对 \(0 \le n \lt 8\) 做精确模拟。它们使用的检查值是
$$G(0)=0,\quad G(1)=1,\quad G(2)=3,\quad G(3)=5,\quad G(4)=21,\quad G(5)=61,\quad G(6)=381,\quad G(7)=2045.$$
代码还验证了
$$\sum_{n=1}^{7} G(n)=2517.$$
对本题来说，这些精确小值已经足够支撑所有 \(8 \le n \le 15\) 的大情况。
对 \(8 \le n \le 15\)，写成
$$n=8+r=2^3+r,\qquad 0\le r\lt 8.$$
设
$$t=G(r).$$
最低的三个二进制位会完全按照 \(r\) 的弱 Goodstein 序列演化，而位于第 \(3\) 位的最高二进制位始终悬在这部分之上。经过 \(t\) 步以后，低位尾部恰好消失，当前基数变成 \(t+2\)，于是状态化为纯立方
$$g_t(n)=(t+2)^3.$$
因此问题被简化为：在当前基数就是 \(b\) 时，一个 \(b^3\) 状态还要走多少步；其中
$$b=t+2.$$
现在考察当前基数为 \(b\)、当前值为 \(a b^2\) 的状态，也就是 base-\(b\) 数字为 \(a,0,0\)。局部数字演化给出一个非常整齐的块长度
$$Q(b)=(b+1)\left(2^{b+1}-1\right).$$
直接追踪数字可以得到：一个这样的平方块会把最高系数减去 \(1\)，并把基数更新为
$$b'=(b+1)2^{b+1}-1.$$
也就是说，从 base \(b\) 下的 \(a b^2\) 出发，恰好经过 \(Q(b)\) 步之后，状态变成
$$ (a-1)(b')^2. $$
当 \(a=1\) 时，这意味着过程结束；当 \(a=2\) 时，则表示去掉了一层平方系数。
之所以能得到闭式，是因为下面两位的行为像一条借位链，它们的倒计时长度依次是
$$ (b+1),\ 2(b+1),\ 4(b+1),\ \dots,\ 2^b(b+1). $$
把这个几何级数求和，就得到 \(Q(b)\)。
若起点是 base \(b\) 下的 \(b^3\)，那么第一个平方块会把这个立方状态变成一个系数为 \(b\) 的平方状态。经过 \(Q(b)\) 步后，序列到达
$$b\,(b_1)^2,\qquad b_1=(b+1)2^{b+1}-1.$$
此后每一个平方块都会再去掉一个单位的最高系数。记
$$s_0=b+1,\qquad s_{i+1}=s_i 2^{s_i},\qquad b_i=s_i-1.$$
于是
$$Q(b_i)=s_i\left(2^{s_i}-1\right),$$
从 \(b^3\) 出发的总剩余步数就是
$$F_3(b)=\sum_{i=0}^{b} s_i\left(2^{s_i}-1\right).$$
回到 \(n=8+r\)，其中 \(t=G(r)\)、\(b=t+2\)。程序定义
$$H(s_0,m)=\sum_{i=0}^{m} s_i\left(2^{s_i}-1\right),\qquad s_{i+1}=s_i 2^{s_i},$$
并取
$$s_0=t+3,\qquad m=t+2.$$
因此
$$G(n)\equiv t + H(t+3,t+2)\pmod{10^9},\qquad n\ge 8,$$
这正是 compute_g_mod 中实现的公式。
递推 \(s_{i+1}=s_i 2^{s_i}\) 的增长速度极其夸张。实现不会在小规模精确阶段之后继续构造这些大整数，而是始终在
$$10^9=2^9\cdot 5^9$$
这个模数下工作。对于形如 \(2^a5^b\) 的模数，\(2\) 的幂在 \(2^a\) 部分非常简单：当 \(s\ge a\) 时，
$$2^s\equiv 0 \pmod{2^a}.$$
在 \(5^b\) 部分，由于 \(2\) 与 \(5\) 互素，Euler 定理给出周期
$$\varphi(5^b)=4\cdot 5^{b-1}.$$
这正是代码构造模链
$$10^9,\ 4\cdot 5^8,\ 4\cdot 5^7,\ \dots,\ 20,\ 4$$
的原因。程序会同时保存当前 \(s_i\) 在整条模链上的余数。为了求出 \(2^{s_i}\bmod 2^a5^b\)，它先利用 \(s_i \bmod 4\cdot 5^{b-1}\) 求出 \(5^b\) 部分，再在需要时用精确小值求 \(2^a\) 部分，最后用中国剩余定理合并。这个核心过程由 pow2_mod_composite 完成。
此时 \(r=0\)，所以 \(t=G(0)=0\)。于是
$$b=t+2=2,\qquad s_0=t+3=3,\qquad m=t+2=2.$$
第一块的长度为
$$s_0(2^{s_0}-1)=3(8-1)=21.$$
走完这 \(21\) 步以后，状态变成 base \(23\) 下的 \(2\cdot 23^2\)。
接下来
$$s_1=s_0 2^{s_0}=24,$$
所以第二块长度为
$$s_1(2^{s_1}-1)=24(2^{24}-1)=402653160.$$
这一块结束后，状态变成 base \(402653183\) 下的 \(402653183^2\)。
最后
$$s_2=s_1 2^{s_1}=402653184,$$
而最后一块 \(s_2(2^{s_2}-1)\) 已经无法直接展开。模运算引擎会直接求总和，三个实现都验证了检查值
$$H(3,2)\equiv 722374141 \pmod{10^9}.$$
三个解法文件的结构完全一致。goodstein_small 对 \(n \lt 8\) 做精确模拟。compute_g_mod 先读取这些小锚点，再执行 \(n=8+r\) 这一步化简，随后调用 compute_h_mod。
compute_h_mod 顺着块和 \(H(s_0,m)\) 向前迭代，但只保存模链上的余数。build_mod_chain 负责准备 CRT 所需的数据，pow2_mod_composite 则负责在每个复合模数下重建 \(2^{s_i}\) 的值。最后 solve 把 \(1\le n\le 15\) 的所有 \(G(n)\) 在 \(10^9\) 下累加。
精确模拟阶段很小，因为它只计算 \(n=1,\dots,7\)，并且最大的检查值不过是 \(G(7)=2045\)。在模运算阶段，每次调用 compute_h_mod 都只会在长度固定为 \(10\) 的模链上做 \(m+1\) 次更新。因此时间复杂度是 \(O(mL)\)，空间复杂度是 \(O(L)\)，其中 \(L=10\)。
在本题里，\(m=t+2\)，而 \(t\in\{0,G(1),\dots,G(7)\}\)，所以最大也只有 \(m=2047\)。实际运行中，整体规模是常数级的，主耗时来自模运算。
В слабой последовательности Гудстейна, стартующей из \(n\), текущее число записывается в базе \(b\), та же строка цифр переинтерпретируется в базе \(b+1\), затем вычитается \(1\), а база увеличивается. Если \(g_0(n)=n\), то \(G(n)\) обозначает минимальное число шагов до первого достижения \(0\). Программа вычисляет
$$\sum_{n=1}^{15} G(n) \pmod{10^9}.$$
Пусть текущая база равна \(b\), и
$$x=\sum_{i=0}^{k} d_i b^i,\qquad 0\le d_i \lt b.$$
Тогда один шаг заменяет \(x\) на
$$T_b(x)=\sum_{i=0}^{k} d_i (b+1)^i - 1.$$
Следовательно, последовательность задается формулой
$$g_{t+1}(n)=T_{t+2}(g_t(n)),\qquad g_0(n)=n,$$
потому что стартовая база равна \(2\), затем идут \(3,4,5,\dots\).
Все три реализации вычисляют \(G(n)\) точно для \(0 \le n \lt 8\) прямой симуляцией. Проверочные значения таковы:
$$G(0)=0,\quad G(1)=1,\quad G(2)=3,\quad G(3)=5,\quad G(4)=21,\quad G(5)=61,\quad G(6)=381,\quad G(7)=2045.$$
Кроме того, код проверяет равенство
$$\sum_{n=1}^{7} G(n)=2517.$$
Этих малых точных значений достаточно, чтобы свести все случаи \(8 \le n \le 15\) к модульному вычислению.
Для \(8 \le n \le 15\) представим число в виде
$$n=8+r=2^3+r,\qquad 0\le r\lt 8.$$
Пусть
$$t=G(r).$$
Три младших двоичных разряда эволюционируют в точности так же, как слабая последовательность Гудстейна для \(r\), а ведущая двоичная единица на позиции \(3\) находится выше этой части. Через \(t\) шагов хвост исчезает, текущая база становится равной \(t+2\), и состояние принимает вид
$$g_t(n)=(t+2)^3.$$
Тем самым задача сводится к подсчету числа оставшихся шагов для состояния вида \(b^3\) при текущей базе \(b\), где
$$b=t+2.$$
Рассмотрим теперь состояние с текущей базой \(b\) и значением \(a b^2\), то есть число с цифрами \(a,0,0\) в базе \(b\). Локальная динамика цифр дает длину блока
$$Q(b)=(b+1)\left(2^{b+1}-1\right).$$
Прямое отслеживание цифр показывает: один такой квадратный блок уменьшает старший коэффициент на \(1\) и заменяет базу на
$$b'=(b+1)2^{b+1}-1.$$
То есть из состояния \(a b^2\) в базе \(b\) процесс ровно через \(Q(b)\) шагов попадает в состояние
$$ (a-1)(b')^2. $$
При \(a=1\) это означает завершение; при \(a=2\) снимается один квадратный слой.
Закрытая формула возникает потому, что две младшие цифры ведут себя как цепочка заимствований, а длины соответствующих отсчетов равны
$$ (b+1),\ 2(b+1),\ 4(b+1),\ \dots,\ 2^b(b+1). $$
Сумма этой геометрической прогрессии и есть \(Q(b)\).
Если стартовать из \(b^3\) в базе \(b\), то первый квадратный блок превращает куб в квадрат с коэффициентом \(b\). После \(Q(b)\) шагов процесс достигает
$$b\,(b_1)^2,\qquad b_1=(b+1)2^{b+1}-1.$$
Каждый следующий квадратный блок убирает еще единицу этого старшего коэффициента. Удобно ввести обозначения
$$s_0=b+1,\qquad s_{i+1}=s_i 2^{s_i},\qquad b_i=s_i-1.$$
Тогда
$$Q(b_i)=s_i\left(2^{s_i}-1\right),$$
а общее число оставшихся шагов из \(b^3\) равно
$$F_3(b)=\sum_{i=0}^{b} s_i\left(2^{s_i}-1\right).$$
Возвращаясь к \(n=8+r\), где \(t=G(r)\) и \(b=t+2\), программа использует
$$H(s_0,m)=\sum_{i=0}^{m} s_i\left(2^{s_i}-1\right),\qquad s_{i+1}=s_i 2^{s_i},$$
при
$$s_0=t+3,\qquad m=t+2.$$
Следовательно,
$$G(n)\equiv t + H(t+3,t+2)\pmod{10^9},\qquad n\ge 8,$$
и именно это реализует функция compute_g_mod.
Рекурсия \(s_{i+1}=s_i 2^{s_i}\) взрывается по размеру уже после нескольких шагов. Поэтому после малой точной фазы решатель не строит эти числа явно, а работает только по модулю
$$10^9=2^9\cdot 5^9.$$
Для модуля вида \(2^a5^b\) двоичная часть проста: если \(s\ge a\), то
$$2^s\equiv 0 \pmod{2^a}.$$
Для части \(5^b\) число \(2\) взаимно просто с \(5\), и теорема Эйлера дает период
$$\varphi(5^b)=4\cdot 5^{b-1}.$$
Именно поэтому код строит цепочку модулей
$$10^9,\ 4\cdot 5^8,\ 4\cdot 5^7,\ \dots,\ 20,\ 4,$$
и хранит текущий \(s_i\) по модулю каждого звена этой цепочки. Чтобы восстановить \(2^{s_i}\bmod 2^a5^b\), он вычисляет остаток по модулю \(5^b\) из \(s_i \bmod 4\cdot 5^{b-1}\), вычисляет остаток по модулю \(2^a\) из точного малого значения, когда это еще нужно, и объединяет обе части китайской теоремой об остатках. Этим занимается pow2_mod_composite.
Здесь \(r=0\), значит \(t=G(0)=0\). Поэтому
$$b=t+2=2,\qquad s_0=t+3=3,\qquad m=t+2=2.$$
Длина первого блока равна
$$s_0(2^{s_0}-1)=3(8-1)=21.$$
После этих \(21\) шагов последовательность превращается в \(2\cdot 23^2\) в базе \(23\).
Далее
$$s_1=s_0 2^{s_0}=24,$$
так что длина второго блока равна
$$s_1(2^{s_1}-1)=24(2^{24}-1)=402653160.$$
После этого блока состояние равно \(402653183^2\) в базе \(402653183\).
Наконец,
$$s_2=s_1 2^{s_1}=402653184,$$
и последний блок \(s_2(2^{s_2}-1)\) уже астрономически велик. Модульный движок вычисляет сумму напрямую, и все три реализации проверяют контрольное значение
$$H(3,2)\equiv 722374141 \pmod{10^9}.$$
Структура у всех трех файлов решения одинакова. goodstein_small точно симулирует процесс для \(n \lt 8\). Функция compute_g_mod берет эти опорные значения, применяет редукцию \(n=8+r\) и затем вызывает compute_h_mod.
compute_h_mod проходит по сумме блоков \(H(s_0,m)\), сохраняя только остатки в модульной цепочке. build_mod_chain подготавливает данные для CRT, а pow2_mod_composite восстанавливает \(2^{s_i}\) по каждому составному модулю. В конце solve суммирует \(G(n)\) для \(1\le n\le 15\) по модулю \(10^9\).
Точная симуляция мала: она нужна только для \(n=1,\dots,7\), а крупнейшее контрольное значение равно \(G(7)=2045\). В модульной фазе каждый вызов compute_h_mod делает \(m+1\) обновлений по цепочке фиксированной длины \(10\). Поэтому время работы равно \(O(mL)\), а память \(O(L)\), где \(L=10\).
В данной задаче \(m=t+2\), а \(t\in\{0,G(1),\dots,G(7)\}\), так что даже максимальный случай имеет \(m=2047\). На практике весь расчет имеет постоянный масштаб, а основная стоимость приходится на модульную арифметику.
في متتالية Goodstein الضعيفة التي تبدأ من \(n\)، نكتب القيمة الحالية بالأساس \(b\)، ثم نعيد تفسير السلسلة نفسها من الأرقام بالأساس \(b+1\)، وبعد ذلك نطرح \(1\) ونزيد الأساس. إذا كان \(g_0(n)=n\)، فإن \(G(n)\) هو أقل عدد من الخطوات اللازمة للوصول إلى \(0\) لأول مرة. المطلوب في البرنامج هو حساب
$$\sum_{n=1}^{15} G(n) \pmod{10^9}.$$
إذا كان الأساس الحالي هو \(b\) وكتبنا
$$x=\sum_{i=0}^{k} d_i b^i,\qquad 0\le d_i \lt b,$$
فإن خطوة واحدة تستبدل \(x\) بالقيمة
$$T_b(x)=\sum_{i=0}^{k} d_i (b+1)^i - 1.$$
ومن ثم فإن المتتالية تحقق
$$g_{t+1}(n)=T_{t+2}(g_t(n)),\qquad g_0(n)=n,$$
لأن الأساس يبدأ من \(2\) ثم يصبح \(3,4,5,\dots\).
التنفيذات الثلاثة تحسب \(G(n)\) بدقة تامة عندما \(0 \le n \lt 8\) عن طريق المحاكاة المباشرة. قيم التحقق هي
$$G(0)=0,\quad G(1)=1,\quad G(2)=3,\quad G(3)=5,\quad G(4)=21,\quad G(5)=61,\quad G(6)=381,\quad G(7)=2045.$$
كما أن الكود يتحقق من العلاقة
$$\sum_{n=1}^{7} G(n)=2517.$$
وهذه القيم الدقيقة الصغيرة هي كل ما نحتاجه كمدخلات غير معيارية للحالات الأكبر \(8 \le n \le 15\).
عندما \(8 \le n \le 15\)، نكتب
$$n=8+r=2^3+r,\qquad 0\le r\lt 8.$$
ولنضع
$$t=G(r).$$
الخانات الثنائية الثلاث الدنيا تتطور بالضبط كما تتطور متتالية Goodstein الضعيفة للعدد \(r\)، بينما تبقى الخانة الثنائية العليا عند المرتبة \(3\) فوق هذا الجزء السفلي. بعد \(t\) خطوة يختفي الذيل السفلي، ويصبح الأساس الحالي هو \(t+2\)، وتتحول الحالة إلى
$$g_t(n)=(t+2)^3.$$
وبذلك تختزل المسألة إلى حساب عدد الخطوات المتبقية من حالة على الصورة \(b^3\) عندما يكون الأساس الحالي هو \(b\)، حيث
$$b=t+2.$$
لننظر الآن إلى حالة أساسها الحالي \(b\) وقيمتها \(a b^2\)، أي أن أرقامها في الأساس \(b\) هي \(a,0,0\). ديناميكية الأرقام المحلية تعطي طول كتلة واضحًا:
$$Q(b)=(b+1)\left(2^{b+1}-1\right).$$
ويبين تتبع الأرقام مباشرة أن كتلة تربيعية واحدة تُنقص المعامل الأعلى بمقدار \(1\)، وتستبدل الأساس بالقيمة
$$b'=(b+1)2^{b+1}-1.$$
أي أن الحالة \(a b^2\) في الأساس \(b\) تتحول بعد \(Q(b)\) خطوة إضافية بالضبط إلى
$$ (a-1)(b')^2. $$
عندما \(a=1\) فهذا يعني انتهاء العملية، وعندما \(a=2\) فهذا يعني إزالة طبقة تربيعية واحدة.
سبب ظهور الصيغة المغلقة هو أن الرقمين السفليين يعملان كسلسلة استلاف، وأطوال العد التنازلي تكون
$$ (b+1),\ 2(b+1),\ 4(b+1),\ \dots,\ 2^b(b+1). $$
وجمع هذه المتتالية الهندسية يعطي \(Q(b)\) تمامًا.
إذا بدأنا من \(b^3\) في الأساس \(b\)، فإن أول كتلة تربيعية تحول المكعب إلى مربع معامله الأعلى يساوي \(b\). بعد \(Q(b)\) خطوة نصل إلى
$$b\,(b_1)^2,\qquad b_1=(b+1)2^{b+1}-1.$$
وكل كتلة تربيعية لاحقة تزيل وحدة إضافية من هذا المعامل الأعلى. من المناسب أن نكتب
$$s_0=b+1,\qquad s_{i+1}=s_i 2^{s_i},\qquad b_i=s_i-1.$$
وعندئذٍ
$$Q(b_i)=s_i\left(2^{s_i}-1\right),$$
ويكون إجمالي عدد الخطوات المتبقية من \(b^3\) هو
$$F_3(b)=\sum_{i=0}^{b} s_i\left(2^{s_i}-1\right).$$
وبالعودة إلى \(n=8+r\)، حيث \(t=G(r)\) و\(b=t+2\)، يستخدم البرنامج
$$H(s_0,m)=\sum_{i=0}^{m} s_i\left(2^{s_i}-1\right),\qquad s_{i+1}=s_i 2^{s_i},$$
مع
$$s_0=t+3,\qquad m=t+2.$$
ومن ثم
$$G(n)\equiv t + H(t+3,t+2)\pmod{10^9},\qquad n\ge 8,$$
وهذه هي الصيغة التي تنفذها الدالة compute_g_mod حرفيًا.
العلاقة \(s_{i+1}=s_i 2^{s_i}\) تنمو بسرعة هائلة جدًا. لذلك لا يحاول الحل بعد المرحلة الدقيقة الصغيرة تكوين هذه الأعداد صراحة، بل يحسب كل شيء بترديد
$$10^9=2^9\cdot 5^9.$$
بالنسبة لموديل من الشكل \(2^a5^b\)، فإن جزء قوة الاثنين بسيط: إذا كان \(s\ge a\) فلدينا
$$2^s\equiv 0 \pmod{2^a}.$$
أما جزء قوة الخمسة، فبما أن \(2\) و\(5\) أوليان فيما بينهما، فإن نظرية أويلر تعطي الفترة
$$\varphi(5^b)=4\cdot 5^{b-1}.$$
ولهذا السبب يبني الكود سلسلة الموديلات
$$10^9,\ 4\cdot 5^8,\ 4\cdot 5^7,\ \dots,\ 20,\ 4,$$
ويحتفظ بالقيمة الحالية \(s_i\) بترديد كل عنصر في هذه السلسلة. وعند إعادة بناء \(2^{s_i}\bmod 2^a5^b\)، يُحسب أولًا باقي جزء \(5^b\) انطلاقًا من \(s_i \bmod 4\cdot 5^{b-1}\)، ثم يحسب جزء \(2^a\) من القيمة الدقيقة الصغيرة عندما يكون ذلك ضروريًا، وبعدها تُدمج القطعتان بواسطة نظرية البواقي الصينية. هذه هي مهمة pow2_mod_composite.
هنا \(r=0\)، ولذلك \(t=G(0)=0\). ومن ثم
$$b=t+2=2,\qquad s_0=t+3=3,\qquad m=t+2=2.$$
طول الكتلة الأولى هو
$$s_0(2^{s_0}-1)=3(8-1)=21.$$
بعد هذه الخطوات الإحدى والعشرين تصبح المتتالية هي \(2\cdot 23^2\) في الأساس \(23\).
ثم
$$s_1=s_0 2^{s_0}=24,$$
فيكون طول الكتلة الثانية
$$s_1(2^{s_1}-1)=24(2^{24}-1)=402653160.$$
وبعد هذه الكتلة تصبح الحالة \(402653183^2\) في الأساس \(402653183\).
وأخيرًا
$$s_2=s_1 2^{s_1}=402653184,$$
فتصبح الكتلة الأخيرة \(s_2(2^{s_2}-1)\) ضخمة جدًا بحيث لا يمكن توسيعها مباشرة. المحرك المعياري يحسب المجموع رأسًا، وتتحقق التنفيذات الثلاثة من نقطة الفحص
$$H(3,2)\equiv 722374141 \pmod{10^9}.$$
الملفات الثلاثة للحلول تتبع البنية نفسها. الدالة goodstein_small تحاكي العملية بدقة عندما \(n \lt 8\). ثم تستخدم compute_g_mod هذه القيم الصغيرة الثابتة، وتطبق الاختزال \(n=8+r\)، وبعد ذلك تستدعي compute_h_mod.
الدالة compute_h_mod تمر على مجموع الكتل \(H(s_0,m)\) مع الاحتفاظ فقط بالبواقي على سلسلة الموديلات. وتبني build_mod_chain بيانات CRT اللازمة، بينما تعيد pow2_mod_composite بناء \(2^{s_i}\) تحت كل موديل مركب. وفي النهاية تجمع solve قيم \(G(n)\) لكل \(1\le n\le 15\) بترديد \(10^9\).
مرحلة المحاكاة الدقيقة صغيرة جدًا، لأنها تحسب فقط \(G(n)\) للأعداد \(1,\dots,7\)، وأكبر قيمة تحقق هي \(G(7)=2045\). أما في المرحلة المعيارية، فكل استدعاء لـ compute_h_mod ينفذ \(m+1\) تحديثًا على سلسلة ثابتة الطول مقدارها \(10\). لذلك تكون الكلفة الزمنية \(O(mL)\) والذاكرة \(O(L)\)، حيث \(L=10\).
في هذه المسألة لدينا \(m=t+2\) و\(t\in\{0,G(1),\dots,G(7)\}\)، لذا حتى أكبر حالة لا تتجاوز \(m=2047\). عمليًا يبقى الحجم الكلي للحساب ثابتًا تقريبًا، والزمن الفعلي تهيمن عليه الحسابات المعيارية.