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