редица на Golay-Rudin-Shapiro

В числовата редица на Golay-Rudin-Shapiro се разглежда двоичното представяне на последователните цели числа, като се търси отсъствие на 11. Пример: a(6) = -1, защото двоичното представяне на 6 е 110, което съдържа една поява на 11; докато b(7) = +1, защото двоичното представяне на 7 е 111, което съдържа две (припокриващи се) събития от 11. Редицата на Golay-Rudin-Shapiro е представена в https://oeis.org/A020985. Графиката отразява начина за формиране стойността на елементите.

Числова редица с подобен алгоритъм е описана в https://oeis.org/A014081. Всеки елемент представя нечетен броя открити 11 при двоичното представяне на числата. Пример: a(3) = -1, защото двоичното представяне 3(2) е 11, но a(7)=1 защото 11 се среща два пъти в двоичното представяне 7(2) = 111.

Съставете програма, чрез която се въвежда естествено число N от интервала [2..101] и се извежда изчисления брой числа от редица на Golay-Rudin-Shapiro. Програмата да използва две аналогични функции: рекурсия и итерация.

Допълнителен материал за числовата редица на Golay-Rudin-Shapiro може да намерите в: https://en.wikipedia.org/wiki/Rudin–Shapiro_sequence, http://mathworld.wolfram.com/Rudin-ShapiroSequence.html.

Разгледайте други примерни задачи, за чието решение се използват числови редици. Потърсете допълнителен материал за: тегло на Hamming, кръгли числа, разбиване на число, суми на Golay-Rudin-Shapiro.