2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Фибоначчи k-го уровня
Сообщение07.10.2017, 15:23 


21/11/12
776
Санкт-Петербург
$F_1^{k}=F_2^{k}=...=F_k^{k}=1.$ Проще говоря, $k$ единиц являются начальными членами последовательности $F_n^{k}$. Начиная с $k+1$-го члена имеет место рекуррентное соотношение $F_n^{k}=F_{n-1}^{k}+F_{n-k}^{k}$. Привычные Фибоначчи - последовательность второго уровня $(k=2)$. Первого - $F_n^{1}=2^{n-1}$ (и самая быстрорастущая), ну а на третьем уровне последовательность коров Нараяны: $$F_n^{3}=1,1,1,2,3,4,6,9,13,19,28,41,60,88,129,189,277,406,595,872,1278,1873,...$$ Оказывается, задаче 700 лет. Отношение соседних Фибоначчи стремится к точке золотого сечения, предел отношения соседних коров $\approx 1,465571232$ тоже выражается в радикалах (см. Вики). Но чтобы продолжить список, пришлось бы зайти в Вольфрам и законспектировать приближенные значения положительных вещественных корней уравнения $x^k-x^{k-1}-1=0$ а у Нараяны не было Вольфрама! Вопрос: в какой строке $(k)$ и под каким номером $n$ встретится некоторое заданное натуральное число $M$? Ясно, что любое $M$ когда-нибудь да встретится, поскольку за $k$ начальными единицами в $k$-ой строке идут $k$ последовательных членов натурального ряда, но интересуют если не все вхождения, то хотя бы с наименьшим $k$.
Положим $F_n^{k}=M$ и $F_{n-1}^{k}=X$. Тогда дробь $\frac{M}{X}$ приближенно выражает нужную точку золотого сечения $k$-го уровня, и можно записать $\left( \frac{M}{X}\right)^k-\left( \frac{M}{X}\right)^{k-1}-1\approx 0$. Решая это уравнение относительно $k$, получаем $$k\approx \frac{ \lg M-\lg (M-X)}{ \lg M-\lg X}$$ Все $k$ близкие к целым точкам сразу попадают под подозрение, однако имеем перебор на интервале $\frac{M}{(1+\sqrt{5})/2} <X<M$, и лучшее приближение тоже ни о чем еще не свидетельствует. В случае $M=60$, к примеру, лучшее приближение $\frac{ \lg 60-\lg 23}{ \lg 60-\lg 37} \approx 2$, но $60$ не является числом Фибоначчи. Более того, даже разложение точки золотого сечения в непрерывную дробь снимает вопрос только в случае $k=2$. Для $k=3$ имеем $1,465571232 \approx \frac{1}{1},\frac{3}{2},\frac{19}{13},\frac{22}{15},\frac{85}{58},\frac{447}{305},\frac{1873}{1278},...$ Как видим, 4-я, 5-я и 6-я дроби дают более точное приближение, нежели соседние коровы. Проблема. Интересен также вопрос делимости членов указанных последовательностей, но этим пока не занимался.

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


21/11/12
776
Санкт-Петербург
P.S.
Смещая на единицу нижние индексы в формуле $F_n^{k}=F_{n-1}^{k}+F_{n-k}^{k}$, получаем $F_{n-1}^{k}=F_{n-2}^{k}+F_{n-k-1}^{k}$. Подстановка нового значения $F_{n-1}^{k}$ в первую формулу возвращает $F_n^{k}=F_{n-2}^{k}+F_{n-k}^{k}+F_{n-k-1}^{k}$. Совершая такую манипуляцию $k-2$ раз, получаем $F_n^{k}=F_{n-k+1}^{k}+F_{n-k}^{k}+F_{n-k-1}^{k}+...+F_{n-2k+2}^{k}$. Иными словами, сумма $k$ последовательных членов сама входит в последовательность $F_n^{k}$, на чем может быть основано альтернативное определение. Значит, на каждом уровне $>1$ имеется хотя бы одно треугольное число отличное от единицы, могут быть и другие. Например
$77=F_{32}^{11}=2+3+4+5+6+7+8+9+10+11$ или $341=F_{41}^{11}=11+12+14+17+21+26+32+39+47+56+66.$

Верно также $$\det\begin{pmatrix}
F_n^{4} & F_{n+1}^{4} & F_{n+2}^{4} & F_{n+3}^{4}\\ 
F_{n-1}^{4} & F_n^{4} & F_{n+1}^{4} & F_{n+2}^{4}\\ 
F_{n-2}^{4} & F_{n-1}^{4} & F_n^{4} & F_{n+1}^{4}\\ 
F_{n-3}^{4} & F_{n-2}^{4} & F_{n-1}^{4} & F_n^{4}
\end{pmatrix}=(-1)^{(n-1)(k-1)}$$ Не рисую в общем виде (что-то некрасиво получается), но имеется в виду определитель $k$-го порядка, в данном случае - четвертого. Это связано с темой http://dxdy.ru/post1244374.html#p1244374. Для $k=3$ имеем последовательность трехэтажных дробей (аналог подходящих дробей), каждые три столбца которых образуют единичный определитель третьего порядка:
$$\begin{matrix}
 & 1 & 2 & 3 & 4 & 6 & 9 & 13 & 19 & 28\ ... \\ 
 & 1 & 1 & 2 & 3 & 4 & 6 & 9 & 13 & 19\ ... \\ 
 & 1 & 1 & 1 & 2 & 3 & 4 & 6 & 9 & 13\ ... &
\end{matrix}$$ Такая дробь периодична и отображает точку золотого коровьего сечения, которая не является квадратичной иррациональностью.

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


21/11/12
776
Санкт-Петербург
P.S. P.S.
Члены последовательности $F_n^{k}$ представляют собой континуанты особого вида. Сумма одночленов, образованных вычеркиванием $k$ соседних членов из одночлена, все члены которого – единицы, есть количество композиций $n$ из $k$ и единиц. Об этом было здесь. Возникает гипотеза, которую не берусь строго доказать, но численно подтверждается:
Для конечного числа фиксированных $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$.

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


21/11/12
776
Санкт-Петербург
Еще закономерности: $$\sum\ F^{k}_n+1=F^{k}_{n+k}$$ $$\sum\limits_{i=0}^{n} F^{k}_{ki+m}=F^{k}_{kn+m+1}+0^m\ (m<k;0^0=1)$$ $$F^{k+1}_{n+1}=\sum\limits_{i=0} \binom{{n-ki}}{i}$$ Быстрый способ вычисления $k$-боначчи. Хотелось бы эту сумму упростить, вопрос вынесен в пр/р несколько в ином виде. Так же отсюда следуют тривиальные решения для фиксированного $M$: $$M=F^{M-t_n}_{2M-1-n^2}$$ где $t_n=\frac{n(n+1)}{2}$ ($n$-ая сумма натурального ряда), $n\leq \left \lfloor \frac{\sqrt{8M+1}-1}{2} \right \rfloor$.

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


21/11/12
776
Санкт-Петербург
Andrey A в сообщении #1260646 писал(а):
где $... t_n=\frac{n(n+1)}{2}$ ($n$-ая сумма натурального ряда), $n\leq \left \lfloor \frac{\sqrt{8M+1}-1}{2} \right \rfloor$.

Тут закралась ошибка, провисевшая больше года. Правильно будет так: $n\leq \left \lfloor \frac{\sqrt{8M+17}-3}{2} \right \rfloor$. Сформулирую получше что понимается под тривиальными решениями.

$1=F^{k}_{n}$ при условии $n \leqslant k$.

$M=F^{k=M+t}_{n=2M-1+t}$ ($t=0,1,2,...$)

$M=F^{ k=M-\frac{t(t+1)}{2}}_{n=2M-1-t^2}$ ( $0 < t \leqslant \left \lfloor \frac{\sqrt{8M+17}-3}{2} \right \rfloor $ ).

Тема суммирования биномиальных коэффициентов получила продолжение. Переношу сюда результат kthxbye
kthxbye в сообщении #1397841 писал(а):
$$\color
{blue}{\sum_{q=0}^m}&\color{blue}{\binom{n+(m-q)k}{q}}=\color{blue}{\sum_{q=0}^{\min(n,m)}}&\color{blue}{\binom{n}{q}a_k(m-q)}$$ где $$a_k(n)=\begin{cases}
0,&\text{если $n<0$;}\\
1,&\text{если $n=0$;}\\
\sum\limits_{p=0}^k\binom{k}{p}a_k(n-p-1),&\text{если $n>0$.}
\end{cases}$$


и пост Ms-dos4

Ms-dos4 в сообщении #1397996 писал(а):
Можно использовать представление биномиального коэффициента через вычеты
$C_n^k = {1 \over {2\pi i}}\int\limits_{\left| z \right| = \varepsilon } {{{{{(1 + z)}^n}} \over {{z^{k + 1}}}}dz}$
Тогда искомая сумма
$$\sum\limits_{j = 0}^m {C_{n + jk}^{m - j}}  = {1 \over {2\pi i}}\int\limits_{\left| z \right| = \varepsilon } {\sum\limits_{j = 0}^m {{{{{(1 + z)}^{n + jk}}} \over {{z^{m - j + 1}}}}} dz}  =  - {1 \over {2\pii}}\int\limits_{\left| z \right| = \varepsilon } {{{{{(z + 1)}^n}} \over {{z^{m + 1}}[z{{(z + 1)}^k} - 1]}}dz}  + {1 \over {2\pi i}}\int\limits_{\left| z \right| = \varepsilon } {{{{{(z + 1)}^{n + k(m + 1)}}} \over {z{{(z + 1)}^k} - 1}}dz}$$
Второй интеграл равен нулю, что окончательно даёт
$$\sum\limits_{j = 0}^m {C_{n + jk}^{m - j}}  = {1 \over {m!}}{\left. {{{{\partial ^m}} \over {\partial {z^m}}}[{{{{(z + 1)}^n}} \over {1 - z{{(z + 1)}^k}}}]} \right|_{z = 0}}$$
Если ещё постараться, возможно удастся выразить ответ через спецфункции (математика подсказывает, что ответ выражается через обобщенную гипергеометрическую функцию, но возиться лень).

Тривиальные решения соответствуют суммам $2$-х или $3$-х биномиальных коэффициентов, количество их для фиксированного $M$ бесконечно. Если создать таблицу значений $F^{(k)}_n$ ($n$ по оси $x$, $k$ по оси $y$), выделяя маркером ячейки $=M$, образуется воображаемая кривая, которая в точке $(2M-1;M)$ вырождается в прямую под углом $45^{\circ}$. Количество нетривиальных решений конечно. Возможно ли свести задачу $M=F^{(y)}_x$ к нахождению целых точек на некой алгебраической кривой – вот вопрос. Моей компетенции тут к сожалению не достаточно. Но несколько тривиальных точек справа всё же имеем. Для $M=56$, к примеру, получаем $t \leqslant \left \lfloor \frac{\sqrt{8\cdot 56+17}-3}{2} \right \rfloor=9$, и соответствующие решения $56=F^{11}_{30}=F^{20}_{47}=F^{28}_{62}=F^{35}_{75}=$$F^{41}_{86}=F^{46}_{95}=F^{50}_{102}=F^{53}_{107}=F^{55}_{110}$. Других в данном случае и нет, но для $M=55$ кроме восьми тривиальных решений получаем также $55=F^{6}_{20}=F^{2}_{10}$ , как их найти – самое интересное. Пока что представление суммой биномиальных коэффициентов плодотворно, но могут быть и другие подходы. Судите сами.

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


21/11/12
776
Санкт-Петербург
Всё-таки существует алгоритм для нахождения нетривиальных решений задачи $M=F^{y}_x$. Строится последовательность k-боначчи по простому правилу: если некоторый член последовательности превышает $M$ по величине, то следующий берется с сохранением верхнего индекса, нижний же уменьшается на единицу. В противном случае ($\leqslant M$) верхний индекс уменьшается на единицу, нижний – на двойку. Первым членом последовательности берется наименьшее тривиальное решение. Вычислять сами $k$-боначчи быстрее суммами биномиальных коэффициентов, впрочем это дело вкуса (при большом $M$ в конце возникают подпоследовательности соседних фибоначчи и степенней двойки, там это бессмысленно). Алгоритм конечен, но все ли нетривиальные решения охватываются таким способом – тому доказательств нет. Исключений тоже пока не нашел. Пример $M=60.$
$\left \lfloor \frac{\sqrt{8\cdot 60+17}-3}{2} \right \rfloor=9;\ 60-9\cdot 10/2=15;\ 60\cdot 2-1-9^2=38.$ Имеем последовательность $F^{38}_{15}=60,F^{36}_{14}=59,F^{34}_{13}=58,...,F^{24}_8=53,F^{22}_7=53,F^{20}_6=55,$ $F^{18}_5=60,F^{16}_4=69,F^{15}_4=50, F^{13}_3=60,F^{11}_2=89,$ $F^{10}_2=55,F^{8}_1=128,F^{7}_1=64,F^{6}_1=32$ и два нетривиальных решения: $F^{18}_5=F^{13}_3=60.$

Интересно, что каждое треугольное число, начиная с $n=6$, имеет нетривиальное решение: $t_n=F^{n-4}_{3n-10}$, а также $t_n-2=F^{n-3}_{3n-8}$. Достигнув разности $=1$ между соседними членами (как в начале примера), можно сразу опускаться до ближайшего треугольного числа. Видимо есть и другие возможности для ускорения процесса. Не мытьем так катаньем. Кое-что о треугольных числах было здесь.

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


21/11/12
776
Санкт-Петербург
Andrey A в сообщении #1399222 писал(а):
... можно сразу опускаться до ближайшего треугольного числа.

... до ближайшего треугольного числа, не превышающего $M+2.$ Тоже требует доказательств. Верно быть может для достаточно большого $M.$

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


30/01/06
69720
Andrey A в сообщении #1399222 писал(а):
Вычислять сами $k$-боначчи быстрее суммами биномиальных коэффициентов

Не понимаю, почему вы их не вычисляете экспонентами матриц.

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


21/11/12
776
Санкт-Петербург
Munin в сообщении #1399259 писал(а):
... экспонентами матриц.

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

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


30/01/06
69720
Из этого, как я понимаю, следует быстрота и лёгкость вычислений. Впрочем, дело ваше.

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


21/11/12
776
Санкт-Петербург
Munin в сообщении #1399280 писал(а):
... Впрочем, дело ваше.
Да, конечно.

Кое-что добавлю. Обозначим целое положительное число $\left \lfloor \frac{\sqrt{8M+17}-3}{2} \right \rfloor$ буквой $c$. Выбирая первым членом $F^{c-2}_{3c-5}$, заметно сокращаем количество вычислений, причем гарантированно выявляются только нетривиальные решения. Практика подсказывает, что отношение числа итераций к величине $M$ в этом случае убывает с ростом $M$, что важно. Но для $M<8$ алгоритм перестает работать, что не очень важно: нетривиальные решения на этом промежутке отсутствуют.
Для строгого доказательства корректности алгоритма пришлось бы чертить схемы, попробую выразиться всё же на словах. Представим таблицу значений $F^{k}_n$ с началом координат в левом верхнем углу ($n$ по оси $x$, $k$ по оси $y$), где ячейки равные некоторому фиксированному $M$ (решения) выделены маркером. Ясно, что при движении в право из любой точки значения ячеек не убывают. Верно так же, что при движении вниз значения ячеек не возрастают. Нетривиальные точки характеризуются неравенством $n/k>3$. Еще закономерность: если из нетривиальной точки ходить конём (диагональ 1:2, шаг вниз — два шага вправо), то всегда придешь в тривиальную точку, равную исходному значению, причем все промежуточные значения (если таковые имели место) меньше исходного. Выберем теперь верхнюю ячейку, помеченную маркером (наименьшее нетривиальное решение), проведем из неё воображаемую диагональ 1:2 и луч вправо вдоль строки. Образуется сектор, направленный вершиной к началу координат (сектор наименьшего решения). Все ячейки под диагональю численно $<M$. Вершина сектора следующего нетривиального решения расположена ниже, численно $=M$ и не может поэтому находиться под диагональю или на ней. Она внутри сектора наименьшего решения. Таким образом сектора всех нетривиальных решений оказываются вложенными друг в друга как матрешки. Правило же составлено так, что попав на луч или диагональ, воображаемый конь с них уже не сходит и, поскольку координаты его движения убывают, неминуемо проходит все точки решений. Тут скорее схема доказательства чем доказательство, но суть происходящего надеюсь ясна.

Еще раз. Первый член последовательности алгоритма $=F^{c-2}_{3c-5}$, где $c=\left \lfloor \frac{\sqrt{8M+17}-3}{2} \right \rfloor$. Каждый последующий член сохраняет верхний индекс предыдущего с уменьшением нижнего на единицу если предыдущий был $>M$. В противном случае ($\leqslant M$) верхний индекс уменьшается на единицу, нижний — на двойку. Такая последовательность содержит все нетривиальные решения уравнения $F_x^y=M.$ Тривиальные решения были тут
Andrey A в сообщении #1398300 писал(а):
$1=F^{k}_{n}$ при условии $n \leqslant k$.

$M=F^{k=M+t}_{n=2M-1+t}$ ($t=0,1,2,...$)

$M=F^{ k=M-\frac{t(t+1)}{2}}_{n=2M-1-t^2}$ ( $0 < t \leqslant \left \lfloor \frac{\sqrt{8M+17}-3}{2} \right \rfloor $ ).

Наименьшее $M$ с тремя нетривиальными решениями $=281.$

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


21/11/12
776
Санкт-Петербург
PS В пределах тысячи всего три числа, имеющих три нетривиальных решения: $281,533,769.$ Выписывая наименьшие k-боначчи, имеющие $N$ нетривиальных решений ($N=0,1,2,...$), получаем ряд $1,8,34,281,...$ Можно ли продолжить его до бесконечности? Получить бы еще пару-тройку членов, но тут вопрос к обладателям мат.пакетов.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 12 ] 

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



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

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


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

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