Русская Википедия:Нечётное жадное разложение

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

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

<math>\frac{x}{y} = \sum\frac{1}{2a_i+1}</math>,

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

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

Вопрос о том, завершится ли процесс разложения за конечное число шагов для любого числа <math>x/y</math> с нечётным <math>y</math>Шаблон:Sfn по состоянию Шаблон:На оставался открытым.

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

Пример

Пусть 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.

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

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

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

<math>\frac{8}{77}=\frac{1}{10}+\frac{1}{257}+\frac{1}{197890}=\frac{1}{11}+\frac{1}{77},</math>

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

Примечания

Шаблон:Примечания

Литература

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Harvnb; Шаблон:Harvnb
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Нечётное_жадное_разложение&oldid=10461381