Нечётное жадное разложение

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

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

\text{[math]}

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

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

,

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

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

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

Применение алгоритма к дроби с чётным знаменателем даёт бесконечное разложение. Например, последовательность Сильвестра можно рассматривать как результат работы нечётного жадного алгоритма для дроби $\text{[math]}$ $\text{[math]}$ $1/2$ $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.

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

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

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

\text{[math]}

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

где разложение слева получено жадным алгоритмом, а разложение справа получено нечётным жадным алгоритмом. Однако, как правило, результат разложения нечётным жадным алгоритмом длиннее и имеет большие знаменатели. Например^[4], разложение нечётным жадным алгоритмом числа 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 году^[5] описаны некоторые дополнительные примеры этого типа и приведены методы поиска дробей, дающих произвольно длинные разложения.

ЛитератураПравить

R. Breusch. A special case of Egyptian fractions, solution to advanced problem 4512 // 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. Nothing's new in number theory? // American Mathematical Monthly. — 1998. — Т. 105, вып. 10. — С. 951—954. — doi:10.2307/2589289. — JSTOR 2589289.
Victor Klee, Stan Wagon. Unsolved Problems in Elementary Geometry and Number Theory. — 1991.
Richard Nowakowski. Unsolved problems, 1969—1999 // American Mathematical Monthly. — 1999. — Т. 106, вып. 10. — С. 959—962. — doi:10.2307/2589753. — JSTOR 2589753.
B. M. Stewart. Sums of distinct divisors // American Journal of Mathematics. — 1954. — Т. 76, вып. 4. — С. 779—785. — doi:10.2307/2372651. — JSTOR 2372651.
Stan Wagon. Mathematica in Action. — W. H. Freeman, 1991. — С. 275—277. — ISBN 0-7167-2202-X.
MathPages — Odd-Greedy Unit Fraction Expansions, K. S. Brown

[1] Breusch, 1954; Stewart, 1954

[_3fe4f43312719917-2] Guy, 1981.

[_5b8de65030fadaa7-3] Wagon, 1991.

[_c79ee07cfe65ad01-4] Guy, 1998.

[_d24bad7f31ea38aa-5] Nowakowski, 1999.

[1]

[2]

[3]

[4]

[5]