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

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

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

ИсторияПравить

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

Алгоритм и примерыПравить

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

$\frac{x}{y}=\frac{1}{\lceil <!--\; \lceil \; -->y/x\rceil <!--\; \rceil \; -->}+\frac{(-<!--\; -\; -->y)modx}{y\lceil <!--\; \lceil \; -->y/x\rceil <!--\; \rceil \; -->}$${\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}$${\frac {7}{15}}={\frac {1}{3}}+{\frac {2}{15}}={\frac {1}{3}}+{\frac {1}{8}}+{\frac {1}{120}}$ .

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

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

$\frac{1}{25}+\frac{1}{757}+\frac{1}{763309}+\frac{1}{873960180913}+\frac{1}{1527612795642093418846225}$${\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}$${\frac {5}{121}}={\frac {1}{33}}+{\frac {1}{121}}+{\frac {1}{363}}$ ,

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

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

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

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

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

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

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

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

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

  $\frac{(-<!--\; -\; -->y)modx}{y\lceil <!--\; \lceil \; -->y/x\rceil <!--\; \rceil \; -->}=\frac{2}{y(y+2)/3}$${\frac {(-y){\bmod x}}{y\lceil y/x\rceil }}={\frac 2{y(y+2)/3}}$ 

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

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

В общем случае последовательность дробей $x/y$$x/y$  с минимальным знаменателем $y$$y$ , имеющих разложение жадным алгоритмом с $x$$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 <!--\; \dots \; -->$$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$$P_{0}(x)=x^{2}-x-1=0$  алгоритм осуществляет следующие шаги.

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

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

$\mathrm{\phi <!--\; \phi \; -->}=\frac{1}{1}+\frac{1}{2}+\frac{1}{9}+\frac{1}{145}+\frac{1}{37986}+\cdots <!--\; \cdots \; -->$$\varphi ={\frac 11}+{\frac 12}+{\frac 19}+{\frac 1{145}}+{\frac 1{37986}}+\cdots$ .

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

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

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

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

$\frac{x}{y}=\frac{1}{d}+\frac{xd-<!--\; -\; -->y}{yd}$${\frac {x}{y}}={\frac {1}{d}}+{\frac {xd-y}{yd}}$ ,

где $d$$d$  выбирается среди всех значений, которые удовлетворяют наложенным ограничениям и имеют как можно меньшее значение, при котором $xd>y$$xd>y$  и такое, что $d$$d$  отличается от всех предыдущих знаменателей. Например, разложение Энгеля можно рассматривать как алгоритм этого типа, в котором каждый допустимый знаменатель должен быть получен умножением предыдущего на некоторое целое число. Однако зачастую нетривиально установить, приводит ли такой алгоритм всегда к конечному разложению. В частности нечётное жадное разложение дроби $x/y$$x/y$  образуется жадным алгоритмом с ограничением на нечётность знаменателей. Известно, что при нечётном $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. — JSTOR 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. — JSTOR 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. — JSTOR 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. — JSTOR 2369261.
• S. Wagon. Mathematica in Action. — W. H. Freeman, 1991. — С. 271–277.