[中譯] ProjectEuler 384 Rudin-Shapiro sequence

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者LPH66 (-858993460)時間13年前 (2012/05/13 15:34)推噓0(0推 0噓 0→)

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

384. Rudin-Shapiro sequence http://projecteuler.net/problem=384 定義數列 a(n) 表示 n 的二進位表示法中相鄰的 1 的組數 (可重疊)。例如: a(5) = a(101 ) = 0, a(6) = a(110 ) = 1, a(7) = a(111 ) = 2 2 2 2 定義 b(n) 是 (-1)^a(n) 。 b(n) 這個數列被稱做 Rudin-Shapiro sequence。 n 另外考慮 b(n) 的部份和: s(n) = Σ b(i) i=0 這些數列的前幾項可以列表如下： n 0 1 2 3 4 5 6 7 a(n) 0 0 0 1 0 0 1 2 b(n) 1 1 1 -1 1 1 -1 1 s(n) 1 2 3 2 3 4 3 4 s(n) 有個很特別的性質是所有項都是正的，且正整數 k 恰好出現 k 次。定義 g(t,c)，其中 1≦c≦t，表示 s(n) 當中第 c 次出現 t 的索引。例如: g(3,3) = 6，g(4,2) = 7，g(54321,12345) = 1220847710。令 F(n) 為費伯那西數列，如下定義： F(0)=F(1)=1， F(n)=F(n-1)+F(n-2) 當 n>1。定義 GF(t) = g(F(t),F(t-1))。求 ΣGF(t) 對 2≦t≦45。 -- 文中的三個數列 a(n): http://oeis.org/A014081 b(n): http://oeis.org/A020985 s(n): http://oeis.org/A020986 -- LPH [acronym] = Let Program Heal us -- New Uncyclopedian Dictionary, Minmei Publishing Co. -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.28.91