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

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

История


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

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


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

xy=1y/x+(y)modxyy/x
  (упрощая второй член, если необходимо). Например:

715=13+215=13+18+1120.
  В этом разложении знаменатель 3 первой аликвотной дроби является результатом округления 15/7 до следующего (большего) целого числа, а остаток 2/15 — результат сокращения (15(mod7))/(153)=6/45. Делитель второй дроби — 8, — является результатом округления 15/2 до следующего (большего) целого числа, а остаток 1/120 — это то, что осталось от 7/15 после вычитания 1/3 и 1/8.
 Поскольку каждый шаг разложения уменьшает числитель остаточной дроби, этот метод завершится за конечное число шагов. Однако, по сравнению с древними египетскими методами разложения или более современными методами, этот метод может дать разложение с довольно большими знаменателями. Например, жадное разложение числа 5/121:

125+1757+1763309+1873960180913+11527612795642093418846225,
  в то время как другие методы дают куда более простое разложение:

5121=133+1121+1363,
  а для 31/311 жадный алгоритм даёт разложение на десять дробей, последняя из которых имеет в знаменателе 500 знаков, тогда как существует представление:

112+163+12799+18708.

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


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

12+13+17+143=18051806,
  то получается ближайшее приближение к 1 снизу среди египетских дробей с k членами. Например, для любой египетской дроби для числа в открытом интервале (1805/1806,1) требуется по меньшей мере пять членов. Описано применение таких ближайших разложений для нижней оценки числа делителей совершенного числа, а также в теории групп.

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


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

  • любая дробь 1/y приводит к одному члену в разложении, самая простая такая дробь — 1/1;
  • любая дробь вида 2/y для нечётных y>1 требует двух членов в разложении, самая простая такая дробь — 2/3;
  • в разложении дроби 3/y необходимы три члена в том и только в том случае, когда y1(mod6), в этом случае — y=2(modx) и y(y+2)/3 нечётно, так что остаток разложения после первого шага:
    (y)modxyy/x=2y(y+2)/3
  • разложение дроби 4/y даёт четыре члена тогда и только тогда, когда y1(mod24) или y17(mod24). В этих случаях числитель — ymodx остаточной дроби равен 3 и знаменатель сравним с 1(mod6). Самая простая дробь вида 4/y с четырьмя членами разложения — 4/17, гипотеза Эрдёша — Штрауса утверждает, что все дроби вида 4/y имеют разложение с тремя или меньше членами, но при y1(mod2)4 или y17(mod2)4 такие разложения следует искать методами, отличными от жадного алгоритма.

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

1,23,37,417,531,6109,7253,897,9271,.

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


 Существует метод приближённого вычисления корней многочлена, основанный на жадном алгоритме, определяющем жадное разложение корня. На каждом шаге образуется дополнительный многочлен, который имеет остаток разложения в качестве корня. Например, для вычисления жадного разложения золотого сечения как одного из двух решений уравнения P0(x)=x2x1=0 алгоритм осуществляет следующие шаги.

  1. Поскольку P0(x)<0 для x=1 и P0(x)>0 для всех x2, корень P0(x) должен находиться между 1 и 2. Таким образом, первый член разложения — 1/1. Если x1 — остаток после первого шага жадного разложения, должно выполняться уравнение P0(x1+1)=0, которое можно преобразовать в P1(x1)=x12+x11=0.
  2. Поскольку P1(x)<0 для x=1/2 и P1(x)>0 для всех x>1, корень P1 лежит между 1/2 и 1, первый член в разложении x1 (второй член в разложении золотого сечения) равен 1/2. Если x2 — остаток после этого шага жадного разложения, он удовлетворяет уравнению P1(x2+1/2)=0, которое можно преобразовать в P2(x2)=4x22+8x21=0.
  3. Поскольку P2(x)<0 для x=1/9 и P2(x)>0 для всех x>1/8, следующим членом разложения будет 1/9. Если x3 — остаток после этого шага жадного разложения, он удовлетворяет уравнению P2(x3+1/9)=0, которое можно преобразовать в уравнение с целыми коэффициентами P3(x3)=324x32+720x35=0.

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

φ=11+12+19+1145+137986+.

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


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

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


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

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