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

Простой метод нахождения египетских дробей.

В математике жадный алгоритм для египетских дробей — это жадный алгоритм , впервые описанный Фибоначчи , для преобразования рациональных чисел в египетские дроби . Египетская дробь — это представление несократимой дроби в виде суммы отдельных единичных дробей , таких как ⁠5/6⁠ = ⁠1/2⁠ + ⁠1/3⁠ . Как следует из названия, эти представления использовались еще в Древнем Египте , но первый опубликованный систематический метод построения таких расширений был описан в 1202 году в Liber Abaci Леонардо Пизанского (Фибоначчи). ^[1] Он называется жадным алгоритмом, потому что на каждом шаге алгоритм жадно выбирает наибольшую возможную единичную дробь , которая может быть использована в любом представлении оставшейся дроби.

Фибоначчи на самом деле перечисляет несколько различных методов построения представлений египетских дробей. ^[2] Он включает жадный метод как последнее средство для ситуаций, когда несколько более простых методов не срабатывают; см. Египетские дроби для более подробного списка этих методов. Как подробно описывает Зальцер (1948), жадный метод и его расширения для аппроксимации иррациональных чисел были повторно открыты несколько раз современными математиками, самым ранним и наиболее известным из которых был Дж. Дж. Сильвестр  (1880) ^[3] Близкий к нему метод расширения, который производит более близкие аппроксимации на каждом шаге, позволяя некоторым единичным дробям в сумме быть отрицательными, восходит к Ламберту (1770).

Расширение, полученное этим методом для числа, называется жадным египетским расширением , расширением Сильвестра или расширением Фибоначчи–Сильвестра . Однако термин расширение Фибоначчи обычно относится не к этому методу, а к представлению целых чисел в виде сумм чисел Фибоначчи . ${\displaystyle x}$ ${\displaystyle x}$

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

Алгоритм Фибоначчи расширяет дробь, которую нужно представить, многократно выполняя замену (упрощая второй член в этой замене по мере необходимости). Например: в этом расширении знаменатель 3 первой единичной дроби является результатом округления ⁠ ${\displaystyle x/y}$ $${\displaystyle {\frac {x}{y}}={\frac {1}{\left\lceil {\frac {y}{x}}\right\rceil }}+{\frac {(-y){\bmod {x}}}{y\left\lceil {\frac {y}{x}}\right\rceil }}}$$ $${\displaystyle {\frac {7}{15}}={\frac {1}{3}}+{\frac {2}{15}}={\frac {1}{3}}+{\frac {1}{8}}+{\frac {1}{120}}.}$$15/7⁠ до следующего большего целого числа, а оставшаяся дробь ⁠2/15⁠ является результатом упрощения ⁠−15 мод 7/15 × 3⁠  =  ⁠6/45⁠ . Знаменатель второй единичной дроби, 8, является результатом округления ⁠15/2⁠ до следующего большего целого числа, а оставшаяся дробь ⁠1/120⁠ это то, что осталось от ⁠7/15⁠ после вычитания обоих ⁠1/3⁠ и ⁠1/8⁠ .

Поскольку каждый шаг расширения уменьшает числитель оставшейся дроби, подлежащей расширению, этот метод всегда заканчивается конечным расширением; однако, по сравнению с древнеегипетскими расширениями или более современными методами, этот метод может производить расширения, которые довольно длинные, с большими знаменателями. Например, этот метод расширяет, в то время как другие методы приводят к гораздо лучшему расширению . Вагон (1991) предлагает еще более плохо себя ведущий пример, ⁠ $${\displaystyle {\frac {5}{121}}={\frac {1}{25}}+{\frac {1}{757}}+{\frac {1}{763\,309}}+{\frac {1}{873\,960\,180\,913}}+{\frac {1}{1\,527\,612\,795\,642\,093\,418\,846\,225}},}$$ $${\displaystyle {\frac {5}{121}}={\frac {1}{33}}+{\frac {1}{121}}+{\frac {1}{363}}.}$$31/311⁠ . Жадный метод приводит к расширению с десятью членами, последний из которых имеет более 500 цифр в знаменателе; однако, ⁠31/311⁠ имеет гораздо более короткое нежадное представление, ⁠1/12⁠ + ⁠1/63⁠ + ⁠1/2799⁠ + ⁠1/8708⁠ .

Последовательность Сильвестра и ее ближайшее приближение

Последовательность Сильвестра 2, 3, 7, 43, 1807, ... ( OEIS : A000058 ) можно рассматривать как сгенерированную бесконечным жадным расширением этого типа для числа 1, где на каждом шаге мы выбираем знаменатель ⌊ ⁠у/х⁠ ⌋ + 1 вместо ⌈ ⁠у/х⁠ ⌉ . Усечение этой последовательности до k членов и формирование соответствующей египетской дроби, например (для k  = 4), приводит к максимально возможной недооценке 1 любой k -членной египетской дробью. ^[4] То есть, например, любая египетская дробь для числа в открытом интервале ( ⁠ $${\displaystyle {\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{7}}+{\frac {1}{43}}={\frac {1805}{1806}}}$$1805/1806⁠ , 1) требует по крайней мере пяти членов. Кертисс (1922) описывает применение этих результатов наилучшего приближения для нижней границы числа делителей совершенного числа , в то время как Стонг (1983) описывает приложения в теории групп .

Расширения максимальной длины и условия конгруэнтности

Любая дробь ⁠х/у⁠ требует максимум x членов в своем жадном расширении. Мэйс (1987) и Фрейтаг и Филлипс (1999) исследуют условия, при которых жадный метод производит расширение ⁠х/у⁠ с ровно x членами; их можно описать в терминах условий конгруэнтности по y .

• Каждая дробь ⁠1/у⁠ требует одного члена в своем жадном расширении; простейшая такая дробь — ⁠1/1⁠ .
• Каждая дробь ⁠2/у⁠ требует двух членов в своем жадном разложении тогда и только тогда, когда y ≡ 1 (mod 2) ; простейшая такая дробь — ⁠2/3⁠ .
• Дробь ⁠3/у⁠ требует трех членов в своем жадном расширении тогда и только тогда, когда y ≡ 1 (mod 6) , тогда − y mod x = 2 и ⁠у ( у + 2)/3⁠ нечетно, поэтому дробь, оставшаяся после одного шага жадного расширения, в простейших терминах. Простейшая дробь ⁠ $${\displaystyle {\frac {(-y){\bmod {x}}}{y\left\lceil {\frac {y}{x}}\right\rceil }}={\frac {2}{\,{\frac {y(y+2)}{3}}\,}}}$$3/у⁠ с трехчленным расширением ⁠3/7⁠ .
• Дробь ⁠4/у⁠ требует четырех членов в своем жадном расширении тогда и только тогда, когда y ≡ 1 или 17 (mod 24) , тогда числитель − y mod x оставшейся дроби равен 3, а знаменатель равен 1 (mod 6) . Простейшая дробь ⁠4/у⁠ с четырехчленным расширением ⁠4/17⁠ . Гипотеза Эрдёша–Штрауса утверждает, что все дроби ⁠4/у⁠ имеют разложение с тремя или менее членами, но когда y ≡ 1 или 17 (mod 24), такие разложения должны быть найдены методами, отличными от жадного алгоритма, при этом случай 17 (mod 24) покрывается отношением конгруэнтности 2 (mod 3) .

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

${\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 }$(последовательность A048860 в OEIS ).

Аппроксимация корней полинома

Stratemeyer (1930) и Salzer (1947) описывают метод нахождения точного приближения для корней многочлена, основанный на жадном методе. Их алгоритм вычисляет жадное расширение корня; на каждом шаге этого расширения он сохраняет вспомогательный многочлен, имеющий в качестве корня оставшуюся дробь для расширения. Рассмотрим в качестве примера применение этого метода для нахождения жадного расширения золотого сечения , одного из двух решений полиномиального уравнения P ₀ ( x ) = x ² − x − 1 = 0 . Алгоритм Stratemeyer и Salzer выполняет следующую последовательность шагов:

1. Поскольку P ₀ ( x ) < 0 для x  = 1 и P ₀ ( x ) > 0 для всех x ≥ 2 , должен быть корень P ₀ ( x ) между 1 и 2. То есть первый член жадного расширения золотого сечения равен ⁠1/1⁠ . Если x ₁ — оставшаяся дробь после первого шага жадного расширения, то она удовлетворяет уравнению P ₀ ( x ₁ + 1) = 0 , которое можно разложить как P ₁ ( x ₁ ) = x²
   ₁+ х ₁ − 1 = 0 .
2. Так как P ₁ ( x ) < 0 для x  =  ⁠1/2⁠ , и P ₁ ( x ) > 0 для всех x > 1 , корень P ₁ лежит между ⁠1/2⁠ и 1, а первый член в его жадном разложении (второй член в жадном разложении для золотого сечения) равен ⁠1/2⁠ . Если x ₂ — оставшаяся дробь после этого шага жадного расширения, то она удовлетворяет уравнению P ₁ ( x ₂ + ⁠1/2⁠ ) ​​= 0 , что можно разложить как P ₂ ( x ₂ ) = 4 x²
   ₂+ 8 х ₂ − 1 = 0 .
3. Так как P ₂ ( x ) < 0 для x  =  ⁠1/9⁠ , и P ₂ ( x ) > 0 для всех x > ⁠1/8⁠ , следующий член в жадном расширении — ⁠1/9⁠ . Если x ₃ — оставшаяся дробь после этого шага жадного расширения, то она удовлетворяет уравнению P ₂ ( x ₃ + ⁠1/9⁠ ) ​​= 0 , которое снова можно разложить как полиномиальное уравнение с целыми коэффициентами, P ₃ ( x ₃ ) = 324 x²
   ₃+ 720 х ₃ − 5 = 0 .

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

${\displaystyle \varphi ={\frac {1}{1}}+{\frac {1}{2}}+{\frac {1}{9}}+{\frac {1}{145}}+{\frac {1}{37986}}+\cdots }$(последовательность A117116 в OEIS ).

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

Длина, минимальный знаменатель и максимальный знаменатель жадного расширения для всех дробей с малыми числителями и знаменателями могут быть найдены в On-Line Encyclopedia of Integer Sequences как последовательности OEIS : A050205 , OEIS : A050206 и OEIS : A050210 , соответственно. Кроме того, жадное расширение любого иррационального числа приводит к бесконечно возрастающей последовательности целых чисел, и OEIS содержит расширения нескольких хорошо известных констант. Некоторые дополнительные записи в OEIS, хотя и не помечены как созданные жадным алгоритмом, по-видимому, относятся к тому же типу.

Связанные расширения

В общем случае, если требуется египетское дробное разложение, в котором знаменатели ограничены каким-либо образом, можно определить жадный алгоритм, в котором на каждом шаге выбирается разложение, где выбирается, среди всех возможных значений, удовлетворяющих ограничениям, как можно меньшее, такое что и такое что отличается от всех ранее выбранных знаменателей. Примерами методов, определенных таким образом, являются разложение Энгеля , в котором каждый последующий знаменатель должен быть кратным предыдущему, и нечетное жадное разложение , в котором все знаменатели ограничены нечетными числами. $${\displaystyle {\frac {x}{y}}={\frac {1}{d}}+{\frac {xd-y}{yd}},}$$ ${\displaystyle d}$ ${\displaystyle xd>y}$ ${\displaystyle d}$

Однако может быть сложно определить, всегда ли алгоритм такого типа может успешно найти конечное расширение. В частности, неизвестно, заканчивается ли нечетное жадное расширение конечным расширением для всех дробей, для которых нечетно, хотя можно найти конечные нечетные расширения для этих дробей нежадными методами. ${\displaystyle x/y}$ ${\displaystyle y}$

Примечания

1. Сиглер 2002.
2. Сиглер 2002, глава II.7
3. См., например, Cahen (1891) и Spiess (1907).
4. Кёртисс 1922; Саундарараджан 2005 г.

Ссылки

• Каэн, Э. (1891), «Примечание к развитию числовых величин, которое представляет собой какую-то аналогию с целыми числами и дробями», Nouvelles Annales des Mathématiques , сер. 3, 10 : 508–514..
• Кёртисс, Д. Р. (1922), «О диофантовой задаче Келлога», American Mathematical Monthly , 29 (10): 380–387, doi :10.2307/2299023, JSTOR  2299023.
• Фрайтаг, Х.Т.; Филлипс, Г.М. (1999), «Алгоритм Сильвестра и числа Фибоначчи», Приложения чисел Фибоначчи, т. 8 (Рочестер, Нью-Йорк, 1998) , Дордрехт: Kluwer Acad. Publ., стр. 155–163, MR  1737669.
• Ламберт, Дж. Х. (1770), Beyträge zum Gebrauche der Mathematik und deren Anwendung , Берлин: Zweyter Theil, стр. 99–104..
• Мейс, Майкл (1987), «Наихудший случай расширения Фибоначчи–Сильвестра», Журнал комбинаторной математики и комбинаторных вычислений , 1 : 141–148, MR  0888838.
• Salzer, HE (1947), «Приближение чисел как сумм обратных величин», American Mathematical Monthly , 54 (3): 135–142, doi :10.2307/2305906, JSTOR  2305906, MR  0020339.
• Salzer, HE (1948), «Дополнительные замечания о приближении чисел как сумм обратных величин», American Mathematical Monthly , 55 (6): 350–356, doi :10.2307/2304960, JSTOR  2304960, MR  0025512.
• Сиглер, Лоуренс Э. (пер.) (2002), Liber Abaci Фибоначчи , Springer-Verlag, ISBN 0-387-95419-8.
• Soundararajan, K. (2005), Аппроксимация 1 снизу с использованием n египетских дробей , arXiv : math.CA/0502247.
• Шписс, О. (1907), «Über eine Klasse unendlicher Reihen», Archiv der Mathematik und Physik , третья серия, 12 : 124–134..
• Стонг, Р.Э. (1983), «Псевдосвободные действия и жадный алгоритм», Mathematische Annalen , 265 (4): 501–512, doi : 10.1007/BF01455950, MR  0721884, S2CID  120347233.
• Стратемайер, Г. (1930), «Stammbruchentwickelungen für die Quadratwurzel aus einerrationalen Zahl», Mathematische Zeitschrift , 31 : 767–768, doi : 10.1007/BF01246446, S2CID  120956180.
• Сильвестр, Дж. Дж. (1880), «Об одном пункте теории вульгарных дробей», American Journal of Mathematics , 3 (4): 332–335, doi :10.2307/2369261, JSTOR  2369261.
• Вагон, С. (1991), Mathematica в действии , WH Freeman, стр. 271–277.