2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4  След.
 
 Re: Фибоначчи k-го уровня
Сообщение08.09.2019, 20:11 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
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$ имеем отсутствие нетривиальных решений.

 Профиль  
                  
 
 Re: Фибоначчи k-го уровня
Сообщение09.09.2019, 15:20 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Ок можно увидеть решения для $M \leq 20$ ?

 Профиль  
                  
 
 Re: Фибоначчи k-го уровня
Сообщение10.09.2019, 00:03 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
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.$
Спрашивайте, если что-то непонятно.

 Профиль  
                  
 
 Re: Фибоначчи k-го уровня
Сообщение10.09.2019, 07:50 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
PS Промашка вышла в первом примере. Правильно так: $16=F_{5}^1=F_{15}^6=F_{22}^{10}=F_{27}^{13}=F_{30}^{15}=F_{31+t}^{16+t}$

 Профиль  
                  
 
 Re: Фибоначчи k-го уровня
Сообщение10.09.2019, 16:58 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
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.$

 Профиль  
                  
 
 Re: Фибоначчи k-го уровня
Сообщение18.09.2019, 21:14 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
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}$$

 Профиль  
                  
 
 Re: Фибоначчи k-го уровня
Сообщение19.11.2019, 06:05 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
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}$. Однако, в случае приближенных вычислений имеем дело с накапливающейся ошибкой. Не пробовал.

 Профиль  
                  
 
 Re: Фибоначчи k-го уровня
Сообщение19.11.2019, 11:12 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Re: Фибоначчи k-го уровня
Сообщение19.11.2019, 12:17 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
arseniiv в сообщении #1426738 писал(а):
... эти $a_1, a_2, \ldots$, они ничем не увеличивают общность по сравнению с перебором всех чисел от $1$ до $a_m$

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

 Профиль  
                  
 
 Re: Фибоначчи k-го уровня
Сообщение19.11.2019, 13:00 
Заслуженный участник


27/04/09
28128
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$ можно продолжить последовательность назад по той же рекуррентной формуле, и от этого часто есть польза, а от искусственного ограничения на применимость рекуррентной формулы как раз может быть вред.

 Профиль  
                  
 
 Re: Фибоначчи k-го уровня
Сообщение19.11.2019, 14:07 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
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-му шагу. Такова плата за простоту.

 Профиль  
                  
 
 Re: Фибоначчи k-го уровня
Сообщение09.10.2020, 11:54 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Фибоначчи k-го уровня
Сообщение09.11.2020, 12:59 
Заслуженный участник


09/02/06
4382
Москва
У вас сомнительное малопригодное обобщение чисел Фибоначчи.
Я тоже немного занимался этим и дал другое определение обобщенных чисел Фибоначчи.
Пусть $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$ обобщается на общий случай. Я хочу таким образом улучшить теорему Рота.

 Профиль  
                  
 
 Re: Фибоначчи k-го уровня
Сообщение09.11.2020, 16:47 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
Руст в сообщении #1491321 писал(а):
У вас сомнительное малопригодное обобщение чисел Фибоначчи.

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

Изменено 10.11.2020

 Профиль  
                  
 
 Re: Фибоначчи k-го уровня
Сообщение09.11.2020, 20:10 
Заслуженный участник


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 54 ]  На страницу Пред.  1, 2, 3, 4  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group