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

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

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

История

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

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

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

${\frac {x}{y}}={\frac {1}{\lceil y/x\rceil }}+{\frac {(-y){\bmod {x}}}{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{\pmod {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 знаков, тогда как существует представление:

${\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$ членами. Например, для любой египетской дроби для числа в открытом интервале $(1805/1806,1)$ требуется по меньшей мере пять членов. Описано применение таких ближайших разложений для нижней оценки числа делителей совершенного числа, а также в теории групп.

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

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

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

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

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

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

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

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

1. Поскольку $P_{0}(x)<0$ для $x=1$ и $P_{0}(x)>0$ для всех $x\geqslant 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$.

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

$\varphi ={\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$ существует разложение в египетскую дробь, в которой все знаменатели нечётны, но приведёт ли нечётный жадный алгоритм всегда к конечному разложению — неизвестно.

Литература

• 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.