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

18.12.2020

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

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

x y = ∑ 1 2 a i + 1 {displaystyle {frac {x}{y}}=sum {frac {1}{2a_{i}+1}}} ,

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

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

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

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

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

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

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

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

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

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 году описаны некоторые дополнительные примеры этого типа и приведены методы поиска дробей, дающих произвольно длинные разложения.


Имя:*
E-Mail:
Комментарий: