Problem 396

Weak Goodstein sequence

For any positive integer n, the nth weak Goodstein sequence {g₁, g₂, g₃, …} is defined as:

g₁ = n
for k > 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 6th weak Goodstein sequence is {6, 11, 17, 25, …}:

g₁ = 6.
g₂ = 11 since 6 = 110₂, 110₃ = 12, and 12 - 1 = 11.
g₃ = 17 since 11 = 102₃, 102₄ = 18, and 18 - 1 = 17.
g₄ = 25 since 17 = 101₄, 101₅ = 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 nth weak Goodstein sequence.
It can be verified that G(2) = 3, G(4) = 21 and G(6) = 381.
It can also be verified that ΣG(n) = 2517 for 1 ≤ n < 8.

Find the last 9 digits of ΣG(n) for 1 ≤ n < 16.

弱古德斯坦序列

对于任意正整数n，第n个弱古德斯坦序列 {g₁, g₂, g₃, …}按如下方式定义：

g₁ = n
对于k > 1，将g_k-1写成k进制表示，然后将其视为k+1进制的数，最后减去1，得到g_k。

当g_k变为0时序列终止。

例如，第6个弱古德斯坦序列为{6, 11, 17, 25, …}：

g₁ = 6。
g₂ = 11，因为6 = 110₂，然后110₃ = 12，最后12 - 1 = 11。
g₃ = 17，因为11 = 102₃，然后102₄ = 18，最后18 - 1 = 17。
g₄ = 25，因为17 = 101₄，然后101₅ = 26，最后26 - 1 = 25。
依此类推。

可以证明所有弱古德斯坦序列都会终止。

记G(n)为第n个弱古德斯坦序列中的非零元素个数。
可以验证G(2) = 3，G(4) = 21以及G(6) = 381。
同样可以验证，对于1 ≤ n < 8，ΣG(n) = 2517。

对于1 ≤ n < 16，求ΣG(n)的最后9位数字。