Описание
Часть 2

5. Некоторые факты, связанные с дробями.

5.1. Циклические числа.

Возьмем натуральное число и будем каждый раз переставлять начальную цифру в конец. Полученные числа называют циклическими перестановками исходного числа. Например, циклическими перестановками 12345 являются числа 23451, 34512, 45123, 51234. $n$-значное число называется циклическим, если его произведения на числа 2, 3 … (n-1) являются циклическими перестановками исходного числа.

Наиболее известным циклическим числом является 142857. Действительно, умножение числа на первые 6 натуральных чисел дает: $$ \begin{array}{cc} 142857 \cdot 1 = 142857 \; & \; 142857 \cdot 2 = 285714 \\ 142857 \cdot 3 = 428571 \; & \; 142857 \cdot 4 = 571428 \\ 142857 \cdot 5 = 714285 \; & \; 142857 \cdot 6 = 857142 \end{array} $$

Кстати, число 142857 где-то уже встречалось. Если не помните, то подскажу, продолжив список умножений: $$ 142857 \cdot 7 = 999999 $$

Вспомнили? Действительно, 142857 есть не что иное, как период десятичного представления дроби $\frac{1}{7}$. Отличительной особенностью этого периода является то, что его длина на единицу меньше знаменателя, так что при делении «уголком» все натуральные числа меньшие знаменателя окажутся среди остатков. Поэтому периоды дробей $\frac{2}{7}$, $\frac{3}{7}$ … $\frac{6}{7}$ являются циклическими перестановками периода дроби $\frac{1}{7}$. Понятно что умножение периода 142857 на числа от 1 до 6 равносильно умножению $\frac{1}{7}$ на эти числа, так что циклические свойства числа 142857 вполне объяснимы.

Как мы уже знаем, длина периода десятичного представления дроби $\frac{1}{n}$, которую мы обозначили через $\lambda(n)$, является делителем функции Эйлера $\varphi(n)$. Число $n$, не делящееся на 2 и на 5, назовем полнопериодным (англ. full repetend), если $\lambda(n)=\varphi(n)$. В этом случае, все натуральные числа, меньшие $n$ и взаимно простые с $n$ появляются среди остатков от деления $1$ на $n$, так умножение периода дроби $\frac{1}{n}$ на такие числа дает циклические перестановки периода.

Более того, если $n$ — полнопериодное число, а $A$ — период десятичной представления дроби $\frac{1}{n}$, то, согласно равенству (2.3.3), $$ \frac{1}{n} = \frac{A}{10^{\varphi(n)}-1} $$ откуда $$ А = \frac{10^{\varphi(n)}-1}{n} \label{eq:5.1.1}\tag{5.1.1} $$

Тот факт, что выражение в правой части является целым, вытекает непосредственно из утверждения 4.3.3 (частный случай теоремы Эйлера), однако равенство $\eqref{eq:5.1.1}$ придает частному от деления определенный смысл.

В частности для простого полнопериодного числа $p$ равенство $\eqref{eq:5.1.1}$ превращается в $$ А = \frac{10^{p-1}-1}{p} \label{eq:5.1.2}\tag{5.1.2} $$

Выражение в правой части является «десятичным случаем» частного Ферма (Fermat quotient), которое в общем виде записывается как $q_p(a) = \dfrac{a^{p-1}-1}{p}$ ($p$ — простое число). Интересные свойства частных Ферма приведены в Википедии.

Из вышеприведенных рассуждений может показаться, что для любого полнопериодного простого $p$, число, задаваемое формулой $\eqref{eq:5.1.2}$ является циклическим. Так-то оно так, но…

Следующим после 7 простым полнопериодным числом является 17, для которого $$ \frac{1}{17} = 0,(0588235294117647) $$

Таким образом, мы нашли еще одно циклическое число, так что … минуточку! Цифра 0 в начале периода смотрится без проблем, однако тот же нуль в начале числа 0588235294117647 выглядит не вполне убедительно. С другой стороны, исключить ведущий нуль нельзя, так как от этого число перестает быть циклическим, например: $588235294117647 \cdot 2 = 1176470588235294$, где 0 присутствует в произведении, но не в исходном числе.

Понятно, что если $p \gt 10$, период десятичной дроби для $\frac{1}{p}$ обязательно начинается с нуля (причем возможно не единственного). Поскольку 7 - единственное однозначное полнопериодное простое число, число 142857 возможно является единственным «полноценным» циклическим числом.

Слово «возможно» в последней фразе появилось не случайно, поскольку из предыдущих рассуждений вовсе не следует, что всякое циклическое число является периодом некоторой дроби. В частности, число с нечетным количеством знаков никак не может быть периодом $\frac{1}{p}$ для полнопериодного простого $p$, хотя не вполне очевидно, что оно не может быть циклическим.

«Является ли всякое циклическое число (пусть даже с ведущими нулями) периодом десятичной дроби?» (отсюда сразу следует, что это дробь видa $\frac{1}{p}$, где $p$ — полнопериодное простое число). Эквивалентная формулировка вопроса: «Всякое ли циклическое число является частным Ферма, то есть представимо в виде $\eqref{eq:5.1.2}$?». Наконец, еще одна эквивалентная формулировка (возможно наиболее простая для доказательства): «Пусть $A$ — $n$-значное циклическое число. Всегда ли $А(n+1)=10^n-1$?». Статья в Википедии не задумываясь, дает утвердительный ответ на эти вопросы, хотя все мои попытки найти доказательство не увенчались успехом, что оставляет, хотя и очень малый, шанс найти в десятичной системе другое циклическое число.

Если поверить Википедии и ограничиться рассмотрением циклических чисел, представимых в виде частных Ферма, то десятичная система, где есть лишь одно циклическое число, окажется не столь плоха, как, например, шестиричная или шестнадцатеричная системы (с основаниями 6 и 16), где (как можно проверить, используя все тот же Калькулятор позиционной дроби) циклических чисел нет. Зато 12-ичная система обладает двумя циклическими числами: 2497₁₂ и 186Т35₁₂, получаемыми при p=5 и 7 соответственно (напомню, что Т — двенадцатеричное 10), так что даже в этом контексте она лучше десятичной! Наконец, в 17-ичной системе есть целых 4 полноценных циклических числа (исключая тривиальное 8, период $\frac{1}{2}$): 5B₁₇, 36DA₁₇, 274E9C₁₇, 194ADF7C63₁₇, соответствующие p = 3, 5, 7, B₁₇ (17-ичные цифры A-G, соответствуют десятичным 10-16).

5.2. Теорема Миди́.

Снова обратимся к уже изрядно заезженной дроби $\frac{1}{7}=0,(142857)$. Разделим период на две одинаковые части и сложим их: $142 + 857 = 999$. Получили число из одних девяток. Не слишком ли часто они стали встречаться? Попробуем еще: $\frac{1}{13}=0,(076923)$. Число 13 не является полнопериодным, но все же: $076 + 923 = 999$. Б-р-р-p! А как насчет $\frac{1}{21}=0,(047619)$? Считаем: $047+619=666$. Наконец-то! Даже звериное 666 вызвало меньше злости, чем вездесущие девятки!

Уловили закономерность? Вот она:

5.2.1. (Теорема Миди́.) Рассмотрим несократимую дробь, знаменатель которой — простое число, отличное от 2 и 5. Если период десятичного представления дроби имеет четную длину, сумма обеих половин периода дает число, составленное из одних девяток. Другими словами, если $p$ — простое число, отличное от 2 и 5, $m$ не кратно $p$ и $$ \frac{m}{p} = \overline{0,(a_1a_2 \dots a_na_{n+1} \dots a_{2n})} \;, $$ то $$ \overline{a_1a_2 \dots a_n} + \overline{a_{n+1}a_{n+2} \dots a_{2n}} = 10^{\,n}-1 = \underbrace{99 \dots 9}_{n \; \text{девяток}}\;. $$

Заметим, что последнее равенство равносильно следующему $$ a_i + a_{i+n} = 9, \quad i=1,2 \dots n \;, $$ то есть сумма цифр, отстоящих на пол-периода друга от друга равна 9.

Как вы уже конечно догадались, этот изящный факт был получен французским (точнее нормандским) математиком Этьеном Миди (Étienne Midy), а опубликовано это было (по историческим меркам) сравнительно недавно: «E. Midy, "De Quelques Propriétés des Nombres et des Fractions Décimales Périodiques". Collège Royal de Nantes, 1836»

На самом деле, имеет место более общий факт:

5.2.2. (Расширенная теорема Миди́ — Extended Midy's theorem) Рассмотрим несократимую дробь, знаменатель которой — простое число, отличное от 2 и 5. Если период десятичного представления дроби разбить на части равной длины $k$, сумма этих частей кратна $10^k-1 = \underbrace{99 \dots 9}_{k \; \text{девяток}}$.

Для иллюстрации вновь обратимся к пресловутому 142857, которое в этот раз разобьем на 3 части, по две цифры в каждой: $14 + 28 + 57 = 99$. Другой пример: $\frac{1}{19}=0,(052631578947368421)$. Разбивая период на 6 трехзначных чисел, получаем: $052 + 631 + 578 + 947 + 368 + 421 = 2997 = 3 \cdot 999$. В этот раз вместо 999 получили кратное ему число.

Такое настойчивое появление девяток может показаться невероятным, однако наша бесценная Википедия (как приятно рекламировать сайт, не содержащий рекламы!) и в этом раз выручает, предлагая довольно простое доказательство теорем, приводимое ниже с небольшой привязкой к контексту данной публикации. Вот ссылка на источник.

Вначале докажем одно вспомогательное утверждение, представляющее также самостоятельный интерес:

5.2.3 Пусть $p$ — простое число, отличное от 2 и 5, $n=\lambda(p)$. Тогда период десятичного представления несократимой дроби со знаменателем $p$ кратен $10^{\,k}-1 = \underbrace{99\dots9}_{k\;\text{девяток}}$, где $k$ — некоторый отличный от $n$ делитель числа $n$.

Делитель числа, отличный от самого числа, называется собственным делителем (англ. proper divisor).

Например, собственными делителями $\lambda(7)=6$ являются числа 1, 2, 3. Поэтому число 142857, а также все его циклические перестановки, делятся на 9, 99 и 999. Также $\lambda(13)=6$, поэтому периоды дробей $\frac{a}{13}$ (76923, 153846, 230769 и т.д) также делятся на 9, 99 и 999.

Докажем 5.2.3. Пусть $S$ — период несократимой дроби $\frac{m}{p}$, а $n$ — длина периода. Согласно равенству (2.3.3), $$ \frac{m}{p} = \frac{S}{10^{\,n}-1}\;, \label{eq:5.2.1}\tag{5.2.1} $$ причем (утверждение 4.1.1) $n$ — наименьшее из $i$ при которых $10^{\,i}-1$ делится на $p$.

Пусть $k$ — делитель $n$, причем $k \lt n$. Таким образом, $n=kj$, где $j \gt 1$ — целое число, поэтому $10^{\,n}-1 = \left(10^{\,k}\right)^j - 1$, что согласно 4.1.4, делится на $10^{\,k} - 1$. Следовательно, $10{\,^n}-1=r(10^{\,k}-1)$, где $r$ — целое число, так чтo $\ref{eq:5.2.1}$ можно переписать в виде $$ \frac{m}{p} = \frac{S}{r\left(10^{\,k}-1\right)}\;. \label{eq:5.2.2}\tag{5.2.2} $$

Выходит, что дробь в правой части $\eqref{eq:5.2.2}$ является расширением несократимой дроби $\frac{m}{p}$. Отсюда $r\left(10^{\,k}-1\right)$ делится на $p$. С другой стороны, из упомянутой минимальности длины периода $n$ и $k \lt n$ следует, что $10^{\,k}-1$ не делится на $p$. Поскольку $p$ — простое, это означает, что $10^{\,k}-1$ и $p$ — взаимно простые числа, так что $r$ обязано делиться на $p$.

Перепишем $\eqref{eq:5.2.2}$ в виде: $$ \frac{mr}{p} = \frac{S}{10^{\,k}-1}\;. \label{eq:5.2.3}\tag{5.2.3} $$

Так как $r$ делится на $p$, левая часть $\eqref{eq:5.2.3}$ — целое число, поэтому правая часть — также целое, то есть $S$ делится на $10^{\,k}-1$, что и требовалось доказать.

Попутно получили еще одно утверждение, не имеющее прямого отношения к периодическим дробям:

5.2.4 Пусть $p$ — простое число, отличное от 2 и 5, $n=\lambda(p)$, $k$ — собственный делитель числа $n$. Если $j=\frac{n}{k}$, то $10^{\,(j-1)k} + 10^{\,(j-2)k} + \dots 10^{\,k} + 1$ делится на $p$.

В самом деле, как было установлено при доказательстве 5.2.3, число $r=\dfrac{10{\,^n}-1}{10^{\,k}-1}$ делится на $p$. Но $$ r = \frac{\left(10^{\,k}\right)^j - 1}{10^{\,k}-1} = 10^{\,(j-1)k} + 10^{\,(j-2)k} + \dots 10^{\,k} + 1\,. $$

Пример: Так как $\lambda(7)=\lambda(13)=6$, то числа $10^4+10^2+1=10101\;\;(k=2)$ и $10^3+1=1001\;\;(k=3)$ делятся на 7 и 13.

Настало время вспомнить, как все начиналось, и доказать расширенную теорему Миди (утверждение 5.2.2) откуда, как будет показано ниже, утверждение 5.1.1 следует, как частный случай.

Итак, $S$ – период несократимой дроби, $n$ — длина периода. Выпишем разряды периода: $$ S=\overline{a_1 a_2 \dots a_n} $$

Если $k$ — собственный делитель длины периода $n$, то $n=jk$, где $j$ — целое число, большее 1. Разделим период $S$ на $j$ частей длиной $k$ каждая. Получаем: $$ S_{j-1} = \overline{a_1a_2 \dots a_k} \\ S_{j-2} = \overline{a_{k+1}a_{k+2} \dots a_{2k}} \\ \dots \\ S_1 = \overline{a_{n-2k+1}a_{n-2k+2} \dots a_{n-k}} \\ S_0 = \overline{a_{n-k+1}a_{n-k+2} \dots a_{n}} \\ $$

Таким образом весь период $S$ можно записать, как $$ S = S_{j-1} 10^{\;(j-1)k} + S_{j-2} 10^{\;(j-2)k} + \dots + S_110^k + S_0 \label{eq:5.2.4}\tag{5.2.4} $$

Пусть $N$ - сумма частей периода: $$ N = S_{j-1} + S_{j-2} + \dots + S_1 + S_0 \label{eq:5.2.5}\tag{5.2.5} $$

Вычитая $\eqref{eq:5.2.5}$ из $\eqref{eq:5.2.4}$, получаем: $$ S-N = S_{j-1} (10^{\;(j-1)k}-1) + S_{j-2} (10^{\;(j-2)k}-1) + \dots + S_1 (10^{\;k}-1) $$

Заметим, что каждое выражение в скобках имеет вид $10^{\,qk}-1 = \left(10^{\,k}\right)^q-1$ и делится на $10^{\,k}-1$. Поэтому правая часть, а следовательно и левая часть $S-N$ делится на $10^{\,k}-1$. С другой стороны, как вытекает из доказанного утверждения 5.2.3, $S$ также делится на $10^{\,k}-1$. Таким образом, $N = S-(S-N)$ делится на $10^{\,k}-1$, что подводит черту под доказательством расширенной теоремы Миди.

На этом можно … Но ведь было обещано вернуться к утверждению 5.2.1, то есть «классической» теореме Миди. Поэтому придется сделать еще один глубокий вдох и выдох, прежде чем окончательно разделаться с этой частью.

Итак, пусть длина периода $n=2k$. Делим период на две части $A_1$ и $A_2$ длиной $k$ каждая и находим их сумму $N = A_1 + A_2$. Как было доказано, $N$ кратно $10^{\,k}-1$. С другой стороны, каждое из $A_1$ и $A_2$ содержит не более $k$ цифр. При этом хотя бы одно из них должно быть ненулевым и хотя бы одно из них не должно состоять из $k$ девяток, поскольку периоды (0) и (9) исключены из рассмотрения. Отсюда $0 \lt N \lt 2\cdot \left(10^{\,k}-1\right)$, то есть $N = 10^{\,k}-1$. Далее заметим, что при сложении цифр $A_1$ и $A_2$ перенос в старший разряд невозможен, поэтому сумма каждой пары цифр должна быть равна 9.

Вот теперь … нет не всё! Как вы конечно догадались, теорема Миди и связанные с ней результаты применимы к системе счисления с произвольным основанием. Достаточно число 10 заменить основанием системы $b \gt 1$. Вот что получается:

Обобщение 5.2.1 и 5.2.2: Рассмотрим несократимую дробь, знаменатель которой — простое число, не являющееся делителем основания $b$. Если период $b$-ичного представления дроби разбить на части равной длины $k$, сумма этих частей кратна $b^k-1$ (то есть числу, составленному в $b$-ичной системе из $k$ разрядов величины $b-1$). В частности, если период разбить на две части длиной $k$ каждая, то сумма частей равна $b^k-1$.

Обобщение 5.2.3: Пусть $p$ — простое число, не являющееся делителем основания системы счисления $b$, а $n=\lambda(p)$. Тогда период $b$-ичного представления несократимой дроби со знаменателем $p$ кратен $b^k-1$, где $k$ — некоторый собственный делитель числа $n$.

Обобщение 5.2.4: Пусть $p$ — простое число, не являющееся делителем основания системы счисления $b$, а $n=\lambda(p)$. Если $k$ — некоторый собственный делитель числа $n$ и $j=\frac{n}{k}$, то $b^{(j-1)k} + b^{(j-2)k} + \dots b^{k} + 1$ делится на $p$.

6. Альтернативные представления рациональных чисел.

6.1. Египетские дроби

Как вы наверное заметили, для вычисления $\lambda(n)$ достаточно рассмотреть дробь с числителем равным 1, поскольку такая дробь является заведомо несократимой. Дробь, числитель которой равен 1, а знаменатель положителен называется аликвотной (англ. aliquot fraction от от лат. aliquot — «несколько», «содержащееся в целом количестве»).

Исследования показывают, что аликвотные дроби были первыми дробями, которыми оперировали люди. Представление дроби в качестве суммы попарно различных аликвотных дробей широко использовалось в древнем Египте, при этом записывались только знаменатели. Такое представление будем называть египетской дробью и записывать с использованием квадратных скобок.

В качестве примера приведу задачу из древнеегипетского папируса Ахмеса (годы жизни: 1680-1620 до нашей эры): «Как разделить 7 хлебов между 8 людьми». Казалось бы нет ничего проще: каждый получает по $\frac{7}{8}$ хлеба. Но как это сделать, произведя наименьшее количество разрезов? Понятно, что делить каждый хлеб на 8 частей, делая 49 разрезов — не самая удачная идея. Ситуация проясняется, если представить $\frac{7}{8}$ в виде египетской дроби: $[2, 4, 8]$, что соответствует $\frac{1}{2} + \frac{1}{4} + \frac{1}{8}$. Таким образом, каждый получает половину, четверть и осьмушку хлеба, для чего режем 4 хлеба пополам, 2 хлеба на 4 части и лишь один хлеб на 8 частей. При этом общее количество разрезов становится равным $4 + 2 \cdot 3 + 7 = 17$.

Рассмотрим общее решение задачи о делении $a$ хлебов между $b$ людьми. Так как все сводится к дроби $\frac{a}{b}$, которую при необходимости можно сократить, будем считать $a$ и $b$ взаимно простыми. Кроме того, дробь $\frac{a}{b}$ можно считать правильной. В самом деле, пусть имеется 19 хлебов и 8 человек. Выделяем целую часть: $\frac{19}{8} = 2\frac{3}{8}$ и даем каждому по 2 целых хлеба, сводя таким образом задачу к представлению правильной положительной дроби $\frac{3}{8}$ в виде египетской.

Итак, пусть дана несократимая правильная положительная дробь $\frac{a}{b}$, которую следует представить в виде суммы попарно различных аликвотных дробей. Если $a=1$, дробь уже является аликвотной, так что ее египетское представление состоит только из элемента $b$. Поэтому будем считать, что $a \gt 1$.

Первая мысль — найти наибольшую аликвотную дробь, не превосходящую заданную. Знаменатель такой дроби $q_1$ является наименьшим из целых $q$, для которых $\frac{1}{q} \leqslant \frac{a}{b}$, откуда $q_1$ — наименьшее из целых $q$, для которых $q \geqslant \frac{b}{a}$. Другими словами, $q_1$ является округлением $\frac{b}{a}$ до целого с избытком. Такое округление записывается с помощью верхних квадратных скобок: $$ q_1 = \left \lceil \frac{b}{a} \right \rceil \label{eq:6.1.1}\tag{6.1.1} $$ (Подробнее о верхних и нижних квадратных скобках, также известных, как функции ceil и floor можно прочесть в публикации этого блога «О целом дроби и о дроби в целом»)

Из $\eqref{eq:6.1.1}$ следует, что $$ q_1-1 \lt \frac{b}{a} \leqslant q_1 \label{eq:6.1.2}\tag{6.1.2} $$

В свою очередь из несократимости $\frac{a}{b}$, а также $a \gt 1$ следует, что $\frac{b}{a}$ — дробное число, поэтому фактически оба неравенства в $\eqref{eq:6.1.2}$ являются строгими. Это означает, что $s=q_1 - 1$ есть частное от деления $b$ на $a$ с остатком.

Итак, делим $b$ на $a$ с остатком: $$ b = as + t, \quad \text{причем}\; 0 \lt t \lt a $$ или $$ b = aq_1 - r, \quad \text{где}\quad q_1 = s+1,\quad r = a-t \quad (0 \lt r \lt a). $$

Остюда $$ \frac{a}{b} = \frac{1}{q_1} + \frac{r}{bq_1} \label{eq:6.1.3}\tag{6.1.3} $$

Заметим, что из $2 \leqslant a \lt b$ и $t \gt 0$, следует $q_1 = s+1 \lt \frac{b}{2}+1 \lt \frac{b}{2}+\frac{b}{2} = b$, так что знаменатель первого слагаемого правой части $\eqref{eq:6.1.3}$ меньше знаменателя исходной дроби.

Далее, ввиду $0 \lt r \lt a \lt b \leqslant bq_1$, второе слагаемое в правой части $\eqref{eq:6.1.3}$ является правильной положительной дробью, числитель которой меньше $a$. Ее можно сократить не более, чем на $r$, так что после сокращения знаменатель окажется не меньше $\frac{bq_1}{r} \gt q_1 \gt b$.

Пусть $\frac{a_1}{b_1}$ — дробь, образованная сокращением второго слагаемого правой части $\eqref{eq:6.1.3}$. Как было указано, эта дробь является правильной положительной, причем $a_1 \lt b_1$. Если $a_1 = 1$, требуемое представление получено. В противном случае, применяя вышеизложенный метод к $\frac{a_1}{b_1}$, можно выделить следующую аликвотную дробь $\frac{1}{q_2}$, так что $$ \frac{a}{b} = \frac{1}{q_1} + \frac{1}{q_2} + \frac{a_2}{b_2} $$

Повторяя этот процесс, получаем последовательность дробей $\frac{a_i}{b_i}$, числители которых образуют убывающую последовательность положительных чисел, которая не может быть бесконечной. Таким образом, на некотором шаге числитель станет равным единице и процесс закончится.

Вышеизложенный способ, называемый «скупым методом» (англ greedy method) или методом Фибоначчи, показывает, что любая правильная положительная обыкновенная дробь представима в виде египетской дроби.

Применим «скупой метод» к вышеупомянутой дроби $\frac{7}{8}$: $$ \begin{array}{lll} q_1 = \left\lceil\frac{8}{7}\right\rceil = \left\lceil 1\frac{1}{7}\right\rceil = 2; & \;\; & \frac{7}{8} - \frac{1}{2} = \frac{3}{8} \\ q_2 = \left\lceil \frac{8}{3} \right\rceil = \left\lceil 2\frac{2}{3} \right\rceil = 3; & \;\; & \frac{3}{8} - \frac{1}{3} = \frac{1}{24} \end{array} $$

Получили $\frac{7}{8} = \frac{1}{2} + \frac{1}{3} + \frac{1}{24}$ или $[2,3,24]$, что к возможному удивлению отличается от ранее упомянутого. Согласно «скупому» методу, следует разрезать 4 хлеба пополам, остальные 3 хлеба на 3 части, далее одну из полученных от последнего разрезания долей на 8 (!) частей. Снова получаем $4 + 3 \cdot 2 + 7 = 17$ разрезаний, однако древнеегипетское решение выглядит куда приятнее.

Выводы:

Представление в виде египетской дроби не всегда однозначно;
«Скупой» метод не всегда дает наилучшее решение.

Более того, «скупой» метод не всегда дает представление наименьшей длины! В Википедии приведен пример дроби $\frac{5}{121}$, для которой «скупой» метод дает ужасающее [25, 757, 763309, 873960180913, 8739601809131527612795642093418846225], оставляя за бортом более короткое и гораздо более элегантное [33, 121, 363].

Приведенный ниже Калькулятор египетской дроби использует «скупой» метод с небольшой модификацией, позволяющей, хотя возможно не всегда, но во многих случаях находить скрытые решения.

6.2. Цепные дроби

Наконец, рассмотрим еще одно представление рационального числа, называемое непрерывной и цепной дробью (англ. continued/chain fraction). В данной публикации под цепной дробью будем понимать дробь вида $$ \alpha = a_0 + \cfrac{1}{a_1+\cfrac{1}{a_2+ \cfrac{1}{ \ddots + \cfrac{1}{a_{n-1}} }}} \label{eq:6.2.1}\tag{6.2.1} $$ где $a_0$ — целое число, $a_1,\;a_2,\;\dots\;a_{n-1}$ — целые положительные числа.

Так же как и в случае египетской дроби, цепную дробь можно записать в одну строку, используя квадратные скобки, однако целая часть присутствует и отделяется от последующих элементов точкой с занятой (;). Таким образом, вышеуказанная цепная дробь компактно записывается, как $[a_0; a_1, a_2, \dots a_{n-1}]$. Числа $a_i$ будем называть элементами цепной дроби, а количество элементов $n$ — длиной дроби.

Покажем, что любую обыкновенную дробь $\frac{p}{q}$ (которую разумеется будем считать несократимой) можно представить в виде цепной дроби. Прежде всего выделим целую часть, то есть найдем наибольшее целое число, не превосходящее заданную дробь. Для обозначения целой части будем использовать нижние скобки, так как в данном случае округление до целого происходит вниз: $$ \begin{array}{l} a_0 = \left \lfloor \dfrac{p}{q} \right \rfloor \\ \dfrac{p}{q} = a_0 + \dfrac{r_0}{q}\,, \quad \text{где} \; 0 \leqslant r_0 \lt q \label{eq:6.2.2}\tag{6.2.2} \end{array} $$

Из определения целой части следует, что второе слагаемое в $\eqref{eq:6.2.2}$, называемое дробной частью числа, является правильной неотрицательной дробью. Если дробная часть равна нулю, исходная дробь является целым числом и процесс завершен. В противном случае выделяем целую часть из обратной дроби $\frac{q}{r_0}$, которая обязана быть неправильной: $$ \begin{array}{l} a_1 = \left \lfloor \dfrac{q}{r} \right \rfloor \\ \dfrac{q}{r_0} = a_1 + \dfrac{r_1}{r_0}\,, \quad \text{где} \; 0 \leqslant r_1 \lt r_0 \label{eq:6.2.3}\tag{6.2.3} \end{array} $$

Поставляя значение $\frac{r_0}{q}$ из $\eqref{eq:6.2.3}$ в $\eqref{eq:6.2.2}$, получаем: $$ \dfrac{p}{q} = a_0 + \cfrac{1}{a_1+\cfrac{r_1}{r_0}}\;, $$ так что две цифры цепной дроби уже определены. Повторяя процесс до тех пор, пока дробная часть станет равной нулю, получим остальные цифры. (На самом деле, процесс можно прервать, когда числитель равен единице, так как следующий этап наверняка даст нулевую дробную часть.)

Осталось заметить, что дробная часть обязана стать нулевой, так в противном случае, согласно $0 \leqslant r_{i+1} \lt r_i$, $i=0,1 \dots $, числители дробных частей образовывали бы бесконечно-убывающую последовательность натуральных чисел, а таких последовательностей не бывает.

В качестве иллюстрации переведем $\frac{50}{37}$ в цепную дробь: $$ \begin{array}{lll} a_0 = \left \lfloor \dfrac{50}{37} \right \rfloor = 1, & \quad & \dfrac{50}{37} - 1 = \dfrac{13}{37} \\ a_1 = \left \lfloor \dfrac{37}{13} \right \rfloor = 2, & \quad & \dfrac{37}{13} - 2 = \dfrac{11}{13} \\ a_2 = \left \lfloor \dfrac{13}{11} \right \rfloor = 1, & \quad & \dfrac{13}{11} - 1 = \dfrac{2}{11} \\ a_3 = \left \lfloor \dfrac{11}{2} \right \rfloor = 5, & \quad & \dfrac{11}{2} - 5 = \dfrac{1}{2} \\ a_4 = 2 \end{array} $$

Получили: $$ \dfrac{50}{37} = [1; 2, 1, 5, 2] = 1 + \cfrac{1}{{2+\cfrac{1}{1+\cfrac{1}{5+\cfrac{1}{2}}}}} $$

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

Назовем $i$-м остатком цепной дроби ($i=0,1,2 \dots n-1$) ее знаменатель, начинающийся с $a_i$: $$ \beta_i = a_i + \cfrac{1}{a_{i+1}+ \cfrac{1}{\ddots + \cfrac{1}{a_{n-1}} }} \label{eq:6.2.4}\tag{6.2.4} $$

Легко видеть, что $\beta_i$ в свою очередь является цепной дробью: $\beta_i = [a_i, \dots a_{n-1}]$, при этом исходная дробь является нулевым остатком: $\alpha = \beta_0$, а последний остаток совпадает с последним элементом $\beta_{n-1}$

Далее заметим, что цепную дробь и каждый ее остаток, кроме последнего, можно выразить через последующий остаток: $$ \beta_i = a_i + \frac{1}{\beta_{i+1}} \quad i=0,1 \dots (n-2) \label{eq:6.2.5}\tag{6.2.5} $$ откуда $$ \beta_{i+1} = \frac{1}{\beta_i - a_i} \quad i=0,1 \dots (n-2) $$

Алгоритм перевода в цепную дробь можно записать следующим образом: $$ \begin{array}{l} \beta_0 = \alpha \\ a_i = \left \lfloor \beta_i \right \rfloor \\ \beta_{i+1} = \dfrac{1}{\beta_i - a_i} \end{array} \label{eq:6.2.6}\tag{6.2.6} $$

Из свойств целой части и алгоритма перевода следует $$ a_i \leqslant \beta_i \lt a_i + 1 \quad i=0,1 \ldots (n-1), \label{eq:6.2.7}\tag{6.2.7} $$ причем равенство имеет место тогда и только тогда, когда $i=n-1$, то есть $\beta_i$ - последний остаток.

Отметим еще одно следствие из двойного неравенства $\eqref{eq:6.2.7}$. При $i \lt n-1$ его можно записать, как $0 \lt \beta_i - a_i \lt 1$, откуда $$ \beta_{i+1} = \frac{1}{\beta_i - a_i} \gt 1 \quad i=0,1 \ldots (n-2) $$

Если $n \gt 1$ (то есть $\alpha$ не является целым числом) то, полагая $i=n-2$, получаем $a_{n-1} = \beta_{n-1} \gt 1$, или $a_{n-1} \geqslant 2$. В этом случае $a_{n-1}$ можно заменить на $(a_{n-1}-1)+\frac{1}{1}$, получив новую цепную дробь $[a_0; a_1, \dots a_{n-1}-1, 1]$, значение которой также равно $\frac{p}{q}$. Пример: $$ \frac{3}{2} = 1+\cfrac{1}{2} = 1+\cfrac{1}{1+\cfrac{1}{1}}\;. $$ Однако, представление в виде цепной дроби становится однозначным, если потребовать, что для цепной дроби, не являющейся одно-элементной (то есть с длиной большей 1) последний элемент отличен от единицы:

6.2.1 Всякая цепная дробь соответствует рациональному числу. Наоборот, всякое рациональное число однозначно представимо в виде цепной дроби, последний элемент которой, при наличии не менее двух элементов, отличен от единицы.

Если дана цепная дробь, то путем последовательных упрощений ее можно привести к виду $\frac{p}{q}$, где $p$ и $q$ — целые числа. При этом, так как все элементы, кроме целой части, положительны, знаменатель $q$ — также положительное число.

Наоборот, существование цепной дроби для любого рационального числа следует из вышеприведенного алгоритма, в котором, как было показано, последний элемент может быть равен 1 только при $n=1$. Осталось доказать единственность такой дроби.

Пусть некое рациональное число $r$ представимо в виде двух цепных дробей: $[a_0; a_1, \dots a_{n-1}]$ и $[a_0';a_1' \dots a_{k-1}']$, где $n \leqslant k$, причем при $n \gt 1$ каждое из $a_{n-1},\;a_{k-1}'$ отлично от 1. Остатки этих дробей будем обозначать через $\beta_i$ и $\beta_i'$ соответственно.

Покажем, что $a_0 = \lfloor r \rfloor$. (Напоминаем, что $\lfloor \dots \rfloor$ означает целую часть числа.) Так как $a_0$ является целым числом по определению, достаточно показать, что $0 \leqslant r - a_0 \lt 1$. Для этого рассмотрим три случая:

а) Если $n=1$ (одно-элементная дробь), то $r=a_0$, так что $r - a_0 = 0$.

б) Если $n=2$, то $r = a_0 + \frac{1}{a_1}$. При этом, согласно определению цепной дроби, $a_1$ – положительное число. С другой стороны, $a_1$ является последним элементом дроби, который по условию отличен от единицы. Отсюда $a_1 \gt 1$, так что значение $r - a_0 = \frac{1}{a_1}$ положительно и меньше 1, что и требовалось доказать.

в) Наконец, рассмотрим случай $n \gt 2$. Тогда $r = a_0 + \frac{1}{\beta_1}$. При этом $\beta_1$ не является последним остатком, поэтому, согласно $\eqref{eq:6.2.7}$, $\beta_1 \gt a_1 \geqslant 1$, так что и в этом случае $r - a_0 = \frac{1}{\beta_1}$ положительно и меньше 1.

Аналогично доказывается, что $a_0' = \lfloor r \rfloor$, следовательно $а_0 = a_0'$.

Если $n=1$, то $r$ — целое число, так что $r = a_0 = a_0'$. Если при этом $k \gt 1$, то, согласно $\eqref{eq:6.2.7}$, $r = \beta_0' \gt a_0' = r$, что является противоречием. Отсюда $k=1$ и дроби совпадают.

Если $n \gt 1$, то в соответствии с $\eqref{eq:6.2.5}$, имеем: $\beta_1 = \beta_1' = \dfrac{1}{r - \lfloor r \rfloor}$. Применяя к $\beta_1$ и $\beta_1'$ вышеуказанные рассуждения приходим к равенству элементов $a_1$ и $a_1'$, а также к равенству значений остатков $\beta_2$ и $\beta_2'$. Повторяя рассуждения $n-1$ раз, получаем: $$ \begin{array}{l} a_i = a_i' \quad \text{для} \; i=0,1 \dots (n-2) \\ [a_{n-1}]=[a_{n-1}'; \dots a_{k-1}'] \end{array}\;, $$ откуда на основании вышеприведенных рассуждений для одно-элементной дроби заключаем, что $a_{n-1}=a_{n-1}'$ и $k=n$, так что цепные дроби полностью совпадают.

Многочисленные приложения цепных дробей основаны на их свойстве давать наилучшее приближение. При этом $i$-e приближение дроби ($i=0,1 \dots (n-2))$ получается отбрасыванием всех элементов после $a_i$: $$ \gamma_i = [a_0; a_1 \dots a_i]\quad i=1,2 \dots n. $$ Число $\gamma_i\;\;(i=0,\dots n-1)$ будем называть $i$-м заголовком цепной дроби (другой термин: отрезок дроби). Заметим, что длина $i$-го заголовка равна $i+1$, при этом $(n-1)$-й заголовок совпадает со всей дробью: $\gamma_{n-1} = \alpha$.

Вполне естественно ожидать, что точность приближения $i$-м заголовком улучшается с увеличением $i$. Прежде чем доказать, что это действительно так, приведем формулы, полученные всё тем же остроумным Эйлером (не перестаю восхищаться гениальностью этого ученого):

6.2.2 Пусть $\gamma_i = \frac{p_i}{q_i}$, где $p_i$ и $q_i$ — взаимно-простые числа ($q \gt 0$, как обычно). Тогда $p_i$ и $q_i$ удовлетворяют следующим соотношениям: $$ \begin{array}{lll} p_{-1} = 1, & p_0 = a_0, & p_{i} = a_i\,p_{i-1} + p_{i-2} \quad \text{при} \quad i \geqslant 1 \\ q_{-1} = 0, & q_0 = 1, & q_{i} = a_i\,q_{i-1} + q_{i-2} \quad \text{при} \quad i \geqslant 1 \,. \end{array} \label{eq:6.2.8}\tag{6.2.8} $$

Дроби вида $\frac{p_i}{q_i}$ часто называют подходящими дробями $i$-го порядка. Чтобы не вводить дополнительных терминов, мы будем называть $i$-м заголовком как цепную дробь, так и для соответствующую ей обыкновенную дроби в надежде, что это не внесет путаницы.

Заметим, что $\gamma_0 = [a_0] = \frac{a_0}{1}$, что подтверждает $\eqref{eq:6.2.8}$ для $p_0$ и $q_0$. Что касается странных $p_{-1}$ и $q_{-1}$, то введены они исключительно для распространения рекуррентных формул на случай $i=1$. Вычислим для проверки $p_1$ и $q_1$ непосредственно: $$ \frac{p_1}{q_1} = [a_0;a_1] = a_0+\cfrac{1}{a_1} = \frac{a_1\,a_0+1}{a_1}\,, $$ Значения числителя и знаменателя дроби в правой части в точности соответствуют рекуррентной формуле $\eqref{eq:6.2.8}$ для $i=1$. Однако не будем спешить с выводами: ведь следует доказать несократимость дроби. Пусть $p_1' = a_1\,a_0+1$ и $q_1'=a_1$ имеют общий делитель $d \gt 1$. Тогда $p_1' - a_0\,q_1' = 1$ должно делится на $d$, что невозможно. Таким образом, дробь действительно несократима, так что $p_1 = p_1'$ и $q_1 = q_1'$.

Справедливость формул для $i=0$, а также верность рекуррентных формул для $i=1$ дают базу индукции. Осталось обосновать индукционный переход, то есть доказать что из справедливости рекуррентных формул для $i=k \; (k \geqslant 1)$ следует их справедливость для $i=k+1$.

Для этого одновременно с заданной цепной дробью $\alpha = [a_0;a_1 \dots a_{n-1}]$ рассмотрим дробь $\alpha'=[a_1;a_2 \dots a_{n-1}]$, являющуюся 1-м остатком $\alpha$, заголовки которой будем обозначать со штрихом. Таким образом $$ \gamma_i' = [a_1;a_2, \dots a_{i+1}] \quad i=0,1 \dots n-2 \,. $$ (Заметим, что поскольку заголовок $\gamma_i'$ начинается не с $a_0$, a с $a_1$, он должен оканчиваться на $a_{i+1}$, чтобы иметь требуемую длину $i+1$.)

В частности $\gamma_{k}' = [a_1; a_2, \dots a_{k+1}]$ является 1-м остатком заголовка $\gamma_{k+1}=[a_0;a_1 \dots a_{k+1}]$, так что, согласно $\eqref{eq:6.2.5}$ $$ \gamma_{k+1} = a_0 + \frac{1}{\gamma_k'} \label{eq:6.2.9}\tag{6.2.9} $$

Вспомним, что несократимая дроби, соответствующая $\gamma_i$ обозначаются через $\dfrac{p_i}{q_i}$. Аналогично введем обозначение $\dfrac{p_i'}{q_i'}$ для несократимого представления $\gamma_{i}'$. Из $\eqref{eq:6.2.9}$ получаем: $$ \frac{p_{k+1}}{q_{k+1}} = a_0 + \frac{q_k'}{p_k'} = \frac{a_0 \, p_k' + q_k'}{p_k'} $$

Снова дробь в правой части является несократимой, так как в противном случае наибольший общий делитель $p_k'$ и $a_0 \, p_k' + q_k'$ был бы также делителем $q_k' = (a_0 \, p_k' + q_k') - a_0 \, p_k'$, что делает дробь $\frac{p_k'}{q_k'}$ сократимой. Поэтому $$ \begin{array}{l} p_{k+1} = a_0 \, p_k' + q_k' \\ q_{k+1} = p_k' \end{array} \label{eq:6.2.10}\tag{6.2.10} $$

Хотя полученные формулы – это не то, что требуется, они всё же приближают к цели. Дело в том, что согласно индукционному предположению, к $\gamma_{k}'$ (который является не $k+1$-м, а $k$-м заголовком) применимы формулы $\eqref{eq:6.2.8}$, так что $$ \begin{array}{l} p_{k}' = a_{k+1}\,p_{k-1}' + p_{k-2}' \\ q_{k}' = a_{k+1}\,q_{k-1}' + q_{k-2}' \end{array} $$(Снова обращаем внимание на то, что $a_{k+1}$ является последним элементом $\gamma_k'$, поэтому именно это значение появилось в формулах.)

Подставляя значения $p_{k}'$ и $q_{k}'$ в $\eqref{eq:6.2.9}$ и приводя подобные, получаем: $$ \begin{array}{l} p_{k+1} = a_{k+1}\,(a_0 \, p_{k-1}' + q_{k-1}')+ (a_0\,p_{k-2}' + q_{k-2}') \\ q_{k+1} = a_{k+1}\,p_{k-1}' + p_{k-2}'\,. \end{array} \label{eq:6.2.11}\tag{6.2.11} $$

Чтобы «избавиться от штрихов», заметим, что если формулы $\eqref{eq:6.2.10}$ прочесть справа налево, заменив $k$ на $k-1$ и на $k-2$, получим: $$ \begin{array}{ll} a_0 \, p_{k-1}' + q_{k-1}' = p_k & \quad p_{k-1}' = q_k \\ a_0 \, p_{k-2}' + q_{k-2}' = p_{k-1} & \quad p_{k-2}' = q_{k-1} \end{array} $$ отчего равенства $\eqref{eq:6.2.11}$ приобретают новый облик: $$ \begin{align} p_{k+1} & = a_{k+1}\,p_k + p_{k-1} \\ q_{k+1} & = a_{k+1}\,q_k + q_{k-1}\,. \end{align} $$

Нужна ли лупа, чтобы увидеть, что получили не что иное, как рекуррентные формулы $\eqref{eq:6.2.8}$ для $i=k+1$?! Утверждение 6.2.2 доказано.

Приведенное доказательство основано на книге «А.Я.Хинчин. Цепные дроби. 3-е изд. ГИФМЛ М. 1960, гл I § 2» Современные книги обычно приводят более короткий индукционный переход путем замены заголовка $[a_0;a_1, \dots a_{i-1}, a_i]$ более коротким $[a_0;a_1, \dots a_{i-2}, a_{i-1}+\frac{1}{a_i}]$, оставляя без внимания тот факт, что последний элемент при этом становится дробным. Кроме того, несократимость дробей при таком подходе требует отдельного пояснения. Парадоксальнее всего то, что именно А.Я.Хинчин, а не другие авторы, допускает дробные элементы в цепной дроби!

Формулы $\eqref{eq:6.2.8}$ упрощают нахождение приближений, избавляя от необходимости вычислять из заново. Продемонстрируем метод на примере уже знакомой дроби $\dfrac{50}{37} = [1; 2, 1, 5, 2]$: $$ \begin{array}{r|c|l|l} \text{i} & a_i & p_i & q_i \\ \hline -1 & \; & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 2 & 2 \times 1+1=3 & 2 \times 1+0=2 \\ 2 & 1 & 1 \times 3+1=4 & 1 \times 2+1 = 3 \\ 3 & 5 & 5 \times 4+3=23 & 5 \times 3 + 2 = 17 \\ 4 & 2 & 2 \times 23+4=50 & 2 \times 17 + 3 = 37 \end{array} $$

Таким образом, приближения дроби: $1,\; \frac{3}{2},\; \frac{4}{3},\; \frac{23}{17}$, тогда как последняя линия нужна лишь для проверки правильности вычислений. При этом погрешность приближения дробью $\frac{23}{17}$ составляет $\left|\frac{50}{37}-\frac{23}{17}\right| \approx 0,0016$ (здесь $| \dots |$ обозначают абсолютную величину), тогда как приближения соседними знаменателями 16 и 18 дают: $\left|\frac{50}{37}-\frac{22}{16}\right| \approx 0.024$ и $\left|\frac{50}{37}-\frac{24}{18}\right| \approx 0.018$, что гораздо хуже приближения знаменателем 17.

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

Кроме практической ценности, соотношения $\eqref{eq:6.2.8}$ позволяют установить ряд важных свойств приближения цепными дробями. Прежде всего докажем, что

6.2.3 Знаменатели заголовков цепной дроби образуют монотонно-неубывающую последовательность, которая становится монотонно возрастающей при отбрасывании $q_0$.

Согласно определению, $ q_i \gt 0$ при $i \geqslant 0$, поэтому $q{-1} = 0$ меньше всех остальных элементов.

Если $i \geqslant 1$, то $$ q_{i} = a_i\,q_{i-1} + q_{i-2} \geqslant a_i\,q_{i-1} \geqslant q_{i-1}\,. $$ При этом $q_{i-2} \gt 0$, если $i \geqslant 2$, так что неравенство в этом случае является строгим.

Из $q_0=1$ и $q_1=a_1$ следует, что $q_1=q_0$ при $a_1 = 1$ (что допускается, если длина дроби больше 2). Это показывает, что требование об отбрасывании $q_0$ является существенным, что упускают из виду некоторые авторы.

Перейдем к менее очевидным фактам, которые однако довольно просто выводятся из $\eqref{eq:6.2.8}$.

Умножая рекуррентные формулы соответственно на $q_{i-1}$ и $p_{i-1}$, затем вычитая первую формулу из второй, получаем $$ q_i\;p_{i-1} - p_i\,q_{i-1} = -(q_{i-1}\,p_{i-2} - p_{i-1}\,q_{i-2})\,, \quad i \geqslant 1 $$

Введя обозначение $u_i = q_i\,p_{i-1} - p_i\,q_{i-1}$, последнее равенство можно записать, как $u_i = -u_{i-1}$. Другими словами с увеличением $i$ на единицу $u_i$ меняет знак на противоположный. Осталось заметить, что $u_0 = q_0\,p_{-1} - p_0\,q_{-1} = 1$, так что $u_i = (-1)^i$. Вспоминая, что такое $u_i$, получаем: $$ q_i\;p_{i-1} - p_i\;q_{i-1} = (-1)^i\,, \quad i \geqslant 1 \label{eq:6.2.12}\tag{6.2.12} $$

Теперь умножим рекуррентные формулы $\eqref{eq:6.2.8}$ соответственно на $q_{i-2}$ и $p_{i-2}$ и снова вычтем первую формулу из второй. Учитывая $\eqref{eq:6.2.12}$, получаем: $$ \begin{align} q_i\,p_{i-2} - p_i\,q_{i-2} & = a_i(q_{i-1}\,p_{i-2} - p_{i-1}\,q_{i-2}) \\ & = (-1)^{i-1}\,a_i \,, \quad i \geqslant 1 \label{eq:6.2.13}\tag{6.2.13} \end{align} $$

Равенства $\eqref{eq:6.2.12}$ и $\eqref{eq:6.2.13}$ становятся более наглядными, если разделить первое на $-q_i\,q_{i-1}$, а второе на $-q_i\,q_{i-2}$ (чтобы $q_{i-2}$ был отличен от нуля, необходимо $i \geqslant 2$): $$ \begin{array}{ll} \dfrac{p_i}{q_i} - \dfrac{p_{i-1}}{q_{i-1}} = \dfrac{(-1)^{i-1}}{q_i\,q_{i-1}}\,, & \quad i \geqslant 1 \\ \dfrac{p_i}{q_i} - \dfrac{p_{i-2}}{q_{i-2}} = \dfrac{(-1)^i\;a_i}{q_i\,q_{i-2}} \,, & \quad i \geqslant 2 \,. \label{eq:6.2.14}\tag{6.2.14} \end{array} $$

Обратимся к первому равенству из $\eqref{eq:6.2.14}$. Поскольку все $q_i$ положительные числа, правая часть положительна при нечетном $i$ и отрицательна при четном $i$. Таким образом получаем:

6.2.4 Четный член последовательности $\gamma_i$ меньше предыдущего, а нечетный член этой последовательности больше предыдущего. Таким образом последовательность $\gamma_i$ является колеблющейся.

Рассмотрим теперь второе равенство из $\eqref{eq:6.2.14}$, где члены в левой части имеют одинаковую четность. Учитывая, что $a_i \gt 0$ при $i \gt 0$, приходим к следующему выводу что правая часть положительна при четном $i$ и отрицательна при нечетном $i$. Таким образом:

6.2.5 Последовательность $\gamma_{2i}$ является монотонно возрастающей, а последовательность $\gamma_{2i+1}$ является монотонно убывающей.

Утверждение 6.2.5 подсказывает, что заголовки с четными и нечетными находятся по разные стороны от значения исходной дроби. Докажем, что это действительно так::

6.2.6 Значение дроби больше значения каждого своего четного заголовка и меньше значения каждого нечетного заголовка: $$ \gamma_{2i} \lt \alpha \lt \gamma_{2j+1},\quad 0 \leqslant i \leqslant \left\lfloor \frac{n-1}{2} \right\rfloor,\; 0 \leqslant j \leqslant \left\lfloor \frac{n-1}{2} \right\rfloor $$

Так как к одно-элементной дроби утверждение не применимо, а в случае $n=2$ неравенство $\alpha = [a_0; a_1] \gt a_0 = \gamma_0$ очевидно, будем считать, что $n \geqslant 3$.

Вспомним, что $\alpha = \gamma_{n-1}$. Применение равенств $\eqref{eq:6.2.14}$ дает: $$ \begin{array}{l} \alpha - \gamma_{n-2} = \frac{(-1)^{n-2}}{q_{n-1}\,q_{n-2}} \\ \alpha - \gamma_{n-3} = \frac{(-1)^{n-1}a_{n-1}}{q_{n-1}\,q_{n-3}} \end{array} $$

Заметим, что правые части равенств имеют противоположные знаки, что дает $$ \begin{array}{l} \gamma_{n-2} \lt \alpha \lt \gamma_{n-3} \qquad \text{при четном} \; n \\ \gamma_{n-3} \lt \alpha \lt \gamma_{n-2} \qquad \text{при нечетном} \; n \end{array} $$

Полученные неравенства можно обобщить, как $$ \gamma_u \lt \alpha \lt \gamma_v\;, $$ где $u$ и $v$ – соответственно наибольший четный и нечетный индекс, меньший $(n-1)$. Согласно утверждению 6.2.5, для произвольного четного и нечетного индексов $2i$ и $2j+1$, меньших $(n-1)$, получаем $$ \gamma_{2i} \leqslant \gamma_u \lt \alpha \lt \gamma_v \leqslant \gamma_{2j+1}\,, $$ что завершает доказательство утверждения 6.2.6.

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

6.2.7 Если $i \geqslant 0$, то $$ |\alpha - \gamma_i| \lt \frac{1}{q_i^2} $$

Ввиду утверждения 6.2.3, с увеличением $i$ знаменатель дроби в правой части увеличивается начиная с $i=2$, что означает улучшение точности приближения.

Для доказательства заметим, что числа $i$ и $i-1$ имеют разную четность, поэтому, согласно предыдущему утверждению, значение $\alpha$ находится строго между $\gamma_i$ и $\gamma_{i-1}$. Отсюда, согласно первому равенству из $\eqref{eq:6.2.14}$, а также ввиду $q_i \geqslant q_{i-1}$ (утверждение 6.2.3), получаем: $$ |\alpha - \gamma_{i-1}| \lt |\gamma_i - \gamma_{i-1}| = \frac{1}{q_i\,q_{i-1}} \leqslant \frac{1}{q_{i-1}^2}. $$

Для завершения доказательства осталось заменить индекс $(i-1)$ индексом $i$.

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

Также не забудьте посмотреть «Вопросы и задачи».

7. Online-калькуляторы

По правде говоря, к браузерным приложениям автор этой публикации относится как к чему-то несерьезному. В данном случае деваться было некуда, так что пришлось испытать себя в новом поприще. Надеюсь, читатели отнесутся к этой «пробе пера» снисходительно.

Internet Explorer (моя версия IE 11.48.17134.0) настолько архаичен, что ради него пришлось пожертвовать рядом удобств, предоставляемых современными браузерами. Несмотря на достигнутую совместимость, предпочтительнее использовать другие браузеры, например Microsoft Edge. «Родной средой» калькуляторов является Firefox.

При использовании калькуляторов в других страницах следует дать ссылку на этот сайт.

7.1. Калькулятор позиционной дроби

Числитель и знаменатель всегда вводятся в десятичной системе счисления. После ввода данных нажмите знак равенства(=) для вычисления. Значение позиционной дроби указывается в заданной системе счисления, длина периода в десятичной системе. Если дробь не умещается в окне, выберите это окно и сдвиньте указатель вправо для просмотра последующих цифр.

При основании системы счисления превышающем 10 используются следующие буквы для обозначения «больших цифр»:

A	B	C	D	E	F	G	H	I	J
10	11	12	13	14	15	16	17	18	19

Основание системы счисления:

Длина периода:

7.2. Калькулятор египетской дроби

После ввода числителя и знаменателя нажмите знак равенства(=) для вычисления.

Значение египетской дроби записывается в виде последовательности знаменателей, например [2,3,8] соответствует $\frac{1}{2}+\frac{1}{3}+\frac{1}{8}$. Перечисляются все представления, обеспечивающие минимум слагаемых. Результаты с промежуточными (т.е. кроме последнего) знаменателями больше 1,000,000 игнорируются. Если результат не умещается в окне, выберите это окно и сдвиньте указатель вправо для просмотра последующих цифр.

Количество дробей: Длина дроби: Лучшая дробь:

7.3. Калькулятор цепной дроби

Знаменатель должен быть целым положительным числом. Если знаменатель не указан, его значение принимается равным 1.

Если знаменатель больше 1, числитель должен быть целым числом. Если знаменатель равен 1 (или не указан), числитель может также быть десятичной дробью или числовым выражением, например 2*Math.PI, однако точность при этом не гарантируется.

После ввода числителя и знаменателя нажмите знак равенства(=) для вычисления.

В режиме «Без LaTeX» приближения записываются в одну строку (напр. $1/2$ вместо $\frac{1}{2}$). После загрузки страницы следует подождать несколько секунд, пока LaTeX обновится. Обновление LaTeX не работает в некоторых версиях Android. В iOS и Safari (независимо от операционной системы) обновление LaTeX работает неправильно, поэтому в этих конфигурациях режим «Без LaTeX» включен по умолчанию.

Длина дроби: Без LaTeX
Приближения:

Вопросы и задачи.

Часть 1

1.1Может период десятичной дроби оканчиваться нулем?

1.2а) Приведите пример числа меньшего 0,000001, представимого бесконечной периодической десятичной дробью с предпериодом. б) Может «чисто-периодическая» десятичная дробь быть меньше 0,000001?

1.3Какая из нижеперечисленных десятичных дробей представляется правильной обыкновенной дробью со знаменателем, не кратным 2 и 5 (ответ дать без нахождения соответствующей обыкновенной дроби):
а) $0,(99)$; б) $0,54(5)$; в) $0,32(5432)$; г) $0,32(9)$?

1.4В периодической десятичной дроби 0,242424… первую цифру после запятой заменили на 4. Во сколько раз полученное число больше исходного?

1.5a) Всегда ли произведение бесконечных «чисто-периодических» дробей представляется бесконечной «чисто-периодической» дробью? b) Может произведение дробей с предпериодом представляться «чисто-периодической» дробью?

1.6Числа $A$ и $B$ задаются правильными «чисто-периодическими» дробями, периоды которых начинаются соответственно $p$ и $q$ нулями. Сколькими нулями может начинаться период десятичного представления произведения $AB$?

1.7Найти все пары натуральных чисел, удовлетворяющих равенству $\sqrt{xx,xxx\dots} = y,yyy\dots$. (B обеих частях равенства стоят бесконечные десятичные дроби, записанные с помощью цифр $x$ и $y$)

1.8Какие из утверждений верны:
а) Число представимое в виде конечной десятичной дроби представимо в виде конечной дроби в системе счисления с любым основанием;
б) Число представимое в виде периодической десятичной дроби представимо в виде периодической дроби в системе счисления с любым основанием;
в) Если десятичное представление дроби содержит предпериод, то $n$-ичное представление этой дроби содержит предпериод для любого целого $n \gt 1$?

1.9Число $\dfrac{1711}{2019}$ обратили в десятичную дробь, затем стерли первую цифру после запятой и обратили получившуюся десятичную дробь в обыкновенную. Какое число получилось?

Часть 2

2.1Указать множество чисел $n$, для которых $\lambda(n)=1$.

2.2Выведите формулу для $\lambda(2^{n_1}\,3^{n_2}\,5^{n_3}\,7^{n_4}11^{n_5})$, где $n_i$ — целые неотрицательные числа.

2.3Сформулируйте утверждения 4.1.1 и 4.4.2 для системы счисления с произвольным основанием $m \geqslant 2$.

2.4Рассмотрим $m$-ичное представление дроби $\frac{1}{m+1}$.
  а) Определите длину периода дроби.
  б) Найдите период дроби.
  в) Чему равна длина периода $m$-ичного представления дроби $\frac{1}{km+k}$, где $k$ — делитель $m$?

2.5Чему равно $m$-ичное представление дроби $\frac{1}{m^k-1}$, где $k$ — некоторое целое положительное число?

2.6Пусть $p$—простое число, отличное от 2 и 5. Какие из следующих утверждений (в десятичной системе счисления) являются заведомо верными:
  а) Длина периода несократимой дроби $\frac{m}{p}$ четна;
  б) Период несократимой дроби $\frac{m}{p}$ кратен 9;
  в) Число $\underbrace{11...1}_{p\;\text{единиц}}$ кратно $p$?

2.7Десятичное представление правильной дроби $\frac{m}{p}\quad$ является бесконечной периодической дробью, период которой состоит только из нулей и единиц, причем его длина меньше 10. Может $p$ быть простым числом?

2.8Среди правильных дробей с простым знаменателем, десятичное представление которых содержит каждую из цифр 1,3,4,5,6 найти дроби с наименьшей длиной периода.

2.9Целое число записанное в $b^n$-ичной системе счисления можно перевести в $b$-ичную систему путем замены каждой $b^n$-ичной цифры соответствующим $b$-ичным представлением, при необходимости дополненным нулями до $n$-значного. В качестве примера положим $b=2,\;\;n=3$ и переведем число $61_{8}$ в двоичную систему счисления. Получаем: $6=110_{\,2}$,  $1=001_2$, (в последнем случае число $1_2$ было дополнено нулями до трехзначного), так что $61_8=110001_{\,2}$.
  a) Примени́м аналогичный метод к $b^n$-ичным дробям?
  b) Пусть длина периода $b^n$-ичной дроби равна $k$. Всегда ли длина периода соответствующей $b$-ичной дроби равна $nk$?

2.10Докажите, что следующие правильные дроби с положительным знаменателем представимы в виде суммы двух аликвотных дробей с различными знаменателями:
  а) аликвотная дробь;
  б) дробь с числителем, равным 2;
  в) дробь с числителем, равным 4 и знаменателем, дающим при делении на 4 остаток, отличный от 1.
  г) Найдите правильную дробь с числителем 4 и положительным знаменателем, не представимую в виде суммы двух аликвотных дробей.

2.11Пусть $p_i$, $q_i$ — соответственно числитель и знаменатель $i$-го заголовка цепной дроби $[a_0;a_1, \dots a_{n-1}]$. Докажите, что
$\dfrac{p_i}{p_{i-1}} = [a_i; a_{i-1}, \dots a_0]$ при $0 \leqslant i \leqslant n-1$;
$\dfrac{q_i}{q_{i-1}} = [a_i; a_{i-1}, \dots a_1]$ при $1 \leqslant i \leqslant n-1$

2.12Положительные рациональные числа $a$ и $b$ записаны в виде десятичных дробей, у каждой из которых наименьший период состоит из 30 цифр. У десятичной записи числа $a-b$ длина наименьшего периода равна 15. При каком наименьшем натуральном $k$ длина наименьшего периода десятичной записи числа $a+kb$ может также оказаться равной 15?

Описание
Часть 1