Weak Goodstein Sequence

For any positive integer $n$, the $n$th weak Goodstein sequence $\{g_1, g_2, g_3, \dots\}$ is defined as:
$g_1 = n$
for $k \gt 1$, $g_k$ is obtained by writing $g_{k-1}$ in base $k$, interpreting it as a base $k + 1$ number, and subtracting $1$.

The sequence terminates when $g_k$ becomes $0$.

For example, the $6$th weak Goodstein sequence is $\{6, 11, 17, 25, \dots\}$:
$g_1 = 6$.
$g_2 = 11$ since $6 = 110_2$, $110_3 = 12$, and $12 – 1 = 11$.
$g_3 = 17$ since $11 = 102_3$, $102_4 = 18$, and $18 – 1 = 17$.
$g_4 = 25$ since $17 = 101_4$, $101_5 = 26$, and $26 – 1 = 25$.

and so on.

It can be shown that every weak Goodstein sequence terminates.

Let $G(n)$ be the number of nonzero elements in the $n$th weak Goodstein sequence.
It can be verified that $G(2) = 3$, $G(4) = 21$ and $G(6) = 381$.
It can also be verified that $\sum G(n) = 2517$ for $1 \le n \lt 8$.

Find the last $9$ digits of $\sum G(n)$ for $1 \le n \lt 16$.

This is a problem from Project Euler (Problem 396), and its solution involves a mix of number theory, combinatorics, and programming skills. Here is the general idea of how you would solve this.

Let’s denote the $n$th weak Goodstein sequence as $g^{(n)}=\{g_1^{(n)},g_2^{(n)},\ldots\}$. If we look at the initial terms of these sequences, we quickly see that $g_2^{(n)} = n \times (n+1)$, $g_3^{(n)} = n \times (n+1) \times (n+2)/2$, etc. In general, the $k$th term seems to meet the formula $g_k^{(n)} = n \times (n+1) \times (n+2) \ldots (n+k-1) / [(k-1)!]$.

The next observation is that a term $g^{(n)}_k$ from the $n$th weak Goodstein sequence in base $k$ always has the form $\overline{111\ldots1}_k$. This helps a lot to calculate the next term $g^{(n)}_{k+1} = g^{(n)}_k (k+1) – 1 = \overline{111\ldots1}_k (k+1) – 1$ in a relatively efficient way.

Now let’s denote by $a_k (n)$ the number of base-$k$ digits in $g^{(n)}_{k+1}$ (note this excludes the least significant digits). We seek an expression for $a_{k+1} (n)$ using $a_k (n)$. It turns out that the digits of $\overline{111\ldots1}_k (k+1)$ in base $k+1$ are dependent only on the three least significant digits of $\overline{111\ldots1}_k$.

Using these observations, we can construct a recurrence for $a_k (n)$ which allows us to compute it relatively efficiently.

Finally, remember the task was to compute $G(n)$, the number of nonzero terms in the n-th Goodstein sequence. These nonzero terms are precisely the nonzero $a_k (n)$. So, we just compute these values for $1\leq n\leq 15$ and we sum them up modulo $10^9$ to get the last 9 digits.

It is also worth mentioning that this problem is computationally difficult and the description provided here just gives you a roadmap. Writing an efficient computer program implementing these insights might still be pretty challenging. Furthermore, proving the facts stated here formally would also constitute a significant amount of work. For example, proving that all Goodstein sequences terminate is equivalent to proving the termination of the Hydra Game, which is non-trivial and requires the use of ordinal numbers.

More Answers: