[中譯] Projecteuler (308)

[LPH66 (-858993460)]

: 推 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)
推 babufong:太感謝LPH66　我還真不認識這位名人＠＠
→ babufong:自己翻的也相去不遠　看來看不懂不是因語言　是背景知識
※ 編輯: LPH66           來自: 140.112.28.92        (10/30 23:43)
推 babufong:再次感謝L大附上的連結　看了之後對這更了解了
推 meowth:@@
推 utomaya:我解出來了 答案是"壹伍三九六六九八零七六六零九二四"
→ utomaya:凌晨才看到這件文件 不過太累了 掙扎了一下還是體力不支
→ utomaya:無緣前20 不過還是謝謝你的文件
→ utomaya:不過 文件附的一千個質數(應為1100質數) 8831的步數是錯的
→ utomaya:應為923159118202
→ utomaya:喔~ 拍謝 我搞錯了 這文件是"near to a British billion"
→ LPH66:其實文中的程式和題目的程式有點小不同 XD
→ LPH66:那篇文中的程式是在第280步得到2^5 這裡則是第281步
→ LPH66:不過這一點差別應不致影響10^12這個估計值才是
推 jurian0101:大開眼界了，康威竟然把哥德爾編碼這樣用~~~