ProjectEuler 384 Rudin-Shapiro sequence - 拼圖

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.

--