← 完整题目索引

PROJECT EULER · #0384

鲁丁-夏皮罗序列

Rudin-Shapiro Sequence

仅题目 · 待解原题 ↗

将序列 a(n) 定义为 n 的二进制展开中相邻的 1 对的数量(可能重叠)。
例如:a(5)=a(1012)=0a(6)=a(1102)=1a(7)=a(1112)=2

定义序列b(n)=(1)a(n)
这个序列称为Rudin-Shapiro序列。

还要考虑 b(n) 的求和序列:s(n)=i=0nb(i)

这些序列的前几个值是:

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),其中 1cts(n) 中的索引,其中 ts(n) 中出现第 c 次。
例如:g(3,3)=6g(4,2)=7g(54321,12345)=1220847710

F(n) 为斐波那契数列,定义如下:
F(0)=F(1)=1 并且
F(n)=F(n1)+F(n2) 对于 n>1

定义 GF(t)=g(F(t),F(t1))

GF(t) 2t45

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。