作者LPH66 (-858993460)
看板puzzle
标题[中译] Projecteuler (308)
时间Sat Oct 30 23:29:32 2010
: 推 babufong:可否借文求哪位板友帮翻Project Euler 308 XD 10/30 22:02
308. An amazing Prime-generating Automaton
一个叫做 Fractran 的"程式语言"的"程式"为一串分数。
这种"程式语言"有一个内部状态是个整数，初始值是某个种子。
每次它会乘上"程式"中第一个乘了之後还是整数的分数。
例如如下的这个由 John Horton Conway 所写的"程式":
17 78 19 23 29 77 95 77 1 11 13 15 1 55
----,----,----,----,----,----,----,----,----,----,----,----,---,----
91 85 51 38 33 29 23 19 17 13 11 2 7 1
如果它将种子设为 2 开始跑的话, 那麽以下会是这个"程式"运作当中的一部份状态值:
15, 825, 725, 1925, 2275, 425, ..., 68,
4, 30, ...,
136,
8, 60, ..., 544,
32, 240, ...
其中出现了许多 2 的次方值，如 4=2^2, 8=2^3, 32=2^5 等
可以证明，所有中间出现的 2 的次方其指数都是质数，
而且所有 2 的质数次方都会依序出现在其中！
如果有人利用这程式来解第七题(求第一万零一个质数)，
他需要执行几步才会得到 2^(第一万零一个质数) 这个值？
--
文中的那位 John Horton Conway 正是数学界的那位名人 Conway
(发明 Life game 的那家伙)
本题中的 Fractran 也是 Conway 本人发明的
http://en.wikipedia.org/wiki/FRACTRAN
连这题这个 14 个分数的"程式"也是他本人写的...
顺带一提, 2^2 会在第 19 步出现, 2^3 是第 69 步, 2^5 则是第 281 步
关於这支"程式"
http://www.jstor.org/stable/2690263 这篇文有详细解释
文中有个参考值是第一千个质数 8831
要出现 2^8831 需要 "near to a British billion" 也就是约 10^12 步
--
'Oh, Harry, don't you
see?' Hermione breathed. 'If she could have done
one thing to make
absolutely sure that every single person in this school
will read your interview, it was
banning it!'
---'Harry Potter and the order of the phoenix', P513
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.28.92
※ 编辑: LPH66 来自: 140.112.28.92 (10/30 23:35)
1F：推 babufong:太感谢LPH66 我还真不认识这位名人＠＠ 10/30 23:35
2F：→ babufong:自己翻的也相去不远 看来看不懂不是因语言 是背景知识 10/30 23:36
※ 编辑: LPH66 来自: 140.112.28.92 (10/30 23:43)
3F：推 babufong:再次感谢L大附上的连结 看了之後对这更了解了 10/30 23:43
4F：推 meowth:@@ 10/30 23:54
5F：推 utomaya:我解出来了 答案是"壹伍三九六六九八零七六六零九二四" 10/31 11:34
6F：→ utomaya:凌晨才看到这件文件 不过太累了 挣扎了一下还是体力不支 10/31 11:35
7F：→ utomaya:无缘前20 不过还是谢谢你的文件 10/31 11:36
8F：→ utomaya:不过 文件附的一千个质数(应为1100质数) 8831的步数是错的 10/31 11:38
9F：→ utomaya:应为923159118202 10/31 11:39
10F：→ utomaya:喔~ 拍谢 我搞错了 这文件是"near to a British billion" 10/31 11:41
11F：→ LPH66:其实文中的程式和题目的程式有点小不同 XD 10/31 13:33
12F：→ LPH66:那篇文中的程式是在第280步得到2^5 这里则是第281步 10/31 13:34
13F：→ LPH66:不过这一点差别应不致影响10^12这个估计值才是 10/31 13:34
14F：推 jurian0101:大开眼界了，康威竟然把哥德尔编码这样用~~~ 10/31 23:19