2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Фибоначчи k-го уровня
Сообщение08.09.2019, 20:11 


21/11/12
997
Санкт-Петербург
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
955
Adelaide, Australia
Ок можно увидеть решения для $M \leq 20$ ?

 Профиль  
                  
 
 Re: Фибоначчи k-го уровня
Сообщение10.09.2019, 00:03 


21/11/12
997
Санкт-Петербург
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
997
Санкт-Петербург
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
997
Санкт-Петербург
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
997
Санкт-Петербург
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
997
Санкт-Петербург
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
26689
Ну как, теория (однородных линейных рекуррентных уравнений) говорит, что если корни $\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
997
Санкт-Петербург
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
26689
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
997
Санкт-Петербург
arseniiv в сообщении #1426758 писал(а):
Кстати я бы снял условие $K_{<0} = 0...$

Да, я тоже думал об этом. Непригодность знакопеременных последовательностей — белое пятно на карте, как-то оно связано друг с другом. Но тогда количество композиций из отрицательного числа элементов должно получить толкование. Не очень пока помещается в голове.
arseniiv в сообщении #1426758 писал(а):
Андрей А в сообщении #1426758 писал(а):
Применимо ли это в численных методах решения уравнений?
То, как мы записываем уравнение? А какая разница.
Нет, имелось в виду вообще получение рациональных приближений вещественного корня (корней) через отношение членов рекуррентных последовательностей. Не обязательно соседних. В заявленном виде аппроксимация может оказаться медленной, числа — большими, гораздо больше элементов непрерывных дробей соотв. точности. Плюс — простота алгоритма.
arseniiv в сообщении #1426758 писал(а):
... написать куда более простое (но не уменьшающее общности!)

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

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

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



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

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


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

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