作者babufong (嗶嗶)
看板puzzle
標題[中譯] ProjectEuler 361 Subsequence of Thue-Morse sequence
時間Sun Dec 4 12:32:40 2011
361. Subsequence of Thue - Morse sequence
http://projecteuler.net/problem=361
Thue - Morse sequence {Tn} 是一個二進位制的數列，他符合以下條件：
T0 = 0
T2n = Tn
T2n+1 = 1 - Tn
我們可以知道 {Tn} 的前幾項是這樣的：
01101001
100101101001011001101001....
定義 {An} 是一個整數數列，而他的每一項用二進位制表示都有出現在 {Tn} 之中
舉例來說，十進位制的 18 用二進位制表示就是 10010
10010 出現在 T8 到 T12 之間，所以 18 是 {An} 的其中一項
14 用二進位制表示為 1110，而 1110 從未出現在 {Tn} 中，故 14 不是 {An} 其中一項
An 的前幾項我們也知道了，如下：
n 0 1 2 3 4 5 6 7 8 9 10 11 12 ...
An 0 1 2 3 4 5 6 9 10 11 12 13 18 ...
我們還能證明出 A100 = 3251 而 A1000 = 80852364498
18
請計算出 Σ A10^k 的末九位
k=1
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 125.224.7.197
※ 編輯: babufong 來自: 125.224.7.197 (12/04 12:33)
1F：推 LPH66:啊, 一題平方數題號和幸運數題號出現了 12/04 16:51
2F：→ babufong:有助於解成就嗎XD 12/05 01:22
3F：推 LPH66:是啊 我的幸運數成就才 42 題而已 12/05 06:41
4F：→ LPH66:(話說現在到 361 為止也才 66 個幸運數...) 12/05 06:42
5F：推 LPH66:唔, 我現在是找到一個演算法可以求 An 了 12/05 20:36
6F：→ LPH66:可是如果要求 A_{10^18} 我需要一個遞歸數列的前10^9項和.. 12/05 20:37
7F：→ LPH66:這鬼東西顯然不可能先算好 偏偏OEIS上沒有這個遞歸數列orz 12/05 20:38
8F：→ LPH66:看有沒有人跟我核對一下: A_一萬 的末九位是 843783988 12/05 20:41
9F：→ LPH66:然後 A_一萬 這個數字是十進位34位 二進位113位 12/05 20:41
10F：→ babufong:我無法 我還是只會用excel解題orz 12/05 20:51
11F：推 LPH66:好像找到方法算了...結果還是用遞歸關係來做 12/06 00:26
12F：→ LPH66:不知道10^18時會不會很慢... 12/06 00:27
13F：推 utomaya:我也可以確定 A_一萬 的末九位是 843783988 12/06 00:49
14F：→ utomaya:若沒算錯的話 A_1萬=6717653396222467045074718843783988 12/06 00:50
15F：→ utomaya:加油了! 還剩4個席位... 12/06 00:51
16F：→ babufong:u大您不必緊張 前次改版已經將席位加到50席了XD 12/06 01:54
17F：推 LPH66:現在的進度是 A_{10^15} 要約25秒 然後索引多1位要3~4倍時間 12/06 01:58
18F：→ LPH66:在想要不要就乾脆半小時給他暴力跑出來好了... 12/06 01:58
19F：→ LPH66:結果因為記太多東西了 A_{10^16} 直接告訴我記憶體不足 XD 12/06 02:06
20F：→ LPH66:再來想想怎麼省... 12/06 02:06
21F：推 LPH66:最後還是回到跑比較快的 C 用了三分鐘跑出了一個錯的答案.. 12/08 20:20
22F：推 utomaya:如果沒算錯的話 A_{10^18}化作二進制應該有1126216794位數 12/09 00:59
23F：→ utomaya:好大的數字 12/09 01:00
24F：推 LPH66:看來果然哪裡出事了...我算的 A_{10^18} 是二進位快15億位 12/09 07:50
25F：推 LPH66:可惡, 原來是 long long overflow 了....orz 12/10 00:23
26F：→ LPH66:到 A_{10^17} 應該都是對的 但是 A_{10^18} 中間結果溢位了 12/10 00:25
27F：推 LPH66:終於搞定了! 拿到第 26 名 XD 12/10 03:12
28F：→ LPH66:(其實會一直鑽這題就是想拿前百名的成就 XDDDD) 12/10 03:12