[中譯] Projecteuler (308)

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者LPH66 (-858993460)時間15年前 (2010/10/30 23:29)推噓5(5推 0噓 9→)

留言14則, 5人參與討論串1/1

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