Жадный алгоритм для египетских дробей

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

Разложение, полученное жадным алгоритмом для числа $x$, называется жадным египетским разложением, разложением Сильвестра или разложением Фибоначчи — Сильвестра числа $x$.

История

Среди нескольких различных методов построения египетских дробей, приведённых Фибоначчи в «Книге абака», был жадный алгоритм, который предлагался к применению, лишь если прочие методы не сработали. Впоследствии жадный алгоритм и его расширения для приближения иррациональных чисел был переоткрыт несколько раз, наиболее ранний и известный случай — алгоритм СильвестраШаблон:SfnШаблон:Sfn. Метод, дающий ближайшее приближение на каждом шаге, для чего разрешаются отрицательные дроби, принадлежит ЛамбертуШаблон:Sfn.

Алгоритм и примеры

Алгоритм Фибоначчи осуществляет разложение $x/y$ путём последовательного проведения замены:

$\frac{x}{y}=\frac{1}{\lceil y/x\rceil }+\frac{(-y)modx}{y\lceil y/x\rceil }$

(упрощая второй член, если необходимо). Например:

$\frac{7}{15}=\frac{1}{3}+\frac{2}{15}=\frac{1}{3}+\frac{1}{8}+\frac{1}{120}$.

В этом разложении знаменатель $3$ первой аликвотной дроби является результатом округления $15/7$ до следующего (большего) целого числа, а остаток $2/15$ — результат сокращения $(-15(\mathrm{mod}7))/(15\cdot 3)=6/45$. Делитель второй дроби — $8$, — является результатом округления $15/2$ до следующего (большего) целого числа, а остаток $1/120$ — это то, что осталось от $7/15$ после вычитания $1/3$ и $1/8$.

Поскольку каждый шаг разложения уменьшает числитель остаточной дроби, этот метод завершится за конечное число шагов. Однако, по сравнению с древними египетскими методами разложения или более современными методами, этот метод может дать разложение с довольно большими знаменателями. Например, жадное разложение числа $5/121$:

$\frac{1}{25}+\frac{1}{757}+\frac{1}{763309}+\frac{1}{873960180913}+\frac{1}{1527612795642093418846225}$,

в то время как другие методы дают куда более простое разложение:

$\frac{5}{121}=\frac{1}{33}+\frac{1}{121}+\frac{1}{363}$,

а для $31/311$ жадный алгоритм даёт разложение на десять дробей, последняя из которых имеет в знаменателе 500 знаков, тогда как существует представлениеШаблон:Sfn:

$\frac{1}{12}+\frac{1}{63}+\frac{1}{2799}+\frac{1}{8708}$.

Последовательность Сильвестра

Последовательность Сильвестра $2,3,7,43,1807,\dots$ можно представить как образованную бесконечным разложением единицы посредством жадного алгоритма, где на каждом шаге выбирается знаменатель $\lfloor y/x\rfloor +1$ вместо $\lceil y/x\rceil$. Если оборвать эту последовательность $k$ членами и образовать соответствующую египетскую дробь, например, для $k=4$:

$\frac{1}{2}+\frac{1}{3}+\frac{1}{7}+\frac{1}{43}=\frac{1805}{1806}$,

то получается ближайшее приближение к $1$ снизу среди египетских дробей с $k$ членамиШаблон:SfnШаблон:Sfn. Например, для любой египетской дроби для числа в открытом интервале $(1805/1806,1)$ требуется по меньшей мере пять членов. Описано применение таких ближайших разложений для нижней оценки числа делителей совершенного числаШаблон:Sfn, а также в теории группШаблон:Sfn.

Разложения максимальной длины и условия сравнения по модулю

Любая дробь $x/y$ даёт максимум $x$ членов в жадном алгоритме. Исследованы условия, при которых для разложения $x/y$ необходимо в точности $x$ дробейШаблон:SfnШаблон:Sfn, эти условия можно описать в терминах сравнений $y$ по модулю:

• любая дробь $1/y$ приводит к одному члену в разложении, самая простая такая дробь — $1/1$;
• любая дробь вида $2/y$ для нечётных $y>1$ требует двух членов в разложении, самая простая такая дробь — $2/3$;
• в разложении дроби $3/y$ необходимы три члена в том и только в том случае, когда $y\equiv 1(\mathrm{mod}6)$, в этом случае — $y=2(\mathrm{mod}x)$ и $y(y+2)/3$ нечётно, так что остаток разложения после первого шага:

  $\frac{(-y)modx}{y\lceil y/x\rceil }=\frac{2}{y(y+2)/3}$

  несократим, самая простая дробь вида $3/y$, дающая разложение с тремя членами — $3/7$;

• разложение дроби $4/y$ даёт четыре члена тогда и только тогда, когда $y\equiv 1(\mathrm{mod}24)$ или $y\equiv 17(\mathrm{mod}24)$. В этих случаях числитель — $ymodx$ остаточной дроби равен $3$ и знаменатель сравним с $1(\mathrm{mod}6)$. Самая простая дробь вида $4/y$ с четырьмя членами разложения — $4/17$, гипотеза Эрдёша — Штрауса утверждает, что все дроби вида $4/y$ имеют разложение с тремя или меньше членами, но при $y\equiv 1(\mathrm{mod}2)4$ или $y\equiv 17(\mathrm{mod}2)4$ такие разложения следует искать методами, отличными от жадного алгоритма.

В общем случае последовательность дробей $x/y$ с минимальным знаменателем $y$, имеющих разложение жадным алгоритмом с $x$ членами:

$1,\frac{2}{3},\frac{3}{7},\frac{4}{17},\frac{5}{31},\frac{6}{109},\frac{7}{253},\frac{8}{97},\frac{9}{271},\dots$.

Приближённое вычисление корней многочленов

Существует метод приближённого вычисления корней многочлена, основанный на жадном алгоритмеШаблон:SfnШаблон:Sfn, определяющем жадное разложение корня. На каждом шаге образуется дополнительный многочлен, который имеет остаток разложения в качестве корня. Например, для вычисления жадного разложения золотого сечения как одного из двух решений уравнения $P_0(x)=x^2-x-1=0$ алгоритм осуществляет следующие шаги.

1. Поскольку $P_0(x)<0$ для $x=1$ и $P_0(x)>0$ для всех $x⩾2$, корень $P_0(x)$ должен находиться между $1$ и $2$. Таким образом, первый член разложения — $1/1$. Если $x_1$ — остаток после первого шага жадного разложения, должно выполняться уравнение $P_0(x_1+1)=0$, которое можно преобразовать в $P_1(x_1)=x_1^2+x_1-1=0$.
2. Поскольку $P_1(x)<0$ для $x=1/2$ и $P_1(x)>0$ для всех $x>1$, корень $P_1$ лежит между $1/2$ и $1$, первый член в разложении $x_1$ (второй член в разложении золотого сечения) равен $1/2$. Если $x_2$ — остаток после этого шага жадного разложения, он удовлетворяет уравнению $P_1(x_2+1/2)=0$, которое можно преобразовать в $P_2(x_2)=4x_2^2+8x_2-1=0$.
3. Поскольку $P_2(x)<0$ для $x=1/9$ и $P_2(x)>0$ для всех $x>1/8$, следующим членом разложения будет $1/9$. Если $x_3$ — остаток после этого шага жадного разложения, он удовлетворяет уравнению $P_2(x_3+1/9)=0$, которое можно преобразовать в уравнение с целыми коэффициентами $P_3(x_3)=324x_3^2+720x_3-5=0$.

Продолжая этот процесс приближения, получается разложение золотого сечения в египетскую дробь:

$\phi =\frac{1}{1}+\frac{1}{2}+\frac{1}{9}+\frac{1}{145}+\frac{1}{37986}+\cdots$.

Другие целочисленные последовательности

Длина, минимальный знаменатель и максимальный знаменатель жадного разложения для дробей с малыми числителями и знаменателями включены в Энциклопедии целочисленных последовательностей. Кроме того, жадное разложение любого иррационального числа приводит к бесконечной возрастающей последовательности целых, и OEIS содержит разложения некоторых хорошо известных констант.

Связанные разложения

Возможно определить жадный алгоритм с некоторыми ограничениями на знаменатель:

$\frac{x}{y}=\frac{1}{d}+\frac{xd-y}{yd}$,

где $d$ выбирается среди всех значений, которые удовлетворяют наложенным ограничениям и имеют как можно меньшее значение, при котором $xd>y$ и такое, что $d$ отличается от всех предыдущих знаменателей. Например, разложение Энгеля можно рассматривать как алгоритм этого типа, в котором каждый допустимый знаменатель должен быть получен умножением предыдущего на некоторое целое число. Однако зачастую нетривиально установить, приводит ли такой алгоритм всегда к конечному разложению. В частности нечётное жадное разложение дроби $x/y$ образуется жадным алгоритмом с ограничением на нечётность знаменателей. Известно, что при нечётном $y$ существует разложение в египетскую дробь, в которой все знаменатели нечётны, но приведёт ли нечётный жадный алгоритм всегда к конечному разложению — неизвестно.

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья