对于任何正整数 $n$，第 $n$ 个弱 Goodstein 序列 $\{g_1,g_2,g_3,\dots \}$ 定义为：

• $g_1=n$
• 对于 $k>1$，$g_k$ 是通过在基数 $k$ 中写入 $g_{k-1}$ 获得的，将其解释为基数 $k+1$ 数字，然后减去 $1$。

当 $g_k$ 变为 $0$ 时，序列终止。

例如，第 $6$ 个弱 Goodstein 序列是 $\{6,11,17,25,\dots \}$：

• $g_1=6$。
• $g_2=11$，因为 $6={110}_2$、${110}_3=12$ 和 $12-1=11$。
• $g_3=17$，因为 $11={102}_3$、${102}_4=18$ 和 $18-1=17$。
• $g_4=25$，因为 $17={101}_4$、${101}_5=26$ 和 $26-1=25$。

等等。

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

设 $G(n)$ 为第 $n$ 个弱 Goodstein 序列中非零元素的数量。
可以验证 $G(2)=3$、$G(4)=21$ 和 $G(6)=381$。
还可以验证 $\sum G(n)=2517$ 对于 $1\le n<8$。

找到$1\le n<16$ 的$\sum G(n)$ 的最后$9$ 位。