редица Thue-Morse

В математиката, редица Thue-Morse (Thue-Morse sequence. Prouhet-Thue-Morse sequence, Morse-Hedlund sequence) е двоична последователност (безкрайна последователност от 0-ли и 1-ци). Началният елемент е 0, последователно се добавя набор от 1-ци и 0-ли, така че стойността на добавения фрагмент от булеви стойности е инверсия на вече съществуващата предходна част. Така при втората стъпка се добавя 1 - вече първите два елемента са 01. Третата стъпка е добавяне на инверсната им стойност 10 - числовата редица е вече 0110. Четвъртата и всяка следваща стъпка следва същия алгоритъм - добавя се инверсията, побитовото отрицание, на предходните елементи. Инверсията на 0110 е 1001 и числовата редица Thue-Morse е вече 01101001 или 0, 1, 1, 0, 1, 0, 0, 1. Броя цифри, дължината на всеки следващ елемент, е два пъти по-голяма от тази на предходния. В езиците за програмиране съществува функция за побитово отрицание.

Съставете програма, чрез която се въвежда естествено число N от интервала [1..101] се извеждат последователните числа от редицата Thue-Morse до указания номер. Програмата да използва две аналогични функции - рекурсия и итерация. При извеждане на редицата е използвана следната формула за общия член: а(n) = (1+ A000069(n)) (mod 2).

Подробно описание за редицата Thue-Morse може да намерите на следните адреси: https://en.wikipedia.org/wiki/Thue-Morse_Sequence; http://mathworld.wolfram.com/Thue-MorseSequence.html, http://oeis.org/A010060.

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