作者babufong (嗶嗶)
看板puzzle
標題[中譯] ProjectEuler 396 Weak Goodstein sequence
時間Sun Sep 30 11:07:36 2012
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 的末九位數。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 125.224.9.104
※ 編輯: babufong 來自: 125.224.9.104 (09/30 11:08)
1F：推 LPH66:只到 15 果然有詐... G(8) 就已經是很 G8 的天文數字了 囧 09/30 13:32
2F：→ babufong:是啊 我還想說7還很好算 結果8就炸了 09/30 13:41
3F：推 LPH66:然後 9 更炸上天 orz 這樣 15 要怎麼算.... 09/30 13:44
4F：推 utomaya:我也炸掉了，然後我就想到282題的次方塔，非常類似的解法 09/30 17:10
5F：→ utomaya:G(8)=805306368*(2^402653183)-3 09/30 17:16
6F：推 LPH66:u大是不是中間少算了幾次翻倍... 09/30 17:28
7F：→ LPH66:喔囧 是我弄錯了 orz 09/30 17:29
8F：→ LPH66:還好 G(9) 應該沒弄錯 OAO 09/30 17:30
9F：推 jurian0101:太驚悚了，這樣子"連解最新十題"的成就今世別想完成XD 09/30 22:25
10F：→ babufong:成就好像是解最新一題、五題、二十五題吧XD 09/30 22:26