Detailed mathematical approach

Problem Summary

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}.$

Mathematical Approach

Step 1: One Weak Goodstein Step

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.

Step 2: Exact Small Values Used as Anchors

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\).

Step 3: Reducing \(n\) to a Pure Cube State

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.$

Step 4: The Square-Block Lemma

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)\).

Step 5: From \(b^3\) to the Recurrence Used in Code

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.

Step 6: Why Modular Evaluation Is Necessary

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.

Worked Example: \(n=8\)

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}.$

How the Code Works

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\).

Complexity Analysis

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.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=396
2. Goodstein sequences and termination: Wikipedia - Goodstein's theorem
3. Chinese remainder theorem: Wikipedia - Chinese remainder theorem
4. Euler's theorem and \(\varphi(5^k)=4\cdot 5^{k-1}\): Wikipedia - Euler's theorem