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

[Andrey A]

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

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

Четырьмя постами выше приведен пример аппроксимации алгебраического числа отношением количества композиций. Очень просто, хотя и медленно. В параллельной теме описан вполне корректный алгоритм разложения радикала $k$-ой степени в цепную дробь. Целая часть кв. иррациональности, и ничего более. Это по поводу "так или иначе". Мало ли в мире идей, да и не стоит всё сводить к двум известным задачам; $k$-боначчи, во всяком случае, здесь действительно не причем.

[Andrey A]

Руст
Кое-что еще. Задача аналогичная поиску дискретного логарифма для последовательностей Люка вида ${\displaystyle \{U_{n}(P,-1)\}}$ (Википедия) решена здесь. Это можно обобщить и на последовательности ${\displaystyle \{U_{n}(P,Q)\}}$, если бы вопрос стоял остро, в чем не уверен. Теперь что касается разложения действительного алгебраического числа в цепную дробь. Тут, строго говоря, существует метод, вытекающий из самых общих положений. На сколько это пересекается с Вашими идеями — судите сами. Лучше на примере.

Возьмем многочлен $f_{x}=2x^5-3x^4+5x^3+7x^2-11x-13.$ Он имеет единственный вещественный корень $x_0$, и считаем, что целая часть $\left \lfloor x_0 \right \rfloor=1$ нам известна* $\left ( \dfrac{1}{1}<x_0<\dfrac{2}{1} \right ).$ Первая дробь образует первое нижнее приближение (будем помечать это знаком "-") и является первой подходящей дробью по определению. Вторая дробь ("+") не факт что подходящая, но удовлетворяет основному свойству подходящих дробей: $p_2q_1-p_1q_2=(-1)^2.$ Третьим шагом берем медианту $\dfrac{1+2}{1+1}=\dfrac{3}{2}$ и проверяем ее на избыточность/недостаточность: $f_{\frac{3}{2}}>0.$ Метим ее знаком (+). Два плюса к ряду, значит вторая дробь не была подходящей. По терминологии А.Я.Хинчина это "промежуточная дробь". Далее простое правило: новая медианта строится из последней полученной дроби и последней дроби противоположного ей знака. В данном случае так: $\dfrac{1+3}{1+2}=\dfrac{4}{3};\ f_{\frac{4}{3}}<0.$ Знак изменился, значит $\dfrac{3}{2}$ была подходящей, и следующую медианту строим из двух новообразованных$: \dfrac{3+4}{2+3}=\dfrac{7}{5}$ ну, и т.д. Собственно, и всё. Хотел выписать в таблицу, да надо ли? Подходящие возникают на смене знаков, протяженность серий последовательных плюсов и минусов соответствуют как раз знакам цепной дроби. Число итераций — сумма знаков цепной дроби. Excel'я в данном случае хватает на $19$ знаков, что соответствует приближению $x_0 \approx \dfrac{10530331}{7322306}.$ Алгоритм простейший, требует только возможности грубого сравнения больше/меньше, что для алгебраических чисел как раз не проблема.

Очевидный недостаток заключен в необходимости перебирать промежуточные дроби. В вышеупомянутом алгоритме разложения радикала степени $k$ эта проблема решена, однако требуется точное знание параметра $z_n$, который растет. Если бы удалось "малой кровью" решить вопрос по какую сторону от нуля находится величина, заданная тем или иным способом (в данном случае полиномом), описанный алгоритм мог бы оказаться предпочтительней за счет простоты и универсальности. Упускать его из виду во всяком случае не стоит. Задача: не вычисляя суммы, оценить ее с точностью до полуоси )

*На единичном интервале может оказаться более одного вещественного корня.
Тогда потребуется несколько бо́льшая стартовая точность, но смысл тот же.

Upd 16.02.2021
Описанный процесс подобен двоичному поиску с той разницей, что вместо деления на $2$ берется медианта границ соотв. отрезка числовой оси. Для начала процесса не обязательно знать целую часть $x_0$, достаточно пары рациональных точек на оси абсцисс, между которыми $x_0$ расположен, но только он. Требование вполне понятное, надо же как-то указать какой именно корень подлежит аппроксимации. Алгоритм всё тот же, хотя числители и знаменатели образованных дробей поначалу не обязательно вз. просты. Если не забывать их сокращать, с какого-то момента достигается состояние $p_nq_{n-1}-p_{n-1}q_n=\pm 1,$ и "входим в зону" собственно непрерывной дроби. Далее на смене знаков узнаем подходящую, ее разложение соответствует начальным знакам разложения $x_0.$

[Руст]

Рациональные приближения $\frac{P_n}{Q_n}$ любой цепной дроби удовлетворяют соотношению

$$(P_n,Q_n) =q_n(P_{n-1},Q_{n-1})+(P_{n-2},Q_{n-2}).$$

Для алгебраического числа, являющегося корнем неприводимого уравнения

$$f(x)=\sum_{i=0}^k a_ix^{k-i}=0=z^kf(\frac{y}{z})=f_0(y,z)$$

хотелось бы найти как формируются числа $q_n$.
Предварительно модулярным преобразованием $x'=\frac{ax+b}{cx+d}, ad-bc=\pm 1$ сделаем искомый корень максимальным по абсолютной величине. Числа отличающиеся таким преобразованием имеют одинаковое разложение в цепную дробь после некоторого начала. Можно считать, что неприводимое уравнение задано уже для преобразованной величины.
Если уже найдены $(P_n,Q_n),(P_{n-1},Q_{n-1})$, то $\Delta_n=f_0(P_n,Q_n)f_0(P_{n-1},Q_{n-1})<0$ и $q_n$
выбирается как минимальное натуральное, такое что $\Delta_{n+1}<0$. Имеем

$$f_0(P_{n+1},Q_{n+1})=Q_{n+1}^k f(\frac{P_{n+1}}{Q_{n+1}})\approx Q_{n+1}^k [f(\frac{P_n}{Q_n})+\frac{(-1)^n}{Q_nQ_{n+1}}f'(\frac{P_n}{Q_n})].$$

Отсюда можно найти $q_{n+1}$. Для вычислений это годится. Однако, это еще не решает вопрос о структуре и об оценке значений $q_n$ при всех $n$.

[Andrey A]

Простите, я не очень понимаю Вашу терминологию. Если $q_n,q_{n+1}$ — знаки самой дроби, тогда да, мне тоже хотелось бы найти как формируются числа $q_n$, это означало бы найти алгоритм разложения алгебраического числа. В том что он существует, кстати, сомнений не возникает, как и в том что количество связанных с этим вычислений постепенно снижает эффект до минимума. Если бы их было просто много, еще ладно, но дело в постоянно возрастающем параметре, который при вычислении целой части чего-бы-то-ни-было всегда оказывается в знаменателе, поэтому знать его нужно точно. Чем с менее осязаемыми иррациональностями имеем дело, тем более нуждаемся в простом методе, отчего и выложил выше одноклеточный алгоритм. Как вариант. Впрочем, тут могу ошибаться. По поводу непериодических структур совсем ничего не скажу. Дело темное.

[Andrey A]

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

В том что он существует, кстати, сомнений не возникает...

Да, существует. Подобные алгоритмы похожи на цепную реакцию, для начала которой нужны некие стартовые условия, что-то вроде капсюля. Или пусть лучше будет керосин для розжига костра — пара подходящих дробей достаточной точности. Часто хватает первых двух, но не факт что всегда. В случае алгебраического числа можно воспользоваться вышеописанным способом разложения и взять с запасом. Точный порог указать не берусь, но и проблемы в том нет, поскольку ошибку в непрерывных дробях пропустить невозможно. И так, пусть $x$ вещественный корень уравнения $ax^3+bx^2+cx+d=0$, и известны первые $n$ знаков разложения $x \approx \dfrac{p_{n-1}}{q_{n-1}},\dfrac{p_n}{q_n}.$ Задача сводится к нахождению $(n+1)$-го знака $a_{n+1}.$ Тогда становится возможным получить $(n+1)$-ю подходящую дробь по формуле $\dfrac{p_{n+1}=a_{n+1}p_n+p_{n-1}}{q_{n+1}=a_{n+1}q_n+q_{n-1}}$ и продолжить процесс по кругу до нужного предела. Величина $a_{n+1}$ есть целая часть $(n+1)$-го остатка дроби $r_{n+1}$, который, имея $x$ на руках, можно было бы вычислить по формуле

$$r_{n+1}=-\dfrac{p_{n-1}-xq_{n-1}}{p_n-xq_n}$$

Преобразуем это выражение так: $r_{n+1}=-\dfrac{p_{n-1}-xq_{n-1}}{p_n-xq_n}=\dfrac{q_{n-1}}{q_n} \cdot \dfrac{x-\frac{p_{n-1}}{q_{n-1}}}{\frac{p_n}{q_n}-x}=$ $\dfrac{q_{n-1}}{q_n} \left ( \dfrac{\frac{p_n}{q_n}-\frac{p_{n-1}}{q_{n-1}}}{\frac{p_n}{q_n}-x}-1 \right )=$ $\dfrac{q_{n-1}}{q_n} \left ( \dfrac{(-1)^n}{q_nq_{n-1}\left ( \frac{p_n}{q_n}-x \right )}-1 \right )=$ $\dfrac{(-1)^n}{q_n(p_n-xq_n)}-\dfrac{q_{n-1}}{q_n}\ \ \ (1).$

Теперь запишем:
$\dfrac{ax^3+bx^2+cx+d}{\frac{p_n}{q_n}-x}+ax^2+bx+c=\dfrac{ax^2\frac{p_n}{q_n}+bx\frac{p_n}{q_n}+c\frac{p_n}{q_n}+d}{\frac{p_n}{q_n}-x}.$

$\dfrac{ax^3+bx^2+cx+d}{\frac{p_n}{q_n}-x}+ax^2+bx+c+ax\frac{p_n}{q_n}+b\frac{p_n}{q_n}=$ $\dfrac{ax^2\frac{p_n}{q_n}+bx\frac{p_n}{q_n}+c\frac{p_n}{q_n}+d}{\frac{p_n}{q_n}-x}+ax\frac{p_n}{q_n}+b\frac{p_n}{q_n}=\dfrac{ax\left ( \frac{p_n}{q_n} \right )^2+b\left ( \frac{p_n}{q_n} \right )^2+c\frac{p_n}{q_n}+d}{\frac{p_n}{q_n}-x}.$

$\dfrac{ax^3+bx^2+cx+d}{\frac{p_n}{q_n}-x}+ax^2+bx+c+ax\frac{p_n}{q_n}+b\frac{p_n}{q_n}+a\left ( \frac{p_n}{q_n} \right )^2$ $=...=\dfrac{a\left ( \frac{p_n}{q_n} \right )^3+b\left ( \frac{p_n}{q_n} \right )^2+c\frac{p_n}{q_n}+d}{\frac{p_n}{q_n}-x}.$

И, поскольку первая дробь в начале строк нулевая, получаем $\dfrac{p_n}{q_n}-x=\dfrac{a\left ( \frac{p_n}{q_n} \right )^3+b\left ( \frac{p_n}{q_n} \right )^2+c\frac{p_n}{q_n}+d}{a \left ( x^2+x\frac{p_n}{q_n}+\left ( \frac{p_n}{q_n} \right )^2 \right )+b \left ( x+\frac{p_n}{q_n} \right )+c}$ или $q_n(p_n-xq_n)=\dfrac{ap_n^3+bp_n^2q_n+cp_nq_n^2+dq_n^3}{q_n \left ( a \left ( x^2+x\frac{p_n}{q_n}+\left ( \frac{p_n}{q_n} \right )^2 \right )+b \left ( x+\frac{p_n}{q_n} \right )+c \right )}$ (домножая почленно на $q_n^2$).

Подставляя это в $(1)$, получаем $r_{n+1}=\dfrac{(-1)^nq_n \left ( a \left ( x^2+x\frac{p_n}{q_n}+\left ( \frac{p_n}{q_n} \right )^2 \right )+b \left ( x+\frac{p_n}{q_n} \right )+c \right )}{ap_n^3+bp_n^2q_n+cp_nq_n^2+dq_n^3}-\dfrac{q_{n-1}}{q_n}.$

Таким образом удается избавиться от иррациональности в знаменателе, хотя и несколько неуклюже. Главное, числитель теперь можно брать приближенно. Поменяв иксы на наиболее точные к моменту $n$ приближения $\left ( x \approx \dfrac{p_n}{q_n} \right )$, получаем вполне компактное выражение $r_{n+1}\approx \dfrac{cq_n^2+2bp_nq_n+3ap_n^2}{dq_n^3+cp_nq_n^2+bp_n^2q_n+ap_n^3} \cdot \dfrac{(-1)^n}{q_n}-\dfrac{q_{n-1}}{q_n}.$ Остается продолжить это на многочлен степени $k.$





Пусть $x$ вещественный корень многочлена $f_x=c_0+c_1x^1+c_2x^2+...+c_kx^k$, и известны первые $n$ знаков разложения $x \approx \dfrac{p_{n-1}}{q_{n-1}},\dfrac{p_n}{q_n}.$ Тогда, если $n$ не слишком мало, выполняется:

$$a_{n+1}=\left \lfloor \dfrac{c_1q_n^{k-1}+2c_2p_nq_n^{k-2}+3c_3p_n^2q_n^{k-3}+...+(k-1)c_{k-1}p_n^{k-2}q_n+kc_kp_n^{k-1}}{c_0q_n^k+c_1p_nq_n^{k-1}+c_2p_n^2q_n^{k-2}+...+c_{k-1}p_n^{k-1}q_n+c_kp_n^k} \cdot \dfrac{(-1)^n}{q_n}-\dfrac{q_{n-1}}{q_n} \right \rfloor$$

Тут нужно себя похвалить: проще выражения для такого случая и представить трудно. Беглая проверка обнадеживает. Если не найдется желающих протестировать формулу, выложу позже табличку Excel.

Еще проще, кстати, это выражается через рациональное $R_n=\dfrac{p_n}{q_n}: $

$$a_{n+1}=\left \lfloor \dfrac{c_1+2c_2R_n+3c_3R_n^2+...+kc_kR_n^{k-1}}{f_{R_n}} \cdot \dfrac{(-1)^n}{q_n^2}-\dfrac{q_{n-1}}{q_n} \right \rfloor$$

Upd 10.12.2020
Всё не так просто. Иные уравнения гладко идут, но не все. Возможно, вместо $x$ следовало подставить не $\dfrac{p_n}{q_n}$, а $\dfrac{p_{n-1}}{q_{n-1}}$, чтобы верхние приближения компенсировались нижними, но выражения тогда выйдут значительно сложнее. Дело в том еще, что в Excel толком ничего не проверить. Штормит. Не надо мне было хвастаться раньше времени.

[Andrey A]

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

... разложение действительного алгебраического числа в цепную дробь

Разложение алгебраического числа 2.xlsx ссылка для скачивания.

Алгоритм работает корректно, но задача явно не для Excel (отчего и происходят мозоли). Всё что смог. Незаинтересованность программистов — вот для меня загадка (если это действительно серьезная задача).


Upd Файл отредактирован 28.01.2021. Добавлено разложение логарифма.

[Andrey A]

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

Точный порог указать не берусь...

Всё-таки тут нужно больше ясности. Уравнение пятой степени $x^5-2x^4+3x^3-5x^2+7x-7858=0$ требует "для разгона" шесть знаков, т.е. $k+1$. Такого примера достаточно одного — меньшим теоретический порог быть не может. Предположу, что и больше знаков не понадобится, поскольку начиная с $k+1$ для знаменателя исследуемой дроби начинает работать рекуррентное правило, описанное в параллельной теме (радикалы степени k). То есть информации становится достаточно, и подозреваю что это тот же самый порог. Для числителя, кстати, рекуррентное правило тоже работает, поскольку однородный многочлен степени $k-1$ с постоянными коэффициентами, но в Excel этого делать не стал (файл отредактирован). Экспоненциальной точности для числителя хватает, ну, и вообще там всё немножко игрушечное. Если насчет $k+1$ ошибаюсь — что ж, вернуться к "одноклеточному алгоритму" на старте никогда не поздно.

[Andrey A]

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

$$a_{n+1}=\left \lfloor \dfrac{c_1+2c_2R_n+3c_3R_n^2+...+kc_kR_n^{k-1}}{f_{R_n}} \cdot \dfrac{(-1)^n}{q_n^2}-\dfrac{q_{n-1}}{q_n} \right \rfloor$$

Это выражение удается записать еще лаконичней с помощью знака производной: $a_{n+1}=\left \lfloor \dfrac{f'_{R_n}}{f_{R_n}} \cdot \dfrac{(-1)^n}{q_n^2}-\dfrac{q_{n-1}}{q_n} \right \rfloor.$ Возникает гипотеза. Авантюрная, но ничто не мешает ее проверить. Возьмем $\log_bc.$ В общем случае логарифм не является алгебраическим числом, но является корнем уравнения $b^x-c=0.$ Пусть $f_x=b^x-c,$ тогда $f'_x=b^x \ln b$. Если пара подходящих дробей входит в разложение $\log_bc \approx \dfrac{p_{n-1}}{q_{n-1}},\dfrac{p_n}{q_n},...\ ,$ можно взять $\dfrac{p_n}{q_n}=R_n$ и предположить по аналогии $a_{n+1}=\left \lfloor \dfrac{b^{R_n} \ln b}{b^{R_n}-c} \cdot \dfrac{(-1)^n}{q_n^2}-\dfrac{q_{n-1}}{q_n} \right \rfloor,$ или так: $a_{n+1}=\left \lfloor \ln b \left ( 1+\dfrac{c}{b^{R_n}-c} \right ) \cdot \dfrac{(-1)^n}{q_n^2}-\dfrac{q_{n-1}}{q_n} \right \rfloor.$ Получаем разложение логарифма в непрерывную дробь. Правда, первым множителем стоит $\ln b$, который сам вроде бы требует разложения. Но он вне знаменателя, и взятый с некоторой точностью может быть принят за константу. Можно, конечно, организовать двойное разложение или наоборот положить $b=e,\ln b=1$. В конце концов, вопрос не в разложении логарифма, а в справедливости гипотезы. Последнее пока что подтверждается численно. На всякий случай вставил страницу с разложением логарифма в файл excel выше, но его (excel'я) редко хватает даже на 20 знаков, а рекурсивные "методы поддержки" тут уже не работают. Сформулирую еще раз гипотезу. Конечно, она нуждается в более основательной проверке или опровержении.


ФОРМУЛИРОВКА:
Пусть \large $x_0=a_1,a_2,...,a_n,... \approx \dfrac{p_{n-1}}{q_{n-1}},\dfrac{p_n}{q_n},...$ есть вещественный корень уравнения, выраженного некоторой дифференцируемой функцией \large $f_x$ с нулем в правой части равенства. Тогда, начиная с некоторого $n$, выполняется

\large $$a_{n+1}=\left \lfloor \dfrac{f'_{R_n}}{f_{R_n}} \cdot \dfrac{(-1)^n}{q_n^2}-\dfrac{q_{n-1}}{q_n} \right \rfloor\ \ (2),$$

где \large $R_n=\dfrac{p_n}{q_n}.$ Если это верно, становится возможным получить \large $(n+1)$-ю пару подходящих дробей по формуле \large $\dfrac{p_{n+1}=a_{n+1}p_n+p_{n-1}}{q_{n+1}=a_{n+1}q_n+q_{n-1}}$, тем же способом вычислить \large $a_{n+2}$ и продолжить далее по кругу, что составляет алгоритм разложения \large $x_0$ в непрерывную дробь.

___________________________________________

Upd 30.01.
$\sin x$ отлично работает, но только для $0<x<\pi/2.$ Это удается обойти по $\mod \pi/2$, но с периодическими функциями пока неясно.

Upd 31.01.
C периодическими функциями всё в порядке, тут издержки невнимательного программирования. Важно помнить, что знаменатель дроби $\dfrac{f'_{R_n}}{f_{R_n}}$ суть погрешность аппроксимации к моменту $n$ — постоянно убывающая знакопеременная величина. Для разложения $\sin x$ знаменатель $f_{R_n}=\arcsin \dfrac{p_n}{q_n}-x$, поэтому $x$ должен быть взят по $\mod \pi$ на интервале $(-\pi/2,\pi/2)$, тогда всё встает на места. Практической пользы от вычислений в таком виде немного (поскольку арксинус всё равно вычисляется программными средствами), но гипотезу подтверждает хорошо.

Отредактировано 8.05.2021

Upd 8.11.2021

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

Если это верно...

Выражение в скобках "пол" формулы $(2)$ суть $n$-ое приближение $(n+1)$-ого остатка дроби $r_{n+1}.$ Если $x_0$ — корень исследуемого уравнения, можем приравнять $r_{n+1}=-\dfrac{p_{n-1}-x_0q_{n-1}}{p_n-x_0q_n}\approx \dfrac{f'_{R_n}}{f_{R_n}} \cdot \dfrac{(-1)^n}{q_n^2}-\dfrac{q_{n-1}}{q_n}.$ Обозначим $\alpha =\dfrac{f'_{R_n}}{f_{R_n}}$ и сделаем преобразования:
$\alpha \approx \left ( -\dfrac{p_{n-1}-x_0q_{n-1}}{p_n-x_0q_n}+\dfrac{q_{n-1}}{q_n} \right ) \cdot q_n^2 \cdot (-1)^n=$ $\dfrac{p_nq_{n-1}-x_0q_nq_{n-1}-p_{n-1}q_n+x_0q_nq_{n-1}}{q_n(p_n-x_0q_n)} \cdot q_n^2 \cdot (-1)^n=$ $\dfrac{(p_nq_{n-1}-p_{n-1}q_n) \cdot (-1)^n}{q_n(p_n-x_0q_n)} \cdot q_n^2=$ $\dfrac{q_n}{p_n-x_0q_n}.$ Разделив числитель и знаменатель последней дроби на $q_n$, получаем $\alpha \approx \dfrac{1}{\dfrac{p_n}{q_n}-x_0},$ откуда $\dfrac{1}{\alpha } \approx \dfrac{p_n}{q_n}-x_0$ и $x_0 \approx R_n-\dfrac{f_{R_n}}{f'_{R_n}}.$ Далее избавляемся от знака $, взяв вместо $x_0$ его $(n+1)$-ое приближение $R_{n+1}$. В итоге получаем

$$R_{n+1}=R_n-\dfrac{f_{R_n}}{f'_{R_n}}$$

в полном согласии с "методом касательных" Ньютона, из которого заявленная гипотеза может быть выведена обратными преобразованиями. И, собственно, перестает быть гипотезой. Открытым остается вопрос из следующего сообщения. Схема та же, только вместо $R_{n+1}$ оказывается возможным $R_{n+i}=R_n-\dfrac{f_{R_n}}{f'_{R_n}}.$ Но каково $i_{\max}$ для конкретных случаев остается загадкой.

[Andrey A]

Пронумерую задним числом

$$a_{n+1}=\left \lfloor \dfrac{f'_{R_n}}{f_{R_n}} \cdot \dfrac{(-1)^n}{q_n^2}-\dfrac{q_{n-1}}{q_n} \right \rfloor\ \ \ (2)$$

Для алгебраических уравнений операции сводятся к целочисленным, кроме того имеет место рекуррентная зависимость для последовательности числителей и знаменателей дроби $\dfrac{f'_{R_n}}{f_{R_n}}$, описанная в параллельной теме, что также упрощает дело. Но в остальных случаях вычисление $(2)$ может превратиться в отдельную задачу, решаемую по обстоятельствам (например, через вычисление логарифмической производной). Не вдаваясь в подробности, обращу внимание на важную деталь: "подслеповатость" алгоритма на начальных шагах имеет свою обратную сторону. Если $n$ достаточно велико, то, отменив скобочки $\left \lfloor \ \right \rfloor$ в выражении $(2)$, из него можно получить не один знак дроби, коим и является целая часть, а несколько. Чтобы воспользоваться этим в полной мере, однако, надо знать точное количество верных знаков для конкретного случая, тогда алгоритм усиливается на порядок. Целая часть корня уравнения нам априори не известна. Обозначим это символом "ноль" и будем записывать далее в строку максимально возможное количество знаков цепной дроби, на которую способен алгоритм к моменту $n$.
Для корня $x_0\approx 1,63987969...$ уравнения $2x^5+9x^4+6x^3-7x^2+4x-103=0$ получаем последовательность: $0,0,0,1,1,1,3,4,4,8,10,12,13,12,13,14,…$ Для разложения $\tg16^\circ \approx 0,28674539...$ она такая: $0,1,1,4,6,6,6,6,10,10,...$
По мере "ухудшения вычислимости" $(2)$ полезность данного свойства становится очевидной, знать бы где остановиться. Знакомая уже ситуация на новом уровне. А так приходится делать пошаговые проверки. Я даже не уверен, что указанные последовательности возрастают. Думаю, для подобных вопросов лучше создать отдельную тему в разделе "программирование", если речь зайдет о практическом применении.

Исправлено 21.04

[Dmitriy40]

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

Возьмем число побольше и ограничимся поиском нетривиальных решений, 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^{1}_{9}=256<281.$ Конец. Три нетривиальных решения. Полное решение запишем дробями:
[...]
Вычислять $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 в сообщении #1399425 писал(а):

PS В пределах тысячи всего три числа, имеющих три нетривиальных решения: $281,533,769.$

Написал программу по Вашему алгоритму, она за секунду нашла 4 решения:

Используется синтаксис Text

M=281: n=3: F(18,57) F(15,50) F(8,32)
M=406: n=3: F(24,74) F(20,65) F(3,18)
M=533: n=3: F(27,84) F(13,49) F(6,29)
M=769: n=3: F(31,98) F(21,73) F(18,65)

Проверьте пожалуйста что $M=406$ действительно даёт 3 решения и не ошибся ли я где.

Программа на удивление простая, на PARI/GP:

F(u,d)=my(i,s=0); for(i=0,oo, if(i*u>d-1, break); s+=binomial(d-1-(u-1)*i,i)); s;\\Вычисление F(u,d)
{for(M=9,10^3,\\Цикл по искомому числу
   c=floor((sqrt(8*M+17)-3)/2); u=c-2; d=3*c-5; n=[];\\Начальные значения
   while(u>0,\\Пока верхний индекс не обнулился будем искать
      x=F(u,d);
      if(x==M, n=concat(n,[[u,d]]));\\Найдено решение, добавим его к списку
      if(x>M, d--, u--; d-=2);\\Если больше то уменьшаем нижний, иначе (меньше или равно) уменьшаем оба
   );
   if(#n>0,\\Если найдено хоть что-то, то выведем красиво
      printf("M=%d: n=%d:",M,#n);
      for(i=1,#n, printf(" F(%d,%d)",n[i][1],n[i][2]));
      print;
   );
)}

Всё вычисление в трёх строках цикла while, остальное формирование удобного вывода результатов и цикл по $M$.

До $M<10^4$ считала 12с и нашла 8 решений длиной 4:

Используется синтаксис Text

M=2490: n=4: F(65,198) F(60,187) F(36,125) F(9,46)
M=3431: n=4: F(75,230) F(71,221) F(64,204) F(29,109)
M=5900: n=4: F(102,310) F(89,280) F(87,275) F(80,257)
M=6326: n=4: F(109,328) F(101,311) F(93,292) F(44,159)
M=6903: n=4: F(113,341) F(92,292) F(62,211) F(57,197)
M=8569: n=4: F(99,316) F(83,273) F(79,262) F(18,85)
M=8800: n=4: F(120,369) F(112,350) F(41,155) F(20,92)
M=9589: n=4: F(135,406) F(123,380) F(118,368) F(34,136)

При дальнейшем счёте до $M<10^5$ за 7 минут нашлись и решения длиной 5:

Используется синтаксис Text

M=17051: n=5: F(158,492) F(149,469) F(119,388) F(54,203) F(31,135)
M=55628: n=5: F(318,966) F(303,931) F(293,906) F(272,851) F(103,371)
M=60059: n=5: F(339,1022) F(318,975) F(286,893) F(103,373) F(73,285)
M=66444: n=5: F(358,1078) F(329,1012) F(308,958) F(240,771) F(168,565)
M=70876: n=5: F(372,1118) F(312,973) F(279,883) F(260,830) F(168,567)
M=96578: n=5: F(436,1309) F(412,1257) F(342,1074) F(228,751) F(108,401)
M=98951: n=5: F(409,1253) F(399,1228) F(348,1092) F(326,1031) F(150,525)

-- 14.03.2021, 05:48 --

За два часа счёта нашлись и решения длиной 6:

Используется синтаксис Text

M=243676: n=6: F(676,2046) F(594,1838) F(488,1542) F(453,1442) F(384,1243) F(126,486)
M=300728: n=6: F(768,2309) F(728,2219) F(673,2076) F(427,1379) F(233,811) F(142,542)
M=572851: n=6: F(1024,3108) F(874,2708) F(654,2079) F(467,1533) F(451,1486) F(399,1333)
M=672076: n=6: F(1112,3373) F(1074,3278) F(859,2683) F(614,1974) F(601,1936) F(201,756)

Ради интереса сейчас перепишу программу на асме (ибо нефик) и посмотрю на скорость счёта ...

[Andrey A]

Dmitriy40 в сообщении #1509127 писал(а):

... она за секунду нашла 4 решения:

Да, там был недочет, который исправлять не стал, видя нулевой интерес к теме. Но в файле Excel решение $M=406$ упомянуто. Думаю, настоящий интерес для комп. вычислений может представлять последовательность "чемпионов": $1,8,34,281,2490,17051,...$ т.е. наименьшие $M$, для которых существует последовательно $0,1,2,...$ и т.д. нетривиальных решений. В OEIS этой последовательности нет.
По поводу нетривиальности много писано, а надо было просто $n/k>3$ — свойство, которым обладают порядка $1/3$ натуральных чисел. Для OEIS "последовательность чемпионов" можно сформулировать так: последовательность наименьших натуральных чисел, представимых $n$ способами в виде суммы более чем $3$-х элементов треугольника Паскаля, "расположенных" на одной прямой. Кавычки поясняют, что под элементом понимается точка в массиве, а не что-то иное.

P.S. Ага, вот уже вижу у Вас $7$-й член $243676.$ Интересно, что количество десятичных знаков $=n-1$. Долго ли это может продолжаться?

[Dmitriy40]

3ч переписывания программы (из них около 2ч ушло только на биномиальные коэффициенты) и вместо 3.5ч работы PARI/GP она досчитала до $M<10^6$ за жалкие 45с, в 270 раз быстрее. Вот список всех решений до $M<10^6$ от 6 и длиннее:

Используется синтаксис Text

M=243676: n=6: F(676,2046) F(594,1838) F(488,1542) F(453,1442) F(384,1243) F(126,486)
M=300728: n=6: F(768,2309) F(728,2219) F(673,2076) F(427,1379) F(233,811) F(142,542)
M=572851: n=6: F(1024,3108) F(874,2708) F(654,2079) F(467,1533) F(451,1486) F(399,1333)
M=672076: n=6: F(1112,3373) F(1074,3278) F(859,2683) F(614,1974) F(601,1936) F(201,756)
M=806821: n=6: F(1243,3752) F(1210,3675) F(1156,3536) F(1150,3520) F(1127,3458) F(827,2608)
M=826253: n=7: F(1282,3847) F(1143,3506) F(968,3016) F(818,2584) F(523,1721) F(322,1127) F(293,1041)
M=840701: n=6: F(1259,3808) F(1189,3633) F(1099,3388) F(914,2863) F(683,2192) F(544,1784)
M=847301: n=6: F(1287,3873) F(1226,3731) F(1060,3280) F(994,3093) F(959,2993) F(209,793)
M=882078: n=6: F(1308,3941) F(1292,3906) F(1257,3822) F(1056,3274) F(937,2934) F(292,1042)

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

P.S. Ага, вот уже вижу у Вас $7$-й член $243676.$ Интересно, что количество десятичных знаков $=n-1$. Долго ли это может продолжаться?

Беда :

Используется синтаксис Text

M=826253: n=7: F(1282,3847) F(1143,3506) F(968,3016) F(818,2584) F(523,1721) F(322,1127) F(293,1041)
M=5298424: n=8: F(3208,9665) F(3196,9638) F(3124,9462) F(3089,9371) F(2966,9038) F(2573,7923) F(2529,7796) F(1360,4366)

-- 14.03.2021, 09:44 --

Досчиталось до $M<10^7$, приведу все решения длиной не менее 7 (нашлись 3шт длиной 8):

Используется синтаксис Text

M=826253: n=7: F(1282,3847) F(1143,3506) F(968,3016) F(818,2584) F(523,1721) F(322,1127) F(293,1041)
M=2147628: n=7: F(2068,6206) F(1957,5947) F(1847,5651) F(1821,5579) F(1253,3946) F(1058,3374) F(968,3109)
M=2801380: n=7: F(2330,7022) F(2265,6867) F(2085,6382) F(1932,5950) F(1875,5787) F(1056,3395) F(377,1380)
M=2805776: n=7: F(2339,7043) F(2269,6878) F(1973,6067) F(1489,4668) F(1038,3342) F(519,1803) F(477,1678)
M=3369101: n=7: F(2490,7545) F(2387,7273) F(2349,7169) F(2251,6896) F(1674,5233) F(1154,3704) F(599,2058)
M=3465301: n=7: F(2619,7868) F(2554,7723) F(2514,7623) F(2407,7338) F(1659,5193) F(1574,4944) F(839,2774)
M=3704590: n=7: F(2700,8119) F(2690,8098) F(2500,7617) F(2382,7290) F(2297,7050) F(2265,6959) F(1140,3673)
M=3716728: n=7: F(2673,8064) F(2632,7966) F(2426,7414) F(2283,7011) F(1992,6174) F(1838,5726) F(1048,3401)
M=5247801: n=7: F(3154,9529) F(2978,9067) F(2905,8865) F(2659,8168) F(2159,6718) F(1329,4273) F(503,1817)
M=5298424: n=8: F(3208,9665) F(3196,9638) F(3124,9462) F(3089,9371) F(2966,9038) F(2573,7923) F(2529,7796) F(1360,4366)
M=5509426: n=7: F(3276,9866) F(3244,9793) F(3029,9228) F(2874,8794) F(2173,6767) F(1301,4196) F(864,2898)
M=5586153: n=7: F(3338,10016) F(3282,9897) F(2768,8496) F(2403,7441) F(2218,6901) F(2028,6344) F(1802,5679)
M=5839651: n=8: F(3414,10243) F(3324,10044) F(3303,9992) F(2887,8848) F(2238,6967) F(2008,6292) F(934,3113) F(419,1578)
M=6117203: n=7: F(3478,10451) F(3452,10396) F(3367,10192) F(2437,7557) F(2412,7484) F(622,2189) F(358,1401)
M=6385576: n=7: F(3515,10595) F(3472,10493) F(3149,9619) F(2970,9110) F(2189,6838) F(1149,3763) F(424,1603)
M=7020201: n=7: F(3650,11025) F(3503,10642) F(3474,10563) F(3434,10453) F(3026,9296) F(2947,9068) F(2359,7353)
M=7172576: n=7: F(3784,11353) F(3712,11198) F(3609,10939) F(3089,9483) F(2237,6998) F(1990,6270) F(1345,4360)
M=7754228: n=7: F(3912,11759) F(3863,11651) F(3737,11332) F(3608,10981) F(3548,10814) F(1717,5474) F(632,2247)
M=8684026: n=8: F(4164,12493) F(4069,12284) F(3875,11775) F(3751,11431) F(3109,9588) F(2085,6580) F(1329,4338) F(884,3013)
M=8892701: n=7: F(4119,12434) F(4010,12155) F(3778,11517) F(3751,11441) F(3224,9928) F(3114,9608) F(2170,6835)
M=9673399: n=7: F(4395,13186) F(4285,12941) F(4079,12396) F(2974,9217) F(2445,7661) F(1366,4463) F(1198,3963)

[Andrey A]

(Беда )

Пушкин сидит у себя и думает: Я - гений, ладно. Гоголь тоже гений. Но ведь и Толстой гений, и Достоевский, царство ему небесное, гений! Когда же это кончится?
Тут все и кончилось.

Главное — восьмой член найден $M=826253$. Ага, и девятый $5298424$? Это я уже не могу проверить, круто!
Но тут еще одна беда. Угол секущей тр-ка Паскаля — вовсе не любое число, но с целым тангенсом. То есть $\arctg k$. Только сейчас обратил внимание. Тогда формулировка для OIES несколько путаная выходит.
(Да и задача по-хорошему требует обобщения: дробное $k$? Как это, как это...)

Пока имеем последовательность: $1,8,34,281,2490,17051,243676,826253,5298424,...\ (n=0,1,2,...)$
Для OIES: последовательность наименьших натуральных чисел, представимых $n$ способами в виде суммы более чем $3$-х элементов треугольника Паскаля, расположенных на одной прямой под углом $\arctg k$, где $k>0$ — некоторое целое число. Например $34=\binom{8}{0}+\binom{7}{1}+\binom{6}{2}+\binom{5}{3}+\binom{4}{4}=1+7+15+10+1\ (k=2);$ $=\binom{15}{0}+\binom{11}{1}+\binom{7}{2}+\binom{3}{3}=1+11+21+1\ (k=5)$.

[Dmitriy40]

Andrey A
Нашлась и длиной 9:

Используется синтаксис Text

M=41037270: n=9: F(9055,27167) F(8810,26594) F(8392,25450) F(7890,24018) F(7300,22307) F(6169,18990) F(5412,16755) F(5165,16024) F(4356,13625)

Полный список покажу наверное часика через 3, как досчитается до $10^8$.

О, пока писал и отправлял сообщение, прямо на глазах нашлась и длиной 10:

Используется синтаксис Text

M=52658451: n=10: F(10134,30508) F(9939,30013) F(9652,29228) F(8839,26908) F(8579,26154) F(6951,21381) F(6851,21086) F(3878,12267) F(3174,10169) F(1252,4428)

Да они прям посыпались ворохом ... Длина 11:

Используется синтаксис Text

M=64926751: n=11: F(11326,34041) F(10779,32618) F(10702,32403) F(9954,30268) F(8875,27125) F(8219,25198) F(8129,24933) F(6980,21540) F(4894,15348) F(1374,4843) F(790,3095)

Причём между 10 и 11 лишь одна длиной 9 (и 4 длиной 8), а между 9 и 10 длиной 8 не было вовсе.

[Andrey A]

Dmitriy40
Хорошо бы убедиться, что последовательность приживется в OEIS. Я с ними не переписывался и как-то не планировал. Можете от своего имени, если есть желание, мне так примеров более чем достаточно. Спасибо. Вот для OEIS при отсутствии доказательств бесконечности большое количество членов, конечно, имеет значение. Если понадобится мое участие — чем могу. А так, для загрузки Вашего компа, думаю, нашлись бы и более серьезные задачи )

Dmitriy40 в сообщении #1509174 писал(а):

Да они прям посыпались ворохом ...

Да, интересно. Интересно еще, что отношение $n/k$ жмется к тройке. Маленькое $k$ — большая редкость.