作者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