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

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

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

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

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

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

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

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

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

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

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

а для ${\displaystyle 31/311}$ жадный алгоритм даёт разложение на десять дробей, последняя из которых имеет в знаменателе 500 знаков, тогда как существует представление[5]:

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

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

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

то получается ближайшее приближение к ${\displaystyle 1}$ снизу среди египетских дробей с ${\displaystyle k}$ членами[6][7]. Например, для любой египетской дроби для числа в открытом интервале ${\displaystyle (1805/1806,1)}$ требуется по меньшей мере пять членов. Описано применение таких ближайших разложений для нижней оценки числа делителей совершенного числа[6], а также в теории групп[8].

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

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

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

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

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

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

${\displaystyle 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 }$.

Существует метод приближённого вычисления корней многочлена, основанный на жадном алгоритме[12][13], определяющем жадное разложение корня. На каждом шаге образуется дополнительный многочлен, который имеет остаток разложения в качестве корня. Например, для вычисления жадного разложения золотого сечения как одного из двух решений уравнения ${\displaystyle P_{0}(x)=x^{2}-x-1=0}$ алгоритм осуществляет следующие шаги.

1. Поскольку ${\displaystyle P_{0}(x)<0}$ для ${\displaystyle x=1}$ и ${\displaystyle P_{0}(x)>0}$ для всех ${\displaystyle x\geqslant 2}$, корень ${\displaystyle P_{0}(x)}$ должен находиться между ${\displaystyle 1}$ и ${\displaystyle 2}$. Таким образом, первый член разложения — ${\displaystyle 1/1}$. Если ${\displaystyle x_{1}}$ — остаток после первого шага жадного разложения, должно выполняться уравнение ${\displaystyle P_{0}(x_{1}+1)=0}$, которое можно преобразовать в ${\displaystyle P_{1}(x_{1})=x_{1}^{2}+x_{1}-1=0}$.
2. Поскольку ${\displaystyle P_{1}(x)<0}$ для ${\displaystyle x=1/2}$ и ${\displaystyle P_{1}(x)>0}$ для всех ${\displaystyle x>1}$, корень ${\displaystyle P_{1}}$ лежит между ${\displaystyle 1/2}$ и ${\displaystyle 1}$, первый член в разложении ${\displaystyle x_{1}}$ (второй член в разложении золотого сечения) равен ${\displaystyle 1/2}$. Если ${\displaystyle x_{2}}$ — остаток после этого шага жадного разложения, он удовлетворяет уравнению ${\displaystyle P_{1}(x_{2}+1/2)=0}$, которое можно преобразовать в ${\displaystyle P_{2}(x_{2})=4x_{2}^{2}+8x_{2}-1=0}$.
3. Поскольку ${\displaystyle P_{2}(x)<0}$ для ${\displaystyle x=1/9}$ и ${\displaystyle P_{2}(x)>0}$ для всех ${\displaystyle x>1/8}$, следующим членом разложения будет ${\displaystyle 1/9}$. Если ${\displaystyle x_{3}}$ — остаток после этого шага жадного разложения, он удовлетворяет уравнению ${\displaystyle P_{2}(x_{3}+1/9)=0}$, которое можно преобразовать в уравнение с целыми коэффициентами ${\displaystyle P_{3}(x_{3})=324x_{3}^{2}+720x_{3}-5=0}$.

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

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

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

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

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

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

• E. Cahen. Note sur un développement des quantités numériques, qui presente quelque analogie avec celui en fractions continues // Nouvelles Annales des Mathématiques. — 1891. — Т. 10. — С. 508–514.
• D. R. Curtiss. On Kellogg's diophantine problem // American Mathematical Monthly. — 1922. — Т. 29, вып. 10. — С. 380–387. — doi:10.2307/2299023. — .
• H. T. Freitag, G. M. Phillips. Applications of Fibonacci numbers, Vol. 8 (Rochester, NY, 1998). — Dordrecht: Kluwer Acad. Publ., 1999. — С. 155–163.
• J. H. Lambert. Beyträge zum Gebrauche der Mathematik und deren Anwendung. — Berlin: Zweyter Theil, 1770. — С. 99–104.
• Michael Mays. A worst case of the Fibonacci–Sylvester expansion // Journal of Combinatorial Mathematics and Combinatorial Computing. — 1987. — Т. 1. — С. 141–148.
• H. E. Salzer. The approximation of numbers as sums of reciprocals // American Mathematical Monthly. — 1947. — Т. 54, вып. 3. — С. 135–142. — doi:10.2307/2305906. — .
• H. E. Salzer. Further remarks on the approximation of numbers as sums of reciprocals // American Mathematical Monthly. — 1948. — Т. 55, вып. 6. — С. 350–356. — doi:10.2307/2304960. — .
• Laurence E. Sigler (trans.). Fibonacci's Liber Abaci. — Springer-Verlag, 2002. — ISBN 0-387-95419-8.
• K. Soundararajan. Approximating 1 from below using n Egyptian fractions. — 2005. — arXiv:math.CA/0502247.
• O. Spiess. Über eine Klasse unendlicher Reihen // Archiv der Mathematik und Physik, Ser. 3. — 1907. — Т. 12. — С. 124–134.
• R. E. Stong. Pseudofree actions and the greedy algorithm // Mathematische Annalen. — 1983. — Т. 265, вып. 4. — С. 501–512. — doi:10.1007/BF01455950.
• G. Stratemeyer. Stammbruchentwickelungen für die Quadratwurzel aus einer rationalen Zahl // Mathematische Zeitschrift. — 1930. — Т. 31. — С. 767–768. — doi:10.1007/BF01246446.
• J. J. Sylvester. On a point in the theory of vulgar fractions // American Journal of Mathematics. — 1880. — Т. 3, вып. 4. — С. 332–335. — doi:10.2307/2369261. — .
• S. Wagon. Mathematica in Action. — W. H. Freeman, 1991. — С. 271–277.