[中譯] ProjectEuler 361 Subsequence of Thue-M
看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者babufong (嗶嗶)時間14年前 (2011/12/04 12:32)推噓11(11推 0噓 17→)留言28則, 3人參與討論串1/2 (看更多)
361. Subsequence of Thue - Morse sequence
http://projecteuler.net/problem=361
Thue - Morse sequence {Tn} 是一個二進位制的數列，他符合以下條件：
T0 = 0
T2n = Tn
T2n+1 = 1 - Tn
我們可以知道 {Tn} 的前幾項是這樣的：
01101001100101101001011001101001....
定義 {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)
推
12/04 16:51, , 1F
12/04 16:51, 1F
→
12/05 01:22, , 2F
12/05 01:22, 2F
推
12/05 06:41, , 3F
12/05 06:41, 3F
→
12/05 06:42, , 4F
12/05 06:42, 4F
推
12/05 20:36, , 5F
12/05 20:36, 5F
→
12/05 20:37, , 6F
12/05 20:37, 6F
→
12/05 20:38, , 7F
12/05 20:38, 7F
→
12/05 20:41, , 8F
12/05 20:41, 8F
→
12/05 20:41, , 9F
12/05 20:41, 9F
→
12/05 20:51, , 10F
12/05 20:51, 10F
推
12/06 00:26, , 11F
12/06 00:26, 11F
→
12/06 00:27, , 12F
12/06 00:27, 12F
推
12/06 00:49, , 13F
12/06 00:49, 13F
→
12/06 00:50, , 14F
12/06 00:50, 14F
→
12/06 00:51, , 15F
12/06 00:51, 15F
→
12/06 01:54, , 16F
12/06 01:54, 16F
推
12/06 01:58, , 17F
12/06 01:58, 17F
→
12/06 01:58, , 18F
12/06 01:58, 18F
→
12/06 02:06, , 19F
12/06 02:06, 19F
→
12/06 02:06, , 20F
12/06 02:06, 20F
推
12/08 20:20, , 21F
12/08 20:20, 21F
推
12/09 00:59, , 22F
12/09 00:59, 22F
→
12/09 01:00, , 23F
12/09 01:00, 23F
推
12/09 07:50, , 24F
12/09 07:50, 24F
推
12/10 00:23, , 25F
12/10 00:23, 25F
→
12/10 00:25, , 26F
12/10 00:25, 26F
推
12/10 03:12, , 27F
12/10 03:12, 27F
→
12/10 03:12, , 28F
12/10 03:12, 28F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
puzzle 近期熱門文章
5
21
PTT遊戲區 即時熱門文章
15
43
