ProjectEuler 396 Weak Goodstein sequence - 拼圖

396. Weak Goodstein sequence

http://projecteuler.net/problem=396


對於任何的正整數 n，第 n 個弱 Goodstein 數列 {g1,g2,g3,...} 被定義為：

‧ g1 = n

‧ 當 k > 1，gk 產生方式為 g(k-1) 以 k 進制表示，再將它以 k+1 進制轉換，再減 1


這數列在 gk 變為 0 時停止。


舉個例子，第 6 個弱 Goodstein 數列為 { 6 , 11 , 17 , 25 , ...}：

‧ g1 = 6

‧ g2 = 11（6 以 2 進制表示為 110，110 再以 3 進制轉換為 12，12 再減 1 為 11）

‧ g3 = 17（11 以 3 進制表示為 102，102 再以 4 進制轉換為 18，18 再減 1 為 17）

‧ g4 = 25（17 以 4 進制表示為 101，101 再以 5 進制轉換為 26，26 再減 1 為 25）

以此類推。


可以知道每個弱 Goodstein 數列最後都會停止。


使 G(n) 為第 n 個弱 Goodstein 數列中非零的元素的數量。


可以知道 G(2) = 3，G(4) = 21，G(6) = 381。


也已知道 ΣG(n) = 2517，當 1 ≦ n ＜ 8。


請求出 ΣG(n)，當 1 ≦ n ＜ 16 的末九位數。

--