редица на Sturmian

Редицата на Sturmian (Sturmian word, Sturmian sequence или billiard sequence) съдържа само 0 и 1 и се използва за определяне броя на различните реални корени на полином от теоремата на Sturm. Такава последователност от числа може да бъде генерирана, чрез играта английски билярд на квадратна маса. Ударената топка последователно може да удари вертикалните и хоризонталните ръбове. Друг начин за представяне елементите на редицата е чрез функцията на Sturm (0 -> 01, 1->0) - към началните елементи на редицата се добавя предходен елемент.

Следват условия на задачи, свързани с числовата редица на Sturmian.

1. Числовата редица представена https://oeis.org/A159684 описва редица на Sturmian имаща за свои първи 20 елемента числата: 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0.

2. Числовата редица от https://oeis.org/A080764 има следните първи 20 елемента:1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0.

3. Числовата редица в https://oeis.org/A171588 има следните първи 20 елемента: 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1.

4. Числовата редица в https://oeis.org/A001333 има следните първи 10 елемента: 1, 1, 3, 7, 17, 41, 99, 239, 577, 1393. Свързана е със знаменатели на дроби при представяне на sqrt(2). Разгледайте допълнителен материал за числа на Пел.

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

Подробно описание за редицата на Sturmian може да намерите и на следните адреси: https://en.wikipedia.org/wiki/Sturmian_sequence; https://en.wikipedia.org/wiki/Sturmian_word; http://mathworld.wolfram.com/SturmianSequence.html.

Използвани формули:

1. a(n) = floor((n + 2)*(sqrt(2) - 1)) - floor((n + 1)*(sqrt(2) - 1)).

2. a(n) = floor((n+1)*sqrt(2)/2) - floor(n*sqrt(2)/2)).

3. a(n) = floor((n + 1)/(2 + sqrt(2))) - floor(n /(2 + sqrt(2))).

4. a(n) = 2*a(n-1) + a(n-2).

Разгледаните редиците са свързани с тези на Бийти (Beatty sequence) – използват ирационални числа.

Разгледайте други основни типове примерни задачи, за чието решение се използват числови редици. Сравнете тази числова редица с числа на Пел, редица на Бийти.