Нечётное жадное разложение — метод построения египетских дробей , в которых все знаменатели нечётные.

Если рациональное число ${\displaystyle x/y}$ является суммой нечётных аликвотных дробей :

${\displaystyle {\frac {x}{y}}=\sum {\frac {1}{2a_{i}+1}}}$ ,

то число ${\displaystyle y}$ должно быть нечётным. Обратно, известно, что в случае нечётности числа ${\displaystyle y}$ любая дробь вида ${\displaystyle x/y}$ имеет разложение с нечётными знаменателями, в котором все знаменатели дробей различны. Например, такое разложение можно найти, заменив ${\displaystyle x/y}$ на ${\displaystyle Ax/Ay}$ , где ${\displaystyle A}$ — число вида ${\displaystyle 35\times 3^{i}}$ для достаточно большого ${\displaystyle i}$ , а затем представив ${\displaystyle Ax}$ в виде суммы делителей ${\displaystyle Ay}$ .

Однако существует более простой жадный алгоритм , который успешно находит египетские дроби с нечётными знаменателями для всех чисел ${\displaystyle x/y}$ (с нечётным ${\displaystyle y}$ ), на которых он проверен: пусть ${\displaystyle u}$ — наименьшее нечётное число, не меньшее ${\displaystyle y/x}$ , включается дробь ${\displaystyle 1/u}$ в разложение и процесс продолжается для остаточной дроби ${\displaystyle x/y-1/u}$ . Этот метод и называется нечётным жадным алгоритмом, а получаемое разложение называется нечётным жадным разложением.

Вопрос о том, завершится ли процесс разложения за конечное число шагов для любого числа ${\displaystyle x/y}$ с нечётным ${\displaystyle y}$ по состоянию на 2006 год оставался открытым .

Применение алгоритма к дроби с чётным знаменателем даёт бесконечное разложение. Например, последовательность Сильвестра можно рассматривать как результат работы нечётного жадного алгоритма для дроби ${\displaystyle 1/2}$ .

Пример

Пусть x / y = 4/23.

23/4 = 5 ¾, следующее большее нечётное число равно 7. Таким образом, на первом шаге получаем разложение:

4/23 = 1/7 + 5/161.

161/5 = 32 1/5, следующее большее нечётное число равно 33. Таким образом, на следующем шаге получаем разложение:

4/23 = 1/7 + 1/33 + 4/5313.

5313/4 = 1328 1/4, следующее большее нечётное число равно 1329. Таким образом, на третьем шаге получаем разложение:

4/23 = 1/7 + 1/33 + 1/1329 + 1/2353659.

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

Дроби с длинными разложениями

Нечётный жадный алгоритм может образовывать разложения, которые короче обычного жадного разложения и с меньшими знаменателями . Например,

${\displaystyle {\frac {8}{77}}={\frac {1}{10}}+{\frac {1}{257}}+{\frac {1}{197890}}={\frac {1}{11}}+{\frac {1}{77}},}$

где разложение слева получено жадным алгоритмом, а разложение справа получено нечётным жадным алгоритмом. Однако, как правило, результат разложения нечётным жадным алгоритмом длиннее и имеет большие знаменатели. Например , разложение нечётным жадным алгоритмом числа 3/179 даёт 19 членов, наибольший из которых примерно равен 1,415×10 ⁴³⁹⁴⁹¹ . Что интересно, числители дробей разложения при этом образуют последовательность целых чисел:

3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 1.

Аналогичные случаи происходят и с другими числами, такими как 5/5809 (пример найден независимо Брауном ( K. S. Brown ) и Бейли ( David Bailey )), и в этом случае разложение имеет 31 член. Хотя знаменатели этого разложения трудно вычислить ввиду их огромного размера, последовательность числителей можно найти относительно эффективно, если использовать модульную арифметику . В 1999 году описаны некоторые дополнительные примеры этого типа и приведены методы поиска дробей, дающих произвольно длинные разложения.

Примечания

Литература

• R. Breusch. // American Mathematical Monthly . — 1954. — Т. 61 . — С. 200—201 .
• Richard K. Guy. Unsolved Problems in Number Theory. — 1981. — С. 88. — ISBN 0-387-90593-6 .
• Richard K. Guy. // American Mathematical Monthly . — 1998. — Т. 105 , вып. 10 . — С. 951—954 . — doi : . — JSTOR .
• Victor Klee, Stan Wagon. Unsolved Problems in Elementary Geometry and Number Theory. — 1991.
• Richard Nowakowski. // American Mathematical Monthly . — 1999. — Т. 106 , вып. 10 . — С. 959—962 . — doi : . — JSTOR .
• B. M. Stewart. Sums of distinct divisors // American Journal of Mathematics . — 1954. — Т. 76 , вып. 4 . — С. 779—785 . — doi : . — JSTOR .
• Stan Wagon. . — W. H. Freeman, 1991. — С. —277. — ISBN 0-7167-2202-X .
• , K. S. Brown