396 : 弱グッドスタイン数列

任意の正の整数$n$に対して、第n弱グッドスタイン数列 (nth weak Goodstein sequence) $\{ 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弱グッドスタイン数列は$\{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$であるから

以下同様である。

すべての弱グッドスタイン数列は有限であることを示すことができる。

第n弱グッドスタイン数列のうち、非ゼロである要素の個数を$G(n)$としよう。 $G(2) = 3, G(4) = 21, G(6) = 381$であることが確かめられている。 同様に、$1 \leq n < 8$に対して$\sum G(n) = 2517$であることが確かめられている。

$1 \leq n < 16$に対する$\sum G(n)$の最後の9桁を求めよ。