Projecteuler (308) - 拼圖

: 推 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

--