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

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

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

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

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

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

Поскольку каждый шаг разложения уменьшает числитель оставшейся дроби, подлежащей разложению, этот метод всегда заканчивается конечным разложением; однако по сравнению с древнеегипетскими расширениями или более современными методами этот метод может давать довольно длинные расширения с большими знаменателями. Например, этот метод расширяет $${\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}},$$в то время как другие методы приводят к гораздо лучшему расширению $${\frac {5}{121}}={\frac {1}{33}}+{\frac {1}{121}}+{\frac {1}{363}}.$$Вагон (1991) предлагает еще более плохой пример: ⁠ 31/311 ​ ​ ⁠ . Жадный метод приводит к разложению с десятью членами, последнее из которых имеет более 500 цифр в знаменателе; однако, ⁠ 31/311 ⁠ короткое имеет гораздо более нежадное представление, ⁠ 1 / 12 ⁠ + ⁠ 1 / 63 ⁠ + ⁠ 1 / 2799 ⁠ + ⁠ 1 / 8708 ⁠ .

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

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

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

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

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

В более общем смысле последовательность дробей ⁠ x / y ⁠, которые имеют жадное разложение по x и имеют наименьший возможный знаменатель 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$ (последовательность A048860 в OEIS ).

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

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

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 .

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

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

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

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

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

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

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

Ссылки

• Каэн, Э. (1891), «Заметка о развитии числовых величин, которая представляет некоторую аналогию с развитием цепных дробей», Nouvelles Annales des Mathématiques , Ser. 3, 10 : 508–514 .
• Кёртисс, Д. Р. (1922), «О диофантовой проблеме Келлога», American Mathematical Monthly , 29 (10): 380–387, doi : 10.2307/2299023 , JSTOR   2299023 .
• Фрайтаг, HT ; Филлипс, GM (1999), «Алгоритм Сильвестра и числа Фибоначчи», Применение чисел Фибоначчи, Vol. 8 (Рочестер, Нью-Йорк, 1998) , Дордрехт: Kluwer Acad. Опубл., стр. 155–163, MR   1737669 .
• Ламберт, Дж. Х. (1770), Вклад в использование математики и ее применение , Берлин: Zweyter Theil, стр. 99–104 .
• Мэйс, Майкл (1987), «Наихудший случай расширения Фибоначчи – Сильвестра», Журнал комбинаторной математики и комбинаторных вычислений , 1 : 141–148, MR   0888838 .
• Зальцер, HE (1947), «Приближение чисел как суммы обратных величин», American Mathematical Monthly , 54 (3): 135–142, doi : 10.2307/2305906 , JSTOR   2305906 , MR   0020339 .
• Зальцер, 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 .
• Саундарараджан, К. (2005), Приближение 1 снизу с использованием n египетских дробей , arXiv : math.CA/0502247 .
• Шписс, О. (1907), «Об одном классе бесконечных рядов», Архив математики и физики , третья серия, 12 : 124–134 .
• Стонг, Р.Э. (1983), «Псевдосвободные действия и жадный алгоритм», Mathematische Annalen , 265 (4): 501–512, doi : 10.1007/BF01455950 , MR   0721884 , S2CID   120347233 .
• Стратемейер, Г. (1930), «Разложение стволовой дроби для квадратного корня из рационального числа», Mathematical Journal , 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 .