Фибоначчи k-го ур-я + алгебраическое число в цепную дробь

[Andrey A]

dimkadimon в сообщении #1414134 писал(а):

... в какой строке $(k)$ и под каким номером $n$ встретится некоторое заданное натуральное число $M$? У вас уже есть ответ на этот вопрос для маленьких $M$?

Да как же, вот в посте от 15.06.2019 описан алгоритм, отвечающий на этот вопрос однозначно, и даже известно количество шагов алгоритма. Это касается нетривиальных решений $M\ (n/k>3$), тривиальные решения имеются для любого $M$ и описываются формулой (там же). По вашей ссылке находим последовательность $F^{k=4}_n$. Случаи $k<4$ также имеются в OEIS (об этом в начале темы), но выписывать далее частные случаи функции от двух переменных вряд ли интересно для OEIS. Хотя да, вот вижу k=5,6,8... терпеливые они) Двумерный же массив включает в себя любое $M$, причем бесконечное число раз, что видно из формулы $M=F^{k=M+t}_{n=2M-1+t}\ (t=0,1,2,...)$. Решения ложатся на некоторую кривую (которую и "пеленгует" алгоритм), к моменту $(n/k<2$) она вырождается в прямую под углом $45^{\circ}$. Что значит маленькое $M$? Давайте так: Вы мне задаете число, я привожу пример полного решения уравнения $M=F^y_x$. Видимо, я опять смутно всё изложил. Число можно с вариантами, а то с вероятностью $2/3$ имеем отсутствие нетривиальных решений.

[dimkadimon]

Ок можно увидеть решения для $M \leq 20$ ?

[Andrey A]

dimkadimon в сообщении #1414226 писал(а):

... можно увидеть решения для $M \leq 20$ ?

Пожалуйста. Берем $M=16$.
1. Вычисляем $c=\left \lfloor \frac{\sqrt{8\cdot 16+17}-3}{2} \right \rfloor=4$.
2. $F^{c-2}_{3c-5}=F^{2}_{7}=13.$ Поскольку $13<16$, следующим шагом уменьшаем верхний индекс на $1$, нижний – на $2$.

3. $F^{2-1}_{7-2}=F^{1}_{5}=16.$ Имеем одно нетр. решение, и поскольку $k=1$, других больше нет.

4. Тривиальные решения на промежутке $3\geqslant \frac{n}{k}>2$ вычисляем по формуле $M=F^{ M-\frac{t(t+1)}{2}}_{2M-1-t^2}\ (1 < t \leqslant c$)$, и далее по формуле $M=F^{M+t}_{2M-1+t}\ (t=0,1,2,...)$ Итого:

$$16=F_{15}^6=F_{22}^{10}=F_{27}^{13}=F_{30}^{15}=F_{31+t}^{16+t}$$

Некоторые тривиальные решения могут быть вычислены двояко, поэтому на границе интервалов иногда возникает путаница. Это ладно. Возьмем число побольше и ограничимся поиском нетривиальных решений, a то не очень показательно.

$M=281$
$c=\left \lfloor \frac{\sqrt{8\cdot 281+17}-3}{2} \right \rfloor=22$.
$F^{c-2}_{3c-5}=F^{20}_{61}=274<281.$ Уменьшаем верхний индекс на $1$, нижний – на $2$ (обозначим это "процедура 2", или пр2)
$F^{20-1}_{61-2}=F^{19}_{59}=276<281.$ пр2
$F^{18}_{57}=281=281.$ Решение. пр2
$F^{17}_{55}=290>281.$ Оставляем верхний индекс без изменений, нижний уменьшаем на $1$ (процедура 1, или пр1)
$F^{17}_{54}=258<281.$ пр2
$F^{16}_{52}=267<281.$ пр2
$F^{15}_{50}=281=281.$ Решение. пр2
$F^{14}_{48}=301>281.$ пр1
$F^{14}_{47}=259<281.$ пр2
$F^{13}_{45}=279<281.$ пр2
$F^{12}_{43}=306>281.$ пр1
$F^{12}_{42}=258<281.$ пр2
$F^{11}_{40}=285>281.$ пр1
$F^{11}_{39}=238<281.$ пр2
$F^{10}_{37}=265<281.$ пр2
$F^{9}_{35}=300>281.$ пр1
$F^{9}_{34}=246<281.$ пр2
$F^{8}_{32}=281=281.$ Решение. пр2
$F^{7}_{30}=330>281.$ пр1
$F^{7}_{29}=264<281.$ пр2
$F^{6}_{27}=322>281.$ пр1
$F^{6}_{26}=251<281.$ пр2
$F^{5}_{24}=325>281.$ пр1
$F^{5}_{23}=245<281.$ пр2
$F^{4}_{21}=345>281.$ пр1
$F^{4}_{20}=250<281.$ пр2
$F^{3}_{18}=406>281.$ пр1
$F^{3}_{17}=277<281.$ пр2
$F^{2}_{15}=610>281.$ пр1
$F^{2}_{14}=377>281.$ пр1
$F^{2}_{13}=233<281.$ пр2
$F^{1}_{11}=1024>281.$ пр1
$F^{1}_{10}=512>281.$ пр1
$F^{1}_{9}=256<281.$ Конец. Три нетривиальных решения. Полное решение запишем дробями:

$281\ //\ \frac{8}{32},\frac{15}{50},\frac{18}{57},\frac{28}{77},\frac{50}{120},\frac{71}{161},\frac{91}{200},\frac{110}{237},\frac{128}{272},\frac{145}{305},\frac{161}{336},\frac{176}{365},\frac{190}{392},\frac{203}{417},\frac{215}{440},\frac{226}{461},\frac{236}{480},$$\frac{245}{497},\frac{253}{512},\frac{260}{525},\frac{266}{536},\frac{271}{545},\frac{275}{552},\frac{278}{557},\frac{280}{560},\frac{281+t}{561+t}.$

Вычислять $F^k_n$ можно различными способами, это обсуждается. Я использую формулу $F^{k+1}_{n+1}=\sum\limits_{i=0} \binom{{n-ki}}{i}$. К примеру $F^8_{32}=\binom{31}{0}+\binom{24}{1}+\binom{17}{2}+\binom{10}{3}=1+24+136+120=281.$
Спрашивайте, если что-то непонятно.

[Andrey A]

PS Промашка вышла в первом примере. Правильно так: $16=F_{5}^1=F_{15}^6=F_{22}^{10}=F_{27}^{13}=F_{30}^{15}=F_{31+t}^{16+t}$

[Andrey A]

Andrey A в сообщении #1414305 писал(а):

... на границе интервалов иногда возникает путаница.

PS PS Путаницу с тривиальными решениями надо бы устранить, чтобы к этому больше не возвращаться. Пусть $t_n=\dfrac{n(n+1)}{2}$ $n$-ая сумма натурального ряда. Для каждого $M>1$ определено $c=\left \lfloor \dfrac{\sqrt{8M+17}-3}{2} \right \rfloor$. Тем самым определена двойная последовательность, которую запишу дробями: $\dfrac{f_c'}{f_c''}=\dfrac{-t_c}{-c^2},\dfrac{-t_{c-1}}{-(c-1)^2},\dfrac{-t_{c-2}}{-(c-2)^2},\dfrac{-t_{c-3}}{-(c-3)^2},...,\dfrac{-1}{-1},\dfrac{0}{0},\dfrac{1}{1},\dfrac{2}{2},\dfrac{3}{3},...$ Тогда все тривиальные решения для $M>1$ определены формулой

$$M=F_{2M-1+f_c''}^{M+f_c'}$$

Отдельный случай $M=1$. Тут просто: $F_n^k=1$ для всех $n \leqslant k.$

[Andrey A]

Andrey A в сообщении #1253915 писал(а):

... Интересен также вопрос делимости членов указанных последовательностей, но этим пока не занимался.

В случае $k=1$ возможен единственный простой делитель $p=2$. Случай $k=2$ описан подробно в литературе, но для $k>2$ простых закономерностей на первый взгляд не просматривается. Будем выписывать вместо $F_n^k$ остатки деления $F_n^k \mod p$, где $p$ – некоторое простое число. Количество возможных подпоследовательностей длиной $k$ конечно, и с некоторого $n$ неизбежно повторение. Значит последовательность $F_n^k \mod p$ периодична ( $F_n^{k}=F_{n-1}^{k}+F_{n-k}^{k}$ ), причем для фиксированных $k,p$ длина периода определена однозначно. Обозначим $N_p^k$ – длина периода последовательности $F_n^k \mod p$. Отсюда сразу следует общая закономерность

$$a \equiv b \mod N_p^k \ \ \Rightarrow \ \ F_a^k \equiv F_b^k \mod p,$$

а также несколько утверждений для составных модулей, которые строго доказать не берусь:

$$N^k_{p_1p_2...p_n}=\ lcm (N^k_{p_1},N^k_{p_2},...,N^k_{p_n}).$$

$$N^k_{p^r}=p^{r-1}N^k_p.$$

$$N^k_{p_1^{r_1}p_2^{r_2}...p_n^{r_n}}=\ lcm (N^k_{p_1^{r_1}},N^k_{p_2^{r_2}},...,N^k_{p_n^{r_n}}).$$

Исправлено 19.09.2019


Порядок расположения нулей внутри периода последовательности $F_n^k \mod p$ – вопрос отдельный. В случае $k=1$ их нет вообще, а значение $N^1_{p>2}$ совпадает со значением дискретного логарифма по основанию $2$. В случае $k=2$ расположение нулей внутри периода также периодично. "Малый" период может быть равен $N_p^2,N_p^2/2$ или $N_p^2/4$. Об этом можно почитать, пройдя по ссылке maxal, там же описан метод вычисления малого периода непрерывными дробями. Но вот в случае $k>2$ нули непериодичны; об этом чуть позже, пока приведу пример $N^2_3=N^3_3=8:$

$$F_n^2 \mod 3=(1,1,2,0,2,2,1,0)$$

$$F_n^3 \mod 3=(1,1,1,2,0,1,0,0)$$

Как видим, решение уравнения $F^2_x \ \vdots \ 3$ записывается короче, чем $F^3_x \ \vdots \ 3$. В первом случае $x \equiv 0 \mod 4$, во втором $x \equiv 5,7,0 \mod 8$. Тут, однако, возникают вопросы.
1) Обязательно ли период включает в себя $k$ начальных единиц? Это было бы удобно, т.к. других методов вычисления $N^k_p$ кроме перебора по $\mod p$ не известно, но что если период начинается с $k+1$-го знака?
2) Почему, собственно, нули вообще должны содержаться в периоде? Что если члены одной из рассматриваемых последовательностей не делятся к примеру на $127$? Справедливо же это для $F^1_n$.
Перепишем рекуррентное правило $F_n^{k}=F_{n-1}^{k}+F_{n-k}^{k}$ так: $F_{n-k}^{k}=F_n^{k}-F_{n-1}^{k}.$ Здесь до сих пор рассматривались последовательности положительных чисел, но в случае $k>1$ ничто не мешает продолжить их влево $(n<1)$, и всё сказанное выше о делимости $F^k_n$ остается в силе. В частности, предыдущий пример можно было получить из двух/трех последовательных единиц в обратном порядке. Иными словами, каждые $k$ последовательных члена полностью определяют последовательность остатков не только в прямом, но и в обратном движении, любой номер можно взять "точкой отсчета", и предположение о существовании членов, не входящих в период приводит тогда к противоречию. Далее видим, что для всех последовательностей, за исключением $k=1$ определено $F^k_0=F^k_k-F^k_{k-1}=1-1=0.$ Оно делится на любое $p$, и, значит, через $N^k_p$ номеров получим еще хотя бы один член кратный $p$, например $p=127$. Продолжая строить последовательность влево от единиц по $\mod p$, получаем в обратном порядке $k-1$ нулей, единицу, $k-2$ нуля, $p-1$. Это доказывает невозможность периодического расположения нулей внутри периода для $k>2$. Наиболее близки к этому состоянию $N^p_p=p^2-1$ и более общий случай $N^{(p^r)}_p=p^{2r}-1$ (относительно короткие периоды). Таблица некоторых значений $N^k_p<50000$ выглядит так:

$$\begin{matrix} & p & 2 & 3 & 5 & 7 & 11 & 13 & 17 & 19\\ k & + & --- & --- & --- & --- & --- & --- & --- & ---\\ 1 & | & 1 & 2 & 4 & 3 & 10 & 12 & 8 & 18\\ 2 & | & 3 & 8 & 20 & 16 & 10 & 28 & 36 & 18\\ 3 & | & 7 & 8 & 31 & 57 & 60 & 168 & 288 & 381\\ 4 & | & 15 & 80 & 312 & 342 & 1330 & 2196 & 96 & 14480\\ 5 & | & 21 & 78 & 24 & 336 & 120 & 366 & 288 & 180\\ 6 & | & 63 & 728 & 3124 & 2400 & & & & \\ 7 & | & 127 & 728 & 19531 & 48 & & & & \\ 8 & | & 63 & 3146 & 2232 & & & & & \end{matrix}$$

[Andrey A]

Andrey A в сообщении #1258474 писал(а):

Возникает гипотеза, которую не берусь строго доказать, но численно подтверждается:
Для конечного числа фиксированных $a>b>c>d>...>0$, не имеющих общего делителя $>1$, последовательность $K_n$ определена, как количество композиций $n$ из $a,b,c,d,…$ и задается рекуррентным правилом $K_n=K_{n-a}+K_{n-b}+K_{n-c}+K_{n-d}+...$ при стартовых условиях $K_0=1,K_{n<0}=0$. Предел отношения соседних членов такой последовательности $(n\rightarrow \infty )$ есть вещественный корень уравнения $x^a-x^{a-b}-x^{a-c}-x^{a-d}-...=1$.

Это можно обобщить. Пусть задана последовательность $K_{n<0}=0,K_0=1,K_n=b_0K_{n-a_0}+b_1K_{n-a_1}+b_2K_{n-a_2}+...+b_mK_{n-a_m}$, где $a_i,b_i$ — некоторые фиксированные наборы натуральных аргументов, $a_0>a_{i>0}$. Отношение соседних членов $K_n/K_{n-1}$ такой последовательности с ростом $n$ стремится к положительному вещественному корню уравнения $x^{a_0}-b_1x^{a_0-a_1}-b_2x^{a_0-a_2}-...-b_mx^{a_0-a_m}=b_0.$ Параметр $b_0$ можно брать и отрицательным числом. В некоторых случаях отрицательными могут быть другие $b_i$, если последовательность не становится знакопеременной. Знать это заранее бывает не просто. Логически мысля, ничто не мешает $b_i \in \mathbb{R}$. Однако, в случае приближенных вычислений имеем дело с накапливающейся ошибкой. Не пробовал.

[arseniiv]

Ну как, теория (однородных линейных рекуррентных уравнений) говорит, что если корни $\xi_i$ характеристического уравнения (которое вы написали) все разные, решение имеет вид $C_1 \xi_1^n + \ldots + C_m \xi_m^n$. Отсюда можно сделать вывод, когда знакопеременность на бесконечном промежутке неизбежна, а когда ещё сойдёт (чтобы все отрицательные корни были «забиты» большим по модулю положительным).

Ну и если корни бывают кратные, всё снова аналогично дифурам: будут вместо констант многочлены от $n$ соответствующей степени. Тут хитрее будет, да.

Кстати вы зря вводите эти $a_1, a_2, \ldots$, они ничем не увеличивают общность по сравнению с перебором всех чисел от $1$ до $a_m$ (и пусть некоторые коэффициенты будут нулями, делов-то), а чтение всего, куда они попадают, ухудшают.

[Andrey A]

arseniiv в сообщении #1426738 писал(а):

... эти $a_1, a_2, \ldots$, они ничем не увеличивают общность по сравнению с перебором всех чисел от $1$ до $a_m$

Ну да, достаточно было бы вместо $a>b>c>d>...$ уточнить $a\geqslant b\geqslant c\geqslant d \geqslant...$ Если кто из капли воды может сделать вывод о существовании морей, озер и океанов, то и вовсе писать ничего не нужно. А так всё же понарядней будет ) Применимо ли это в численных методах решения уравнений?

[arseniiv]

Andrey A в сообщении #1426751 писал(а):

Ну да, достаточно было бы вместо $a>b>c>d>...$ уточнить $a\geqslant b\geqslant c\geqslant d \geqslant...$

Я имел в виду, что можно вместо

Andrey A в сообщении #1426705 писал(а):

Пусть задана последовательность $K_{n<0}=0,K_0=1,K_n=b_0K_{n-a_0}+b_1K_{n-a_1}+b_2K_{n-a_2}+...+b_mK_{n-a_m}$, где $a_i,b_i$ — некоторые фиксированные наборы натуральных аргументов, $a_0>a_{i>0}$.
<…>
$x^{a_0}-b_1x^{a_0-a_1}-b_2x^{a_0-a_2}-...-b_mx^{a_0-a_m}=b_0.$

написать куда более простое (но не уменьшающее общности!)

кто-нибудь бы писал(а):

Пусть задана последовательность $K_{n<0}=0, K_0=1,$ $K_n = b_{m-1} K_{n-1} + b_{m-2} K_{n-2} + \ldots + b_0 K_{n-m}$, где $b_i$ — некоторые натуральные числа [или нули, если здесь ноль не считается натуральным].
<…>
$x^m = b_{m-1} x^{m-1} + \ldots + b_1 x + b_0.$

и это куда более снисходительно по отношению к глазам читателя.

Andrey A в сообщении #1426751 писал(а):

Применимо ли это в численных методах решения уравнений?

То, как мы записываем уравнение? А какая разница. Когда численно решают, нередко представляют уравнение в какой-нибудь такой форме, которую анализировать — или брать за исходные данные — было бы наоборот не очень удобно.

-- Вт ноя 19, 2019 15:05:25 --

Кстати я бы снял условие $K_{<0} = 0$, потому что нам нужно только несколько нулей непосредственно перед единицей (их и постулировать), а для больших отрицательных $n$ можно продолжить последовательность назад по той же рекуррентной формуле, и от этого часто есть польза, а от искусственного ограничения на применимость рекуррентной формулы как раз может быть вред.

[Andrey A]

arseniiv в сообщении #1426758 писал(а):

Кстати я бы снял условие $K_{<0} = 0...$

Да, я тоже думал об этом. Непригодность знакопеременных последовательностей — белое пятно на карте, как-то оно связано друг с другом. Но тогда количество композиций из отрицательного числа элементов должно получить толкование. Не очень пока помещается в голове.

arseniiv в сообщении #1426758 писал(а):

Андрей А в сообщении #1426758 писал(а):

Применимо ли это в численных методах решения уравнений?

То, как мы записываем уравнение? А какая разница.

Нет, имелось в виду вообще получение рациональных приближений вещественного корня (корней) через отношение членов рекуррентных последовательностей. Не обязательно соседних. В заявленном виде аппроксимация может оказаться медленной, числа — большими, гораздо больше элементов непрерывных дробей соотв. точности. Плюс — простота алгоритма.

arseniiv в сообщении #1426758 писал(а):

... написать куда более простое (но не уменьшающее общности!)

Допускаем ноль и приводим к стандартному виду, если правильно Вас понял. Это пожалуйста, как удобней.

Upd 28.08.2020

Andrey A в сообщении #1426762 писал(а):

Непригодность знакопеременных последовательностей — белое пятно на карте...

Исключение составляет знакопеременность вида $+ - + - + - . . .$ , соответствующая отрицательному корню. Если не ошибаюсь, аппроксимируется наибольший по абсолютной величине вещественный корень уравнения. Для уравнения $x^4+4x^3-4x^2-20x=5$ , к примеру, получаем последовательность

$\begin{matrix} \ n\ |& K\\ - - -&-------\\ \ 1\ |& -4\\ \ 2\ |& 20\\ \ 3\ |& -76\\ \ 4\ |& 309\\ \ 5\ |& -1160\\ \ 6\ |& 4456\\ \ 7\ |& -16664\\ \ 8\ |& 62825\\ \ 9\ |& -234636\\ 10\ |& 878844\\ 11\ |& -3280740\\ 12\ |& 12259741\\ 13\ |& -45758224\\ 14\ |& 170851280\\ 15\ |& -637646896\\ 16\ |& 2380126929\\ 17\ |& -88828608020\\ 18\ |& 33153269476 \end{matrix}$

Как видим, дроби, образованные соседними членами могут быть сократимы; $\gcd (K_{22},K_{23})=2184;\ \dfrac{K_{23}}{K_{22}}=-\dfrac{10990739225}{2944958071}$, что приближает корень уравнения $-2-\sqrt 3$ с точностью всего лишь в 6 дес. знаков. Excel перестает видеть погрешность аж к 47-му шагу. Такова плата за простоту.

[Andrey A]

Табличка Excel для удобства вычислений $k$-боначчи по заданным $k,n$ и нахождения нетривиальных решений для заданного $M$ (при наличии таковых).

[Руст]

У вас сомнительное малопригодное обобщение чисел Фибоначчи.
Я тоже немного занимался этим и дал другое определение обобщенных чисел Фибоначчи.
Пусть $X_n, n\ge 0, n\in Z_+$ последовательность, $f(x)=\sum_{i=0}^k a_ix^k$ - многочлен. Сопоставим $x$у оператор сдвига последовательности $X_n\to X_{n+1}$.
Тогда определено преобразование последовательностей $Y_n=f(X_n)=\sum_{i=0}^k a_iX_{n+i}$.
Берем фиксированный многочлен $f$ -го порядка и ограничимся последовательностями, удовлетворяющими уравнению

$$ (1) \ \ f(X_n)\equiv 0.$$

Они образуют конечномерное пространство, определенное начальными значениями $X_0,...X_{k-1}$.
Если $a_k=1$, то из того, что $X_i, i<k$ целые следует, что все значения целые.
Если $\varphi$ целочисленный полином и $X_n$ последовательность, удовлетворяющая уравнению (1),
то $Y_n=\varphi(X_n)$ так же удовлетворяет соотношению (1).
Если $Y_n=\varphi_1(X_n), Z_n=\varphi_2(Y_n)$, то $Z_n=\varphi (X_n)$, где $\varphi(x)=\varphi_1(x) \varphi_2(x)\mod f(x)$.
В дальнейшем будем считать, что все $a_i$ целые и $a_k=1, a_0\neq 0$.
Среди этих последовательностей выделяются два замечательных:
Последовательность Люка $V_n=\sum_{i=1}^k x_i^n$ и
последовательность Фибоначчи $U_n$ с начальными условиями $U_0=0,...,U_{k-2}=0, U_{k-1}=1.$
Для любой целочисленной последовательности $X_n$ из этого семейства (удовлетворяющего (1))
существует целочисленный многочлен ;$\varphi(x)$, что $X_n=\varphi(U_n). В частности, [math]$$V_n=f'(U_n).$$[/math]
Обратное $\Delta U_n=\varphi_1(V_n)$ -целочисленно с точностью до дискриминанта многочлена $f$.
Так вся теория c $k=2$ обобщается на общий случай. Я хочу таким образом улучшить теорему Рота.

[Andrey A]

Руст в сообщении #1491321 писал(а):

У вас сомнительное малопригодное обобщение чисел Фибоначчи.

Спасибо. Какое-никакое, но обсуждение. Способов обобщения может быть много, например, имея на руках пифагоровы тройки, можно вообразить пифагоровы четверки, пятерки, шестерки и т.д., но доблести в том немного. Последовательности Люка сами обобщают ряд Фибоначчи, вернее формулу Бине. Это удобно, понятно, этим мы пользуемся на практике, и сомнений в их пригодности не возникает. Детский вопрос: возможно ли перечислить все последовательности Люка, которым принадлежит заданное натуральное число? То же относительно Ваших последовательностей, я об них пока не думал, но интересно.
Ладно. По правде сказать, не было у меня искусственного намерения обобщать Фибоначчи. Я занимался континуантами и цепными дробями, и выяснилось, что они естественно принимают $k$-мерные формы. Об этом в конце темы. Единственная известная задача, решаемая с их помощью тут, остальное — тайна покрытая мраком. В сущности обобщено добытое Эйлером правило вычеркивания пар — оказалось, что можно вычеркивать $k$ соседних элементов. Тогда захотелось выписать "единичный случай", т.е. $k$-мерную дробь $1,1,1,1,...$ , что и описано в данной теме. По дороге выяснилось также, что последовательности эти, как и сама Фибоначчи, выражаются суммами элементов треугольника Паскаля, расположенных на прямой под некоторым рациональным углом. Если Ваши последовательности сохраняют данное свойство, могут быть интересные пересечения. Нет?
Ладно. Я понимаю, тема непопулярная $\Rightarrow $ малопригодная $\Rightarrow $ сомнительная. Возможно, Ваши идеи вызовут более оживленное обсуждение.

Изменено 10.11.2020

[Руст]

Если хотим получать новые мощные тесты на простоту или разложение действительного алгебраического числа в цепную дробь,
то так или иначе приходим к использованию этих чисел Фибоначчи и Люка (это мои названия по аналогии).
Тут на множестве таких последовательности естественным образом вводится структура кольца, являющегося факторкольцом по главному идеалу $(f)$.
Понятие целостности и т.д.