Цепные дроби и континуанты

[Andrey A]

Выборочный обзор и несколько наблюдений в качестве ответа на поставленные и непоставленные вопросы. Под последовательностью целых неотрицательных знаков $a_0,a_1,a_2,…,a_n$ понимается цепная (непрерывная) дробь. Континуанты выделяются квадратными скобками $[a_1,a_2,a_3,…,a_n ]$ как у Гаусса, обозначения из Википедии слишком громоздки. Во избежание путаницы:

$$a_1,a_2,a_3,…,a_n=\frac{[a_1,a_2,a_3,…,a_n ]}{[a_2,a_3,…,a_n ]}$$

Нули и единицы

Общеизвестны строгие соответствия:
Конечная дробь $\leftrightarrow $ рациональное число.
Бесконечная периодическая дробь $\leftrightarrow $ квадратичная иррациональность.
Бесконечная непериодическая дробь $\leftrightarrow $ любое другое вещественное число.

Процесс разложения рационального числа в непрерывную дробь часто называют алгоритмом Евклида, хотя Евклида (вроде бы) интересовали не неполные частные и даже не остатки, а только последний остаток перед нулем равный наибольшему общему делителю. Последовательность остатков содержит, впрочем, полную информацию о разложении, как и в случае $p$-ичных дробей. Последнее же частное (полное) в итоге всегда оказывается $>1$. Назовем такое разложение приведенным и считаем по умолчанию $a_k\in \mathbb{N}, a_n>1$, не забывая однако, что для дробей и континуант верно $a_1,a_2,a_3,…,a_n=a_1,a_2,a_3,…,a_n-1,1$. Для континуант в силу свойства

$$[a_1,a_2,a_3,…,a_n ]=[a_n,a_{n-1},a_{n-2},…,a_1 ]\ \ \ (1)$$

верно также

$[a_1,a_2,a_3,…,a_n ]=[1,a_1-1,a_2,a_3,…,a_n ]=[1,a_1-1,a_2,a_3,…,a_n-1,1]$

Однозначность разложения произвольной несократимой дроби $\frac{P}{Q}>1$ означает в континуантах единственность решения системы уравнений $\left\{\begin{matrix}[x_1,x_2,x_3,…,x_n ]=P\\ [x_2,x_3,…,x_n]=Q\end{matrix}\right$ и строгое взаимное соответствие произвольной конечной последовательности натуральных чисел некоторой рациональной точке на числовой оси (и обратно). Побочным результатом восстановления простой дроби из непрерывной является последовательность подходящих дробей:

$$\frac{a_1}{1};\frac{a_2a_1+1}{a_2};...;\frac{p_{k+1}=a_{k+1}p_k+p_{k-1}}{q_{k+1}=a_{k+1}q_k+q_{k-1}};\frac{P=a_np_{n-1}+p_{n-2}}{Q=a_nq_{n-1}+q_{n-2}}.$$

Иногда выписывают «нулевую» дробь $\frac{1}{0}$. В континуантах это выглядит так:

$$\frac{[1]}{[0]};\frac{[a_1]}{[1]};\frac{[a_1,a_2 ]}{[a_2 ]};\frac{[a_1,a_2,a_3 ]}{[a_2,a_3]};...;\frac{[a_1,a_2,a_3,…,a_{n-1}]}{[a_2,a_3,…,a_{n-1}]};\frac{[a_1,a_2,a_3,…,a_{n-1},a_n]}{[a_2,a_3,…,a_{n-1},a_n]}\ \ \ (2)$$

Отсюда еще одно «образующее» тождество:

$$[a_1,a_2,a_3,…,a_n]=a_1[a_2,a_3,…,a_n ]+[a_3,…,a_n]=[a_1,a_2,…,a_{n-1}]a_n+[a_1,a_2,…,a_{n-2}]\ \ \ (3)$$

В случае $a_1=0$ имеем $[0,a_2,a_3,…,a_n]=[a_3,…,a_n]$ и $[a_1,a_2,…,a_{n-1},0]=[a_1,a_2,…,a_{n-2}]$.
Верно также $[a_1,a_2,…,b,0,c,…,a_n ]=[a_1,a_2,…,(b+c),…,a_n]$, в чем легко убедиться, выписывая соответствующие подх. дроби. Для наглядности: если приписанный по краям континуанты ноль действует на манер ластика, «вытирая» соседний знак, то внутри – на манер канцелярского клея, суммируя соседние знаки. Все это верно и для дробей за исключением случая, когда ноль стоит в начале. Его рассмотрим отдельно. Пусть $a_1,a_2,…,a_n$ – разложение некоторой рациональной точки $R>1$. Запишем: $R=a_1,a_2,…,a_n=\dfrac{[a_1,a_2,…,a_n]}{[a_2,…,a_n]}$. Первый знак $a_1$ суть целая часть $R$, то есть $a_1>0$. Тогда дробь $0,a_1,a_2,…,a_n=\dfrac{[0,a_1,a_2,…,a_n]}{[a_1,a_2,…,a_n]}=\dfrac{[a_2,…,a_n]}{[a_1,a_2,…,a_n]}=\frac{1}{R}<1$ является обратной дробью - единственный случай, когда ноль остается в приведенной записи. Дробь с нулем в последующих знаках есть «промежуточная дробь», пользуясь терминологией Хинчина. Пара же последовательных нулей во всех случаях взаимоуничтожается: $0,0,a_1,a_2,…,a_n=(0+a_1),a_2,…,a_n=a_1,a_2,…,a_n$. Существует множество способов привести список произвольно выбранных континуант к общему количеству знаков, манипулируя парами нулей и единицами по краям. Сами же континуанты останутся неприведенными. Из свойства подходящих дробей $p_nq_{n-1}-p_{n-1}q_n=(-1)^n$ следует тождество

$$[a_1,a_2,a_3,…,a_n][a_2,a_3,…,a_{n-1}]-[a_2,a_3,…,a_n][a_1,a_2,a_3,…,a_{n-1}]=(-1)^n,\ \ \ (4)$$

что видно из $(2)$ и соответствует уравнению $Px-Qy=±1$. Легче это не решить – основная причина, пожалуй, по которой до сих пор не забыта эта странная арифметика.

Тождества

Вполне содержательный термин «остаток дроби» $r_k$ не следует путать с остатками от деления в процессе разложения. В сущности это просто дробь, взятая не с первого или не обязательно с первого знака (с k-того), и по аналогии с $p$-ичными дробями может интерпретироваться как последний дробный знак с той лишь разницей, что вместо сложения действует правило образования подходящих дробей: $\dfrac{r_kp_{k-1}+p_{k-2}}{r_kq_{k-1}+q_{k-2}}$. Для рационального $\frac{P}{Q}=a_1,a_2,…,a_k,…,a_n$ рационально и $r_k=a_k,…,a_n=\dfrac{p'}{q'}$. Тогда $\frac{P}{Q}=\dfrac{r_kp_{k-1}+p_{k-2}}{r_kq_{k-1}+q_{k-2}}=\dfrac{\tfrac{p'}{q'}p_{k-1}+p_{k-2}}{\tfrac{p'}{q'}q_{k-1}+q_{k-2}}=\dfrac{p'p_{k-1}+q'p_{k-2}}{p'q_{k-1}+q'q_{k-2}}$. Отсюда еще пара тождеств в континуантах:

$${\tiny [a_1,a_2,…,a_n][b_1,b_2,…,b_m]+[a_2,…,a_n][b_2,…,b_m]=[a_n,a_{n-1},…,a_1,b_1,…,b_{m-1},b_m]}\ (5)$$

$$[a_1,a_2,…,a_n][b_1,b_2,…,b_m]-[a_2,…,a_n][b_2,…,b_m]=[a_n,a_{n-1},…,(a_1-1),1,(b_1-1),…,b_{m-1},b_m]\ (6)$$

Первое – обобщение $(3)$, второе - как следствие. Отсюда же - разрешимость системы уравнений для пары аргументов $P>Q$ одной четности с общим делителем $\leq 2$:

$$\left\{\begin{matrix}[x_1,…,y,z,…,x_n]=P\\ [x_1,…,(y-1),1,(z-1),…x_n]=Q\end{matrix}\right$$

Для $P=403,Q=333$, к примеру, имеем $\frac{403+333}{2}=368=23\cdot 16;\ \frac{403-333}{2}=35=7\cdot 5;\ 23/7=3,3,2;\ 16/5=3,5.$ Соединяя результаты целыми частями, получаем $[2,3,3,3,5]=403;\ [2,3,2,1,2,5]=333$
Замена $7 \leftrightarrow 5$ дает другое решение, поэтому о единственности тут говорить не приходится. Кроме того, может оказаться $y,z=1$ или $y,z=0$. В первом случае действует правило нуля (суммирование соседних знаков, суммы знаков в скобках по-прежнему отличаются на единицу). Во втором случае входим в область отрицательных знаков, и могут пригодиться тождества-рокировки:

$$[a_1,…,b,1,-1,c,d,e,…,a_n ]=[a_1,…,(b-c),1,(d-1),e,…,a_n ]$$

$[a_1,…,b,-c,d,e,…,a_n ]=-[a_1,…,(b-1),1,(c-2),1,(d-1),e,…,a_n ]$

Пусть теперь аргументы $P,Q$ сравнимы по взаимнопростому модулю $m$. Тогда дроби $\frac{P}{m};\ \frac{Q}{m}$ отличаются только целой частью, как и в $p$-ичных дробях. Соответствующие континуанты уже не обязательно взаимно просты: $128=[18,3,2];\ 16=[2,3,2].$ В частности суммы и разности вз. простых слагаемых

$[a_1,a_2,a_3,…,a_n]+[a_2,a_3,…,a_n]=[(a_1+1),a_2,a_3,…,a_n]$

$[a_1,a_2,a_3,…,a_n]-[a_2,a_3,…,a_n]=[(a_1-1),a_2,a_3,…,a_n]$

могут иметь общий делитель $2$. Для них верны тождества похожие на $(5),(6)$:

$$[a_n,…,a_1,b_1,…,b_m]+[a_n,…,(a_1+b_1),…,b_m]=[(a_1+1),a_2,…,a_n][ (b_1+1),b_2,…,b_m]$$

$$[a_n,…,a_1,b_1,…,b_m]-[a_n,…,(a_1+b_1 ),…,b_m]=[(a_1-1),a_2,…,a_n][ (b_1-1),b_2,…,b_m]$$

Вероятно, все подобные выражения могут быть выведены из более общего:

$$[a_1,…,a_l,b_1,…,b_m,c_1,…,c_n][b_1,…,b_m]-[a_1,…,a_l,b_1,…,b_m][b_1,…,b_m,c_1,…,c_n]=$$

$$=[a_1,…,a_{l-1}][c_2,…,c_n]\cdot (-1)^m \qquad (7)$$

Такое тождество не очень удобно для практического применения, но полезно для преобразований и графически соответствует треугольной матрице $(8)$, образованной подходящими дробями $k$-тых остатков дроби $\frac{P}{Q}=a_1,a_2,…,a_l,b_1,b_2,…,b_m,c_1,c_2,…,c_n.$

Возьмем для примера дробь подлиннее: $1,2,3,1,2,3,4,1,2,3,4,5=\dfrac{135997}{94413}$

Вложение:

M1.jpg [ 70.69 Кб | Просмотров: 0 ]

Элементы простой дроби расположены в правом верхнем углу, элементы непрерывной дроби – во второй диагонали. Первые две строки суть последовательность подходящих дробей. Матрица симметрична в том смысле, что каждый ее элемент есть остаток от деления двух соседних элементов как справа так и сверху, и может строиться как из левого верхнего угла так и из правого нижнего по принципу $q_k=a_kq_{k-1}+q_{k-2}$, причем нужное $a_k$ берется из проекции $q_k$ на вторую диагональ. Крайний правый столбец – последовательность остатков деления в процессе разложения $\frac{P}{Q}$. Значение всех определителей $2$-го порядка $=\pm 1$, бОльших прядков $=0$.
Два луча, отраженных под прямым углом от нулевой диагонали пересекаются с верхней строкой в точках $3;520$, с правым столбцом – в точках $11245;157$, между собой – в точке $43$. Ну, а столбец со строкой пересекаются в точке $P=135997$. Эти величины связаны между собой соотношением $135997\cdot 43-11245\cdot 520=157\cdot 3\cdot (-1)^4$, что и соответствует тождеству $(7)$.
Непосредственно из $(5),(6)$ выводятся правила возведения в квдрат и суммирования квадратов вз. простых континуант:

$$[a_1,a_2,…,a_n ]^2=[a_1,a_2,…,(a_n+1),(a_n-1),…,a_2,a_1]$$

$$[a_1,a_2,a_3,…,a_n]^2+[a_2,a_3,…,a_n]^2=[a_n,a_{n-1},…,a_2,a_1,a_1,a_2,…,a_{n-1},a_n] \qquad(9)$$

$$[a_1,a_2,a_3,…,a_n]^2-[a_2,a_3,…,a_n]^2=[a_n,a_{n-1},…,a_2,(a_1-1),1,(a_1-1),a_2,…,a_{n-1},a_n] \qquad(10)$$

Палиндромы

Из общей теории известно, что если $\dfrac{p_{n-1}}{q_{n-1}};\dfrac{p_n}{q_n}$ – две последние подходящие дроби разложения $a_1,a_2,a_3,…,a_n$, то взаимозамена $q_n \leftrightarrow p_{n-1}$ соответствует дроби в обратном движении $a_n,a_{n-1},...,a_2,a_1$ (реверс). Этот факт хорошо иллюстрирует замена в матрице $(8)$ строк на столбцы и обратно (разворот на $180°$). Если же предположить $q_n=p_{n-1}$, что возможно, то такая взаимозамена ничего не меняет (пара подходящих дробей фактически прежняя). Это значит, что восстановление дроби в прямом и обратном движении ведет к одинаковому результату. В силу единственности разложения имеем $a_1=a_n; a_2=a_{n-1};a_3=a_{n-2};…$ и т.д. – ситуация, характеризуемая термином «палиндром». Последняя же пара дробей имеет вид $\frac{B}{C};\frac{A}{B}$, и по свойству $(4)$ подходящих дробей $AC-B^2=(-1)^n$ или $B^2+(-1)^n=AC$. Таким образом, каждое разложение $\frac{A}{B}$ при условии $B^2\equiv \pm 1 \mod A \ (B<A/2)$ имеет форму палиндрома в приведенном виде.
При четном $n=2k\ \frac{A}{B}=a_1,a_2,…,a_{k-1},a_k,a_k,a_{k-1},…,a_2,a_1. $
При нечетном $n=2k-1\ \frac{A}{B}=a_1,a_2,…,a_{k-1},a_k,a_{k-1},…,a_2,a_1.$
Верно и обратное: каждый палиндром обладает свойством $B^2\equiv \pm 1 \mod A.$ Здесь укажу только на тождественную связь между элементами трех подх. дробей $\dfrac{p_{k-2}}{q_{k-2}};\dfrac{p_{k-1}}{q_{k-1}};\dfrac{p_k}{q_k}$ и последних пар подх. дробей соответствующих им четных и нечетных палиндромов:

$$\dfrac{B=p_kq_k+p_{k-1}q_{k-1}}{C=q_k^2+q_{k-1}^2};\dfrac{A=p_k^2+p_{k-1}^2}{B=p_kq_k+p_{k-1}q_{k-1}} \qquad (11)$$

$$\dfrac{B=p_kq_{k-1}+p_{k-1}q_{k-2}}{C=q_{k-1}(q_k+q_{k-2})};\dfrac{A=p_{k-1}(p_k+p_{k-2})}{B=p_kq_{k-1}+p_{k-1}q_{k-2}} \qquad (12)$$

Возвращаясь к континуантам, видим, что случай $(11)$ полностью соответствует тождеству $(9)$. Сложению взаимно простых квадратов сопутствует решение сравнения $x^2\equiv -1\ mod\ A=p^2+q^2.$ Для $A=389=17^2+10^2$, к примеру, из разложения $\frac{17}{10}=1,1,2,3$ получаем $3,2,1,1=\frac{3}{1};\frac{7}{2};\frac{10}{3};\frac{17}{5}$, откуда $x=17\cdot 5+10\cdot 3=115.$ Хотя, можно было полностью выписать и восстановить палиндром $3,2,1,1,1,1,2,3=\frac{3}{1};\frac{7}{2};\frac{10}{3};\frac{17}{5};\frac{27}{8};\frac{44}{13};\frac{115}{34};\frac{389}{115}.$
Случай $(12)$ с тождеством (10) напрямую не соотносится, т.к. последнее не является общим случаем: в центре симметрии стоит единица. При $a_1=1$, впрочем, тождество принимает вид

$$[1,a_2,…,a_n ]^2-[a_2,…,a_n ]^2=[a_n,…,a_2,0,1,0,a_2,…,a_n]=[a_n,…,2a_2+1,…,a_n]$$

из чего можно заключить только, что нечетный палиндром с нечетным центром симметрии есть разность квадратов, но не обратно. Исследуем симметричную континуанту с нечетным кол-вом знаков в общем виде с помощью тождества (5):

$$[a_1,a_2,…,a_{k-1},a_k,a_{k-1},…,a_2,a_1]=$$

$$[a_1,a_2,…,a_{k-1},a_k][a_{k-1},…,a_2,a_1]+[a_1,a_2,…,a_{k-1}][a_{k-2},…,a_2,a_1]=$$

$$[a_1,a_2,…,a_{k-1}]\left( [a_1,a_2,…,a_{k-1},a_k]+[a_1,a_2,…,a_{k-2}]\right) \qquad (13)$$

Это соответствует числителю последней дроби $(12)$. Не любое произведение является разностью квадратов, отсюда неполнота тождества $(10)$. Но остается неясным, любая ли пара множителей $d_1d_2=A$ выражается формулой $(13).$ Запишем уравнение: $\left\{\begin{matrix}[a_1,a_2,…,a_{k-1}]=d_1\\ [a_1,a_2,…,a_{k-1},a_k]+[a_1,a_2,…,a_{k-2}]=d_2\end{matrix}\right$
Из тождества (3) берем $[a_1,a_2,…,a_{k-1},a_k]=a_k[a_1,a_2,…,a_{k-1}]+[a_1,a_2,…,a_{k-2}]$ и подсавляем в предыдущее: $\left\{\begin{matrix}[a_1,a_2,…,a_{k-1}]=d_1\\ a_k[a_1,a_2,…,a_{k-1}]+2[a_1,a_2,…,a_{k-2}]=d_2\end{matrix}\right$ Континуанты $[a_1,a_2,…,a_{k-1}]>[a_1,a_2,…,a_{k-2}]$ взаимно просты, следовательно

1) НОД $(d_1,d_2)\leq 2$ (назовем это «почти вз. простые»)
2) $2[a_1,a_2,…,a_{k-2}]$ есть четный положительный вычет $d_2\mod\ d_1$ «почти вз. простой» с $d_1$.

Хотелось бы сказать – наименьший, но есть исключение: $d_2=4u+2>d_1=4v$. Тут еще возможен вариант «преднаименьший». Неполное частное от такого деления $=a_k$, а отношение $d_1$ к половине вычета выражается дробью $\dfrac{[a_1,a_2,…,a_{k-1}]}{[a_1,a_2,…,a_{k-2}]}=\dfrac{[a_{k-1},a_{k-2},…,a_2,a_1 ]}{[a_{k-2},…,a_2,a_1]}$ и вычисляется уже по стандартной процедуре. Таким образом реализуется «умножение» почти вз. простых чисел цепными дробями – несколко видоизмененный алгоритм Евклида, где вторым делителем выступает не остаток от предыдущего деления, а половина остатка, всё остальное без изменений. Результат – последовательность $a_k,a_{k-1},…,a_2,a_1$ – подпоследовательность нечетного полиндрома $A=[a_1,a_2,…,a_{k-1},a_k,a_{k-1},…,a_2,a_1]=d_1d_2$. Простая дробь $\frac{A}{B}$ может быть также восстановлена из элементов трех последних подх. дробей реверса $a_1,a_2,…,a_{k-1},a_k$ по формуле $(12)$, причем $B^2\equiv 1 \mod A$. Формализовать условия деления на $1$-ом этапе удается в трех пунктах:

1) $A$ нечетное. Делится большее на меньшее, $a_k$ нечетное.
2) $A$ удвоенное нечетное. Делится четное на нечетное, $a_k$ четное.
3) $A\ \vdots\ 4.$ Во избежание повторения результатов делятся любые четные (НОД $=2$). Единственное ограничение – остаток вида $4t+2.$

Приведу для примера все «умножения» для $A=120$.

$\begin{matrix} d_1 & d_2 & \textrm{Первый остаток} & \textrm{Палиндром} & B\\ 2 & 60 & 2 & [2,29,2] & 59\\ 60 & 2 & 2 & [60,0,60]=[120] & 1\\ 4 & 30 & 2 & [4,7,4] & 29\\ 4 & 30 & 6 & [3,1,6,1,3] & 31\\ 6 & 20 & 2 & [6,3,6] & 19\\ 20 & 6 & 6 & [2,1,6,0,6,1,2]=[2,1,12,1,2] & 41\\ 10 & 12 & 2 & [10,1,10] & 11\\ 12 & 10 & 10 & [2,2,2,0,2,2,2]=[2,2,4,2,2] & 49 \end{matrix}$

Количество нечетных палиндромов, равных $A$ в полном соответствии с теоремой о количестве корней из единицы $(<A/2)$ по модулю (Бухштаб стр. 169) - всегда степень двойки. В случае $A$, равного единице, двойке, четверке, степени нечетного простого или удвоенной степени нечетного простого единственным нечетным палиндромом кроме неприведенного $[1,A-2,1]$ является $[A]$.

(комментарий 1)

Чем больше знаков в дроби $a_1,a_2,…,a_{k-1},a_k$, тем ближе к ней на числовой оси расположен соответствующий палиндром. Просто по причине большого количества общих знаков в начале дроби. Любой последовательности подх. дробей, стремящейся к вещественной точке можно поставить в соответствие последовательность палиндромов, стремящихся к ней же, но медленнее (что хорошо бы еще доказать). Возьмем теперь произвольную пару конечных дробей

$$U=a_1,a_2,a_3,…,a_n$$

$$V=b_1,b_2,b_3,…,b_m$$

и вычислим сумму

$$U+V=\frac{[a_1,a_2,a_3,…,a_n]}{[a_2,a_3,…,a_n]}+\frac{[b_1,b_2,b_3,…,b_m]}{[b_2,b_3,…,b_m]}=$$

$$\frac{[a_1,a_2,a_3,…,a_n][b_2,b_3,…,b_m]+[a_2,a_3,…,a_n][b_1,b_2,b_3,…,b_m]}{[a_2,a_3,…,a_n][b_2,b_3,…,b_m]}=$$

$$\frac{[a_1,a_2,a_3,…,a_n ][0,b_1,b_2,b_3,…,b_m]+[a_2,a_3,…,a_n][b_1,b_2,b_3,…,b_m]}{[a_2,a_3,…,a_n][b_2,b_3,…,b_m]}=$$

$$\frac{[a_n,a_{n-1},…,a_2,a_1,0,b_1,b_2,…,b_m]}{[a_2,a_3,…,a_n][b_2,b_3,…,b_m]}=$$

$$\frac{[a_n,a_{n-1},…,a_2,(a_1+b_1),b_2,…,b_m]}{[a_2,a_3,…,a_n][b_2,b_3,…,b_m]}=S$$

Выражение складное, однако деление числителя на знаменатель по обычной процедуре возвращает последовательность знаков, формально не связанных с последовательностями аргументов. Операция сложения не определена – одна из главных причин, затрудняющих применение цепных дробей в прикладных целях. Дробь $S$ вполне может оказаться сократимой: знаменатели независимы и могут быть кратны, а как выразить однозначно в континуантах четверку произвольных «последовательно взаимно простых» чисел мне не известно. В то же время дробь

$$a_n,a_{n-1},…,a_2,(a_1+b_1),b_2,…,b_m=\frac{[a_n,a_{n-1},…,a_2,(a_1+b_1),b_2,…,b_m]}{[a_{n-1},…,a_2,(a_1+b_1),b_2,…,b_m]}=s$$

1) Определена. 2) Несократима. 3) Имеет с $S$ общий числитель. 4) Может быть $>S$,$<S$ и даже $=S$. Пример: $2,5,1,6+4,1,2=6,1,5,(2+4),1,2=6,1,5,6,1,2$. Если назначить суммой $s$ и строить на основе такого сложения некую непротиворечивую арифметику, пришлось бы выбирать: либо $U+V \neq V+U$, что нежелательно, либо считать равными $s$ и реверс-$s$ (как в континуантах - свойство $(1)$), хотя на числовой прямой это разные точки – в общем случае, но не в случае палиндромов! Какая-то это должна быть другая числовая прямая. Или кривая, пересекающаяся с привычной осью в точках палиндромов При том что в каждой окрестности находятся пары палиндромов сколь угодно мало удаленных друг от друга...

[Andrey A]

Пусть $a_1,a_2,a_3,…,a_n=\dfrac{p_{n-1}}{q_{n-1}};\dfrac{p_n}{q_n}$ - некоторая конечная дробь. Что можно сказать о бесконечной дроби с соответствующим чистым периодом? Запишем уравнение:

$(a_1,a_2,a_3,…,a_n)=X,$ или так:

$$X=a_1,a_2,a_3,…,a_n,a_1,a_2,a_3,…,a_n,a_1,a_2,a_3,…,a_n,…$$

Из последней записи видно, что $(n+1)$-ый остаток дроби $r_{n+1}$ равен самому $X$, то есть

$$\frac{r_{n+1}p_n+p_{n-1}}{r_{n+1}q_n+q_{n-1}}=\frac{Xp_n+p_{n-1}}{Xq_n+q_{n-1}}=X.$$

Отсюда $q_nX^2-(p_n-q_{n-1})X-p_{n-1}=0;\ X=\dfrac{p_n-q_{n-1}+\sqrt{(p_n-q_{n-1})^2+4p_{n-1}q_n}}{2q_n}.$
И поскольку $p_{n-1}q_n=p_nq_{n-1}-(-1)^n$, получаем окончательно

$$X=\dfrac{p_n-q_{n-1}+\sqrt{(p_n+q_{n-1})^2-4\cdot (-1)^n}}{2q_n}\qquad (14)$$

(комментарий 2)

Основание квадрата под радикалом в выражении (14) достойно отдельного рассмотрения: $p_n+q_{n-1}$ суть cумма элементов пары подх. дробей, расположенных по диагонали. Выделим это в отдельную функцию $\left \{ ... \right \}$ и запишем в континуантах:

$$\left \{ a_1,a_2,…a_{n-1},a_n\right \}=[a_1,a_2,…a_{n-1},a_n]+[a_2,…a_{n-1}]=$$

$$a_n[a_1,a_2,…,a_{n-2},a_{n-1}]+[a_1,a_2,…a_{n-2}]+[a_2,…,a_{n-2},a_{n-1}]=$$

$$[a_n,a_1,a_2,…,a_{n-2},a_{n-1}]+[a_1,a_2,…,a_{n-2}]=\left \{ a_n,a_1,a_2,…,a_{n-2},a_{n-1}\right \}=$$

$$\left \{ a_{n-1},a_n,a_1,…,a_{n-3},a_{n-2}\right \}=\left \{ a_{n-2},a_{n-1},a_n,a_1,…,a_{n-3}\right \}=...$$

Иными словами, для такой супер-K по меткому выражению одного хорошего математика применимо правило «круглого стола», когда невозможно указать из гостей на первого или последнего. На бумаге «кольцевать» последовательности не удобно, но для строчной записи можно дать следующую формулировку: правило обратного движения (1) справедливо не только для всей последовательности знаков супер-K, но и для двух участков ее произвольного разбиения:

$$\left \{a_1,a_2,…a_{n-1},a_n,b_1,b_2,…b_{m-1},b_m\right \}=\left \{ a_n,a_{n-1},…a_2,a_1,b_m,b_{m-1},…,b_2,b_1\right \}$$

Правило нуля внутри последовательности остается в силе, по краям же ноль не исчезает:

$$\left \{0,a_1,a_2,…a_{n-1},a_n \right \}=\left \{a_1,a_2,…a_{n-1},a_n,0\right \}=[a_1,a_2,…a_{n-1}]+[a_2,…a_{n-1},a_n]\ -$$

суть сумма элементов пары подх. дробей, расположенных по другой диагонали. Верно также

$$[a_1,a_2,…a_{n-1},a_n]-[a_2,…a_{n-1}]=\left \{ 1,(a_1-1),a_2,…a_{n-1},(a_n-1) \right \}$$

Выражение (14) можно тогда переписать так:

$$(a_1,a_2,…a_{n-1},a_n)=\dfrac{\left \{ 1,(a_1-1),a_2,…a_{n-1},(a_n-1)\right \}+\sqrt{\left \{ a_1,a_2,…a_{n-1},a_n \right \}^2-4\cdot(-1)^n}}{2[a_2,…a_{n-1},a_n]}$$

и для всех круговых перестановок значение под радикалом остается неизменным. Это свойство объясняется еще справедливостью определения Эйлера в отношении супер-K как суммы одночленов, образованных вычеркиванием всех возможных пар соседних элементов из одночлена $a_1 a_2 a_3…a_{n-1}a_n$ если элементы расположены не в строку, как в случае континуант, а в «замкнутую строку», причем одночлен со всеми вычеркнутыми парами при четном количестве знаков имеет значение не 1, а 2. Получить алгоритмически последовательность супер-K для натурального аргумента или установить тождественную связь $[a_1,a_2,…a_{n-1},a_n]=\left \{ x_1,x_2,…x_{m-1},x_m \right \}$ в общем виде не удалось. С палиндромами как всегда легче:

$$[a_1,a_2,…a_2,a_1]=\left \{ (a_1-1),a_2,…a_2,(a_1+1) \right \}$$

И более общее выражение, хотя не завершенное:

$$b[a_1,a_2,…a_2,a_1]=\left \{(a_1-1),a_2,…a_2,a_1,(b-1),1\right \}$$

Вернемся чуть назад. Последняя пара подх. дробей палиндрома из n знаков имеет вид $\frac{B}{C};\frac{A}{B}$ (положим A>B>C). Обратная дробь (с добавленным нулем) из (n+1) знаков имеет вид $\frac{C}{B};\frac{B}{A}$, причем $B^2=AC+(-1)^{n+1}.$ Подставим ее в (14) вместо $\dfrac{p_{n-1}}{q_{n-1}};\dfrac{p_n}{q_n}$, делая замены $n\rightarrow n+1,p_n=q_{n-1} \rightarrow B,q_n \rightarrow A,p_{n-1} \rightarrow C$:

$$X=\dfrac{B-B+\sqrt{(2B)^2-4\cdot (-1)^{n+1}}}{2A}=\dfrac{\sqrt{B^2-(-1)^{n+1}}}{A}=\sqrt{\frac{AC}{A^2}}=\sqrt{\frac{C}{A}}.$$

Добавляя ноль справа от палиндрома, получаем последнюю пару $\frac{A}{B};\frac{B}{C}.$ Аналогичные подстановки ведут к $X=\sqrt{\dfrac{A}{C}}.$ Вывод: чисто приодическая дробь с периодом (0, палиндром) или (палиндром,0) есть квадратный корень из некоторого рационального числа. Верно ли обратное?
$A,C$ – не любые числа, но требованием взаимной простоты не связанные. Единственное ограничение – существование целого $B=\sqrt{AC+(-1)^{n+1}}$, из чего видно, что $AC$ в общем случае не является целым квадратом. Пусть $d=\text{НОД}(A,C)$, $A=ad,C=cd$ при вз. простых $a,c$. Обратное утверждение верно, если для произвольной несократимой дроби $\dfrac{a}{c}$, не являющейся квадратом рациональгого числа, находятся $d$ и $B$ такие, что $B=\sqrt{AC+(-1)^{n+1}}$, или $B^2=acd^2+(-1)^{n+1}.$ Это приводит к известному разрешимому уравнению $B^2-acd^2=(-1)^{n+1}$. То же и для обратной дроби $\frac{C}{A}.$ Таким образом, каждый квадратный радикал есть чисто периодическая дробь. Период – палиндром с нулем слева или справа в зависимости от того $<1$ или $>1$ подкоренное значение. Из формул (11), (12) видим, что в окрестности каждой рациональной точки $a_1,a_2,…,a_{k-2},a_{k-1},a_k=\dfrac{p_{k-2}}{q_{k-2}};\dfrac{p_{k-1}}{q_{k-1}};\dfrac{p_k}{q_k}$ расположены радикалы

$$\sqrt{\frac{p_{k-1}(p_k+p_{k-2})}{q_{k-1}(q_k+q_{k-2})}}=(a_1,a_2,…,a_{k-1},a_k,a_{k-1},…,a_2,a_1,0)$$

и

$$\sqrt{\frac{p_k^2+p^2_{k-1}}{q_k^2+q^2_{k-1}}}=(a_1,a_2,…,a_{k-1},a_k,a_k,a_{k-1},…,a_2,a_1,0)$$

с соответствующим полупериодом. Процесс разложения квадратного радикала также можно cвести к полупериоду, если не важны значения старших подх. дробей кроме последних, которые следуют из формул (11), (12). Для решения уравнения $x^2-1957y^2=1$, к примеру, достаточно семи знаков разложения $\sqrt{1957}=44,4,4,1,21,3,4,…=\frac{44}{1};\frac{177}{4};\frac{752}{17};\frac{929}{21};\frac{20261}{458};\frac{61712}{1395};\frac{267109}{6038};...$ $x=267109\cdot 1395+61712\cdot 458=400881151; y\approx x/\sqrt{1957}=9061920.$
Алгоритм разложения не фиксирует нулей, отсюда и термин «промежуточная дробь». Из процедуры вместо $a_1,a_2,…,a_k,…,a_2,a_1,0,a_1,a_2,…$ получаем приведенную запись $a_1,a_2,…,a_k,…,a_2,2a_1,a_2,…$ которая, не являясь формально чистым периодом, усложняет выкладки и вызывает вопросы, хотя присутствие удвоенного первого знака в конце периода также следует из вышесказанного. Корень из целого числа выделяется из общего случая тоько тем, что $A\ \vdots \ C.$ Тут возникает любопытный вопрос: для всякого ли палиндрома $a_1,a_2,…,a_2,a_1$ разрешимо уравнение в целых числах

$$(x,a_1,a_2,…,a_2,a_1,x,0)=\sqrt{y}$$

Или в виде задачи: всякий ли палиндром может быть приближением дробной части целого радикала с точностью до периода?
Две последние подх. дроби палиндрома имеют вид $\frac{B}{C};\frac{A}{B}$, причем $B^2\mp 1=AC.$ Разложению дробной части соответствуют обратные дроби $\frac{C}{B};\frac{B}{A}.$ Прибавим к ним целую часть $x:\ \frac{Bx+C}{B};\frac{Ax+B}{A}.$ Тогда тройка дробей перед нулем принимает вид $\frac{Bx+C}{B};\frac{Ax+B}{A};\frac{x(Ax+B)+Bx+C}{Ax+B}.$ В случае целого радикала числитель последней дроби должен делиться на знаменатель предпоследней: $\frac{Ax^2+2Bx+C}{A}=y=x^2+\frac{2Bx+C}{A}$ Остается выяснить, при каких условиях последняя дробь оказывается сократимой. Из $ \left\{\begin{matrix}2Bx\equiv & -C \\ B^2\equiv & \pm 1 \end{matrix}\right. \mod A$ и взаимной простоты $A,B$ получаем ключевое выражение

$$2x\equiv \mp BC \mod A,$$

которое нужно рассмотреть поподробнее. Если $B,C$ – нечетные, $A$ вынужденно четное, и такое сравнение неразрешимо. Дробь $\frac{11}{24}$, к примеру, не может быть приближением дробной части целого радикала т.к. оба знаменателя последней пары $\frac{11}{5};\frac{24}{11}=2,5,2$ – нечетные. Если же одно из чисел $B,C$ – четное, то

$$\left\{\begin{matrix} x \equiv & (-1)^n\cdot BC/2 \mod A & \text {в случае нечетного}\ A\\ x \equiv & (-1)^n\cdot BC/2 \mod A/2 & \text {в случае четного}\ A \end{matrix}\right.$$

Где $n$ – количество знаков палиндрома.

Пример: $2,6,2=\frac{2}{1};\frac{13}{6};\frac{28}{13}.\ -39 \mod 14=3,17,…$ Отсюда $(3+\frac{13}{28})^2 \approx 12;\ (17+\frac{13}{28})^2\approx 305;…$
$\sqrt{12}=(3,2,6,2,3,0);\ \sqrt{305}=(17,2,6,2,17,0);\ \sqrt{990}=(31,2,6,2,31,0)... $… и т.д. Произведение соседних членов последовательности $y_k$ – число вида $t^2\pm 1$ или $t(t+1).$ Рекуррентное правило: $y_{k+1}=2(y_k+A^2)-y_{k-1}$ или $y_{k+1}=2(y_k+(A/2)^2)-y_{k-1}$ в зависимости от четности $A.$ Подобные «арифметические прогрессии» из радикалов несовершенны: разность прогрессии, не является целым числом, но стремится к целому числу.

Радикалы степени k

Разложение $\sqrt[3]{3}=1,2,3,1,4,1,5,1,1,6,…$ можно легко посчитать на калькуляторе с функцией $\dfrac{1}{n}$, вычитая последовательно целую часть, – процесс, ограниченный точностью вычислительного устройства. Понятно, что раскладывается при этом не сама иррациональность, а десятичное ее приближение, и, поскольку о структуре непериодических последовательностей разложения алгебраических чисел степени $>2$ сказать попросту нечего, попробую предложить хотя бы некий гибридный метод разложения радикалов степени $k$. Определим для начала формулу $(n+1)$-го остатка разложения вещественного $R$ в общем виде. Непосредственно из $R=\frac{r_{n+1}p_n+p_{n-1}}{r_{n+1}q_n+q_{n-1}}$ следует

$$r_{n+1}=-\frac{p_{n-1}-Rq_{n-1}}{p_n-Rq_n}$$

- формула, позволяющая получить вышеупомянутым способом дробь, начиная с $(n+1)$-го знака, или хотя бы один ее знак:

$$a_{n+1}=\left \lfloor -\frac{p_{n-1}-Rq_{n-1}}{p_n-Rq_n} \right \rfloor\qquad(15)$$

Чтобы извлечь лучшее приближение из $\dfrac{3}{1};\dfrac{22}{7}\approx\pi$ Архимеду достаточно было бы подставить в (15) значения: $-\dfrac{3-\pi\cdot1}{22-\pi\cdot7}\approx16$ и получить $\dfrac{16\cdot22+3}{16\cdot7+1}=\dfrac{355}{113}$, но $\pi$ для этого нужно знать с хорошей точностью. Пригодились бы тут его многоугольники - трудно сказать. Сдвиг с мертвой точки в подобных задачах происходит, если удается избавиться от иррациональности в знаменателе. В случае $k=2$ это не сложно:

$$-\dfrac{p_{n-1}-\sqrt{m}q_{n-1}}{p_n-\sqrt{m}q_n}=-\dfrac{(p_{n-1}-\sqrt{m}q_{n-1})(p_n+\sqrt{m}q_n)}{(p_n-\sqrt{m}q_n)(p_n+\sqrt{m}q_n)}=-\dfrac{p_np_{n-1}-mq_nq_{n-1}+(p_{n-1}q_n-p_nq_{n-1}) \sqrt{m}}{p_n^2-mq_n^2}=$$

$$\dfrac{-(p_np_{n-1}-mq_nq_{n-1})+(-1)^n\sqrt{m}}{p_n^2-mq_n^2}=r_{n+1}\qquad(16)$$

Казалось бы противоречие сохраняется: для разложения $\sqrt{m}$ требуется знать величину $\sqrt{m}.$ Но чтобы получить один знак $a_{n+1}$ достаточно целой части $r_{n+1}$, а значит целой части $\sqrt{m}$, после чего вычисляются элементы дроби $\dfrac{p_{n+1}}{q_{n+1}}$ и далее по кругу. Сколько можно получить знаков из разложения (16), если брать $\sqrt{m}$ с точностью, имеющейся к моменту $n$, то есть $\dfrac{p_n}{q_n}$ – вопрос отдельный. В любом случае такое выражение может быть основой некоторого алгоритма разложения квадратного радикала. Обозначим знаменатель $p_n^2-mq_n^2=z_n$ и рациональную часть числителя $-(p_np_{n-1}-mq_nq_{n-1})=-b_n.$ Значение $z_n$ определено как разность величин, на порядок превосходящих результат, а это могут быть большие числа. При заявленном подходе такие вычисления приходится выполнять на каждом этапе, что есть существенный недостаток в сравнении с классической процедурой, где $z_n$ появляется естественным образом как знаменатель новой дроби после сокращения. Найти рекуррентную зависимость для членов последовательности $z_n$ – вполне себе технологический вопрос, который при $k>2$ оказывается чуть ли не самым интересным. Модифицированный алгоритм для $k=2$ уже выкладывался здесь: http://dxdy.ru/topic97794.html
Подставим теперь в (15) радикал степени $k>2$:

$$a_{n+1}=\left \lfloor -\dfrac{p_{n-1}-\sqrt[k]{m}q_{n-1}}{p_n-\sqrt[k]{m}q_n} \right \rfloor$$

и попробуем провести аналогичные преобразования:

$$-\dfrac{p_{n-1}-\sqrt[k]{m}q_{n-1}}{p_n-\sqrt[k]{m}q_n}=$$

$$-\dfrac{\left( p_{n-1}-q_{n-1}m^{\frac{1}{k}}\right) \left( p_n^{k-1}+p_n^{k-2}q_nm^{\frac{1}{k}}+p_n^{k-3}q_n^2m^{\frac{2}{k}}+...+p_n^2q_n^{k-3}m^{\frac{k-3}{k}}+p_nq_n^{k-2}m^{\frac{k-2}{k}}+q_n^{k-1}m^{\frac{k-1}{k}}\right)}{\left( p_n-q_nm^{\frac{1}{k}}\right)\left( p_n^{k-1}+p_n^{k-2}q_nm^{\frac{1}{k}}+p_n^{k-3}q_n^2m^{\frac{2}{k}}+...+p_n^2q_n^{k-3}m^{\frac{k-3}{k}}+p_nq_n^{k-2}m^{\frac{k-2}{k}}+q_n^{k-1}m^{\frac{k-1}{k}}\right)}=$$

$$-\frac{p_{n-1}p_n^{k-1}-mq_{n-1}q_n^{k-1}+\left( p_{n-1}q_n-p_nq_{n-1}\right)\left(p_n^{k-2}m^{\frac{1}{k}}+p_n^{k-3}q_nm^{\frac{2}{k}}+...+p_n q_n^{k-3}m^{\frac{k-2}{k}}+q_n^{k-2}m^{\frac{k-1}{k}}\right)}{p_n^k-mq_n^k}$$

В левых скобках числителя - ($\pm 1$), в правых – ($k-1$) слагаемых, приблизительно равных $\dfrac{p_n^{k-1}}{q_n}$, что следует из $\sqrt[k]{m}\approx \dfrac{p_n}{q_n}.$ Обозначим сумму в скобках $S$, слагаемые в порядке следования - $u_1,u_2,u_3,…,u_{k-1}$, и заметим, что произведение пар симметрично расположенных слагаемых $=m(p_nq_n)^{k-2}.$ Запишем
$u_1+u_{k-1}-2\sqrt{m(p_nq_n)^{k-2}}=(\sqrt{u_1}-\sqrt{u_{k-1}})^2$
$u_2+u_{k-2}-2\sqrt{m(p_nq_n)^{k-2}}=(\sqrt{u_2}-\sqrt{u_{k-2}})^2$

. . . . . . . . . . . . . . . .

$u_{k-1}+u_1-2\sqrt{m(p_nq_n)^{k-2}}=(\sqrt{u_{k-1}}-\sqrt{u_1})^2$
В полусумме имеем
$S-(k-1)\sqrt{m(p_nq_n)^{k-2}}=(\sqrt{u_1}-\sqrt{u_{k-1}})^2+(\sqrt{u_2}-\sqrt{u_{k-2}})^2+...$
Рассмотрим один из квадратов правой части.

$$(\sqrt{u_1}-\sqrt{u_{k-1}})^2=u_1+u_{k-1}-2\sqrt{m(p_nq_n)^{k-2}}\approx 2\dfrac{p_n^{k-1}}{q_n}-2\sqrt{\dfrac{p_n^k}{q_n^k}(p_n q_n )^{k-2}}\approx 0$$

То же и для остальных. Можно предположить, что с ростом $n$ сумма квадратов стремится к нулю, то есть $S\approx (k-1)\sqrt{m(p_nq_n)^{k-2}.$ Если это верно, то погрешность числителя в итоговой формуле

$$a_{n+1}=\left \lfloor \frac{-(p_{n-1}p_n^{k-1}-mq_{n-1}q_n^{k-1})+(-1)^n\cdot\sqrt{m(k-1)^2(p_nq_n )^{k-2}}}{p_n^k-mq_n^k} \right \rfloor \qquad(17)$$

бесконечно мала. В пользу этого предположения говорит и тот факт, что подстановка $k=2$ возвращает точное выражение (16). Формула хорошо подтверждается практикой, однако «стартовая» пара подх. дробей должна быть достаточно точной. Иначе получаем 0 или -1 на следующем этапе вычислений (цепные дроби – не та область, где можно пропустить ошибку). Сколько знаков можно получить из разложения (17) помимо одного, и с какой точностью брать при этом квадратный радикал в числителе – вопрос совсем уже отдельный. Вроде бы такой параметр должен расти, и возникает мысль об аппроксимации квадратичными иррациональностями, но тут заходим слишком далеко. В параллельной теме описан обобщенный алгоритм разложения вещественного корня полинома k-ой степени. Он "менее точен", но точность в данном случае не достоинство, поскольку добавить лишнюю подх. дробь на старте процесса не составляет труда.

По поводу рекуррентного правила последовательности $z_n=p_n^k-mq_n^k$ вопрос когда-то уже выкладывался в иной формулировке. Последовательность $p_n$, являясь функцией от последовательности $a_n$, задается двумя начальными членами $1,a_1$ и рекуррентным правилом: $p_{n+1}=a_{n+1}p_n+p_{n-1}.$ Последовательность $q_n$ отличается начальными членами: $0,1$. Если существует рекуррентное правило для последовательности $p_n^k$, где коэффициенты при членах последовательности – также функция от $a_n$, то оно верно и для $q_n^k$, и для $z_n=p_n^k-mq_n^k.$ Задачу возведения в k-ую степень удается свести к линейной системе из k-1 уравнений, но уже при k=2 решение выглядит витиевато:

$$z_{n+1}=\dfrac{a_{n+1}}{a_n}(a_{n+1}a_n+1)z_n+(a_{n+1}a_n+1)z_{n-1}-\dfrac{a_{n+1}}{a_n}z_{n-2}$$

Перепишем это так:

$$\frac{z_{n+1}}{a_{n+1}(a_{n+1}a_n+1)}=\frac{z_n}{a_n}+\frac{z_{n-1}}{a_{n+1}}-\frac{z_{n-2}}{a_n(a_{n+1}a_n+1)}$$

А лучше так:

$$k=2$$

$$\frac{z_{n+1}}{[a_{n+1}][a_n,a_{n+1}]}-\frac{z_n}{[a_n]}-\frac{z_{n-1}}{[a_{n+1}]}+\frac{z_{n-2}}{[a_n][a_n,a_{n+1}]}=0$$

$$k=3$$

$$\frac{z_{n+1}}{[a_{n+1}][a_n,a_{n+1}][a_{n-1},a_n,a_{n+1}]}-\frac{z_n}{[a_n][a_{n-1},a_n ]}-\frac{z_{n-1}}{[a_{n-1}][a_{n+1}]}+\frac{z_{n-2}}{[a_n][a_n,a_{n+1}]}+\frac{z_{n-3}}{[a_{n-1} ][a_{n-1},a_n][a_{n-1},a_n,a_{n+1}]}=0$$

$k=4$, не влезая в строку, выглядит аналогично, но «и т.д.» ставить рановато. Увидеть закономерность удается только с помощью матрицы (8), расставляя континуанты знаменателей по своим местам (как в пазлах):

Вложение:

M2.jpg [ 76.89 Кб | Просмотров: 0 ]

Положим k=5. Выберем 7 (k+2) элементов третьей строки, спроецируем их на нулевую диагональ, впишем вместо нулей соответствующие степени и очертим подматрицу с большой диагональю из выбранных степеней в качестве основания. Тогда произведение элементов подматрицы, «покрываемых» лучами, исходящими из каждой степени – и есть соответствующий ей знаменатель знакопеременного выражения. То есть

$$\frac{1849^5}{1\cdot 3\cdot 7\cdot 10\cdot 47\cdot 151}-\frac{551^5}{1\cdot 1\cdot 2\cdot 3\cdot 14\cdot 45}-\frac{196^5}{3\cdot 1\cdot 1\cdot 1\cdot 5\cdot 16}+$$

$$+\frac{159^5}{7\cdot 2\cdot 1\cdot 1\cdot 4\cdot 13}+\frac{37^5}{10\cdot 3\cdot 1\cdot 1\cdot 1\cdot 3}-\frac{11^5}{47\cdot 14\cdot 5\cdot 4\cdot 1\cdot 1}-\frac{4^5}{151\cdot 45\cdot 16\cdot 13\cdot 3\cdot 1}=0$$

Повторюсь, элементы строки и сама строка выбирались произвольно. В основании подматрицы могли быть степени элементов другой строки, суммы степеней элементов общего столбца из разных строк или многочлен с постоянными коэффициентами при k-ых степенях, в том числе и $z_n=p_n^k-mq_n^k$ (если $a_n$ – разложение радикала k-ой степени). Тут интерес уже не в $z_n$, а в неком универсальном свойстве матрицы (8), о применимости которого остается догадываться, хотя преодолеть подслеповатость Excel’я при разложении $\sqrt[11]{m}$ таким способом удается прекрасно. Гипотеза проверена в общем виде для k=5. Похоже на индукцию, где вместо логического перехода k - (k+1) употреблена умозрительная экстраполяция свойства матрицы (8) на (k+1)-ый уровень. Решение?

[Lia]

Тема перемещена из форума «Математика (общие вопросы)» в форум «Карантин»
по следующим причинам:

Для неограниченного редактирования.

Как только будет готово, сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

Возвращено.

[Andrey A]

P.S. Возведение в степень в числителях знакопеременного выражения (матрица 8) оказывается вроде бы частным случаем. Вместо $k$-ых степеней там могут стоять произведения $k$ элементов соответсвующего столбца на пересечении фиксированных строк - различных или не различных (как в примере), т.е. одночлены $k$-ой степени. Такая свобода чревата тривиальной причиной, непонятно только какой. Рекуррентное правило для $k$-ых степеней последовательностей подобных фибоначчи должно тогда продолжаться на призведения $k$ последовательных членов или с заданной разностью номеров. Что и не удивительно. Численно подтверждается, но общий случай доказать не берусь.

[Andrey A]

Upd 17.01

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

Такая свобода чревата тривиальной причиной, непонятно только какой.

Глупость написал сгоряча. Возведение в степень эквивалентно умножению по той простой причине, что начальные члены отсутствуют как в итоговых выражениях, так и в самих уравнениях. В результате имеем умножение $k$ последовательностей, объединенных общей рекуррентной зависимостью $q_{n+1}=a_{n+1}q_n+q_{n-1}$ с произвольными парами начальных членов - ответ на вопрос http://dxdy.ru/topic72028.html. Убирая требование целочисленности $a_n$, можно задавать одну из $k$ последовательностей произвольно: последовательность $a_n=\frac{q_n-q_{n-2}}{q_{n-1}}$ определена, значит определена и подматрица с $k+2$ нулями в большой диагонали. Если, конечно, гипотеза верна.

[Andrey A]

В дополнение

Правило Эйлера, упомянутое выше, трактует континуанту как сумму одночленов, образованных вычеркиванием всех возможных пар соседних членов из одночлена $a_1 a_2...a_n$, включая нулевую пару. Возьмем это за определение и попробуем вычеркивать бо́льшее количество соседних членов. Например тройки. Первым одночленом, из которого удается вычеркнуть тройку оказывается $a_1a_2a_3$. Возникает последовательность

$$a_1,\ a_1a_2,\ a_1a_2a_3+1,\ a_1a_2a_3a_4+a_4+a_1,\ a_1a_2a_3a_4a_5+a_4a_5+a_1a_5+a_1a_2,\ a_1a_2a_3a_4a_5a_6+a_4a_5a_6+...+1,...$$

Похоже на обычные континуанты. Разница в том, что остатком деления $n$-го члена последовательности на $(n-1)$-ый оказывается не $(n-2)$-ой, а $(n-3)$-ий член, и для восстановления знаков $a_n$ посредством деления с остатком требуются стартовые значения не двух величин, а трех. Верно и обратное: каждые три натуральных числа $p_n>q_n>r_n$ , не имеющих общего делителя $>1$, однозначно отобразимы континуантами вида $[a_1,a_2,a_3,...a_n]_3,[a_2,a_3,...a_n]_3,[a_3,...a_n ]_3$ с той оговоркой, однако, что число $0$ становится полноправным членом последовательности $a_n$, поскольку уже остаток от деления $p_n$ на $q_n$ не обязан быть $<r_n$. Новые остатки заносятся в конец списка, неполные частные фиксируются обычным порядком, и процесс заканчивается при достижении двух последовательных нулевых остатков*. Для опытов, впрочем, удобно по-прежнему задавать последовательность $a_n$ в натуральных числах, а также тройную последовательность дробей – аналог подходящих дробей, которая в общем виде выглядит так:

$$\begin{matrix} a_1 & a_1a_2 & a_1a_2a_3+1 & ... & p_i=a_ip_{i-1}+p_{i-3} & ... & p_{n-2} & p_{n-1} & p_n \\ 1 & a_2 & a_2a_3 & ... & q_i=a_iq_{i-1}+q_{i-3} & ... & q_{n-2} & q_{n-1} & q_n \\ 0 & 1 & a_3 & ... & r_i=a_ir_{i-1}+r_{i-3} & ... & r_{n-2} & r_{n-1} & r_n \end{matrix}\ \left ( 18 \right )$$

Всё сказанное верно и для $k>3$, если вычеркивать из одночлена $a_1 a_2…a_n$ не тройки, а $k$ соседних членов $(p_i=a_ip_{i-1}+p_{i-k})$, но для удобства оставим пока в примерах $k=3$. Правило обратного движения $(1)$ по-прежнему в силе, это следует из самого принципа образования полиномов, как и взаимная простота элементов $i$-го столбца из $k$ элементов. Дробь в обратном движении $a_n,a_{n-1},...,a_1$ соответствуют замене строк на столбцы (поворот на $180°$) в матрице, образованной последними $k$ столбцами $(18)$, и главное: $\det \begin{pmatrix} p_{n-2} & p_{n-1} & p_n\\ q_{n-2} & q_{n-1} & q_n\\ r_{n-2} & r_{n-1} & r_n \end{pmatrix}=(-1)^{(n-1)(k-1)}$, что является обобщением $(4)$. Для первых $k$ столбцов это утверждение можно проверить непосредственно, остальное доказывается по индукции. Последовательность подходящих дробей можно также продолжить до треугольной матрицы, аналогичной матрице $(8)$, свойства которой в обобщенном виде вызывают любопытство, но на этом видимые аналогии заканчиваются. Главная недостающая аналогия: $\dfrac{p}{q}\rightarrow \begin{matrix} p \\ q \\ r \end{matrix}$. Что такое дробь из $k$ знаков? Свойства медианты в образовании последовательности $(18)$ задействованы в полной мере, но имеет ли смысл утверждение:
$\begin{matrix} p_1+p_2 \\ q_1+q_2 \\ r_1+r_2 \end{matrix}$ принадлежит интервалу ( $ \begin{matrix} p_1 \\ q_1 \\ r_1 \end{matrix}\ , \begin{matrix} p_2 \\ q_2 \\ r_2 \end{matrix}$), может быть это тройки пространственных координат? Что-то вроде $k$-мерной модели Клейна**, но если точка с целыми координатами на плоскости задает рациональную точку на числовой оси, то что задает точка с целыми координатами в $k$-мерном пространстве? Сходятся ли в трехмерном пространстве точки с координатами $(p_i,q_i,r_i )$, если бесконечная последовательность $a_n$ периодична? Можно сомневаться в содержательности подобных вопросов, но было бы странно, если столь органичная конструкция не имела бы под собой «физического смысла».

Из $(18)$ видно, что для любого $k\leq n$ конечная последовательность $a_n$ строго определяет квадратную матрицу из $k$ последних столбцов. Сохраняя $k=3$, запишем $a_1,a_2,...,a_n=\begin{pmatrix} p_{n-2} & p_{n-1} & p_n\\ q_{n-2} & q_{n-1} & q_n\\ r_{n-2} & r_{n-1} & r_n \end{pmatrix}$ , $b_1,b_2,...,b_m=\begin{pmatrix} P_{m-2} & P_{m-1} & P_m\\ Q_{m-2} & Q_{m-1} & Q_m\\ R_{m-2} & R_{m-1} & R_m \end{pmatrix}$ . Имеет место соотношение:

$$a_1,a_2,...,a_n,b_1,b_2,...,b_m=\begin{pmatrix} p_{n-2} & p_{n-1} & p_n\\ q_{n-2} & q_{n-1} & q_n\\ r_{n-2} & r_{n-1} & r_n \end{pmatrix}\begin{pmatrix} Q_{m-2} & Q_{m-1} & Q_m\\ R_{m-2} & R_{m-1} & R_m\\ P_{m-2} & P_{m-1} & P_m \end{pmatrix}$$

Последний столбец матрицы-произведения получается умножением $\begin{pmatrix} p_{n-2} & p_{n-1} & p_n\\ q_{n-2} & q_{n-1} & q_n\\ r_{n-2} & r_{n-1} & r_n \end{pmatrix}\begin{pmatrix}Q_m\\ R_m\\ P_m \end{pmatrix}$

Матрица-множитель образуется из матрицы $b_m$ переносом верхней строки (элемента столбца) вниз. Появляется возможность сформулировать понятие $(n+1)$-го остатка дроби хотя бы на языке матриц, но удивительное дело: такое умножение оказывается обратимо, поскольку определитель системы уравнений, возникающей при решении обратной задачи равен $\pm 1$, и она всегда имеет целые решения. А вот положительные знаки $(n+1)$-го остатка дроби $b_1,b_2,…,b_m$ удается получить только при большом везении. К появлению отрицательных знаков дроби следует отнестись осторожно. Для задачи http://dxdy.ru/post1244374.html#p1244374, с которой всё и началось, такое расширение даже желательно, но разложение рациональной точки $\dfrac{83}{11}=7,1,1,5$ единственное в положительных числах, при допущении знака "$-1$" может быть таким: $1,2,3,4,5,6,7,-1,1,6,6,5,4,3,1,1,5,1,1,5.$ Или таким: $2,2,2,2,2,-1,1,1,2,2,1,1,4,1,1,5.$ И еще сколько угодно вариантов. Любые две дроби могут быть соединены цепочкой подходящих дробей, но содержательный смысл таких последовательностей если и есть, то иной (например, таким способом можно определить «вычитание» - действие, обратное «сложению» из первого оффтопика). В итоге вопросов больше чем ответов, как и положено. Случай $a_1=a_2=...=a_n=1$ описан в посте http://dxdy.ru/post1253915.html#p1253915 Выпишу еще на всякий случай последовательность подходящих дробей для $k=5$:

$$\begin{matrix} a_1 & a_1a_2 & a_1a_2a_3 & a_1a_2a_3a_4 & a_1a_2a_3a_4a_5+1 & ... & p_i=a_ip_{i-1}+p_{i-5} & ...\ \\ 1 & a_2 & a_2a_3 & a_2a_3a_4 & a_2a_3a_4a_5 & ... & q_i=a_iq_{i-1}+q_{i-5} & ...\ \\ 0 & 1 & a_3 & a_3a_4 & a_3a_4a_5 & ... & r_i=a_ir_{i-1}+r_{i-5} & ...\ \\ 0 & 0 & 1 & a_4 & a_4a_5 & ... & s_i=a_is_{i-1}+s_{i-5} & ...\ \\ 0 & 0 & 0 & 1 & a_5 & ... & t_i=a_it_{i-1}+t_{i-5} & ...\ \end{matrix}\begin{matrix} p_{n-4} & p_{n-3} & p_{n-2} & p_{n-1} & p_n\\ q_{n-4} & q_{n-3} & q_{n-2} & q_{n-1} & q_n\\ r_{n-4} & r_{n-3} & r_{n-2} & r_{n-1} & r_n\\ s_{n-4} & s_{n-3} & s_{n-2} & s_{n-1} & s_n\\ t_{n-4} & t_{n-3} & t_{n-2} & t_{n-1} & t_n \end{matrix}$$

* при образовании нулевого остатка с последующим положительным знаком следует брать вместо полного частного неполное $(a_i-1)$. В общем случае процесс деления заканчивается при образовании $k-1$ нулевых остатков, при образовании меньшего кол-ва нулевых остатков с последующим положительным знаком полные частные меняются на неполные $(a_i-1)$ и процесс продолжается.
** Г. Дэвенпорт приводит геометрическую интерпретацию непрерывных дробей Клейна на стр. 112 введения в теорию чисел.

[Andrey A]

Кажется, тут есть проблема, о которой мне следовало позаботиться прежде чем постить. Прячу пока в оффтопик.

(проблема)

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

Дробь в обратном движении $a_n,a_{n-1},...,a_1$ соответствуют замене строк на столбцы (поворот на $180°$) в матрице, образованной последними $k$ столбцами $(18)$

Относительно алгоритма восстановления главной матрицы это утверждение в силе. Но если понимать его в том смысле, что результаты разложения правого столбца и верхней строки матрицы зеркальны, то оно верно только для дробей с положительными элементами $(a_i>0)$. С нулями дело не чисто. Лучше на примере:
разлжение $\begin{pmatrix} 83\\ 53\\ 47\\ 17\end{pmatrix}$ $(k=4)$, ведет с большим количеством нулей к матрице $\begin{pmatrix} 10& 29 & 57 & 83\\ 6& 20 & 41 & 53\\ 5& 18 & 38 & 47\\ 1 & 5 & 13 & 17 \end{pmatrix}$. Разложение верхней строки дает непохожую дробь с меньшим количеством знаков и матрицу $\begin{pmatrix} 4& 38 & 57 & 83\\ 4& 38 & 56 & 57\\ 1& 11 & 29 & 29\\ 0 & 1 & 10 & 10 \end{pmatrix}$. Потом $\begin{pmatrix} 19& 47 & 75 & 83\\ 10& 29 & 56 & 57\\ 1& 11 & 38 & 38\\ 0 & 1 & 4 & 4 \end{pmatrix}$ и дробь поменьше. Тут, конечно, хотелось получить приведенную матрицу со знаком $83$ в правом верхнем углу и дробью без нулей. Но результат озадачил:

$$\begin{pmatrix} 4& 14 & 47 & 83\\ 4& 14 & 46 & 75\\ 1& 5 & 19 & 47\\ 0 & 1 & 5 & 19 \end{pmatrix}=1,1,2,2,0,3,2,0,7,0,1,3,1=1,1,2,0,0,3,0,2,7,0,3,3,1$$

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

[Andrey A]

Подытожу. Замена строк главной матрицы на столбцы и обратно (разворот на $180°$) соответствует дроби, восстановленной в обратном движении от $a_n$ к $a_1$. Каждому столбцу из $k$ знаков можно сопоставить «обратный по модулю» столбец с общим старшим членом, полученный из перевернутой верхней строки. Проблема в том, что взаимное соответствие при таком сопоставлении достигается только относительно алгоритма восстановления. Разложение верхней строки может возвратить дробь в обратном движении, но не обязательно. Будем называть дробь приведенной, если она может быть получена в прямом и обратном движении разложениями правого столбца и верхней строки главной матрицы. Оценить «состояние приведенности», не прибегая к процедуре, уже для $k=3$ составляет задачу, и первым делом под подозрение попадают дроби с нулями. Оказывается, однако, что для достаточно большого $m$ при заданном $k$ приведенных дробей с нулями находится не меньше других. Для $m=77$, например,

$$\begin{pmatrix} 77\\ 18\\ 11 \end{pmatrix}=4,1,2,0,6,0,5,1=\begin{pmatrix} 9 & 49 & 77\\ 2 & 11 & 18\\ 2 & 10 & 11 \end{pmatrix},\begin{pmatrix} 77\\ 49\\ 9 \end{pmatrix}=1,5,0,6,0,2,1,4=\begin{pmatrix} 11 & 18 & 77\\ 10 & 11 & 49\\ 2 & 2 & 9 \end{pmatrix}.$$

А у приведенной дроби без нулей $2,1,3,2,1,3,1=\begin{pmatrix} 18 & 61 & 77\\ 8 & 27 & 34\\ 7 & 24 & 30 \end{pmatrix}$ находится вдруг попутчик $1,1,2,1,2,3,1,2=\begin{pmatrix} 30 & 34 & 77\\ 23 & 26 & 59\\ 17 & 19 & 43 \end{pmatrix}$, так что положительные знаки тоже не дают гарантии. Получить приведенные дроби для фиксированного $m$ удается с помощью процедуры, описанной в оффтопике выше (последовательное разложение вновь образованной верхней строки). Она ведет к циклу из двух шагов, больше пока не наблюдалось. В принципе проблема единообразия имеется в зародыше уже при $k=2$. Тут она порождает маленькую игру, добавляя неопределенности, но не более. Главных вопросов это не снимает.