числа Fibbinary

Числата Fibbinary са такива естествени числа, които в двоични си запис не съдържат две съседни 1-ци, а при равен брой цифри в двоична вид, техния брой (числа Fibbinary) е число на Фибоначи.  Интересна закономерност е, че ако числото n е в редицата, то там също са и числата 2*n и 4*n+1. Редицата с числа Fibbinary е разгледана подробно в http://oeis.org/A003714. Името е дадено от  Marc LeBrun.

Фигурата показва плътността на числа Fibbinary - тя неравномерно намалява с нарастване индекса на числото.

Съставете програма, чрез която се въвежда естествено число N от интервала [1..101] се извеждат числа Fibbinary до указания номер. Програмата да използва две аналогични функции - рекурсия и итерация.

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