Задача 384
Последовательность Рудина-Шапиро

Определим последовательность a(n) как количество пар соседствующих единиц в двоичном представлении числа n (возможны перекрытия).
Например: a(5) = a(1012) = 0, a(6) = a(1102) = 1, a(7) = a(1112) = 2

Определим последовательность b(n) = (-1)a(n).
Эта последовательность называется последовательностью Рудина-Шапиро.

Также рассмотрим сумматорную последовательность для b(n): .

Первые несколько значений этих последовательностей приведены ниже:
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 ≤ ct, как индекс последовательности s(n), при котором t встречается в последовательности c-ый раз.
Например: 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.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net