Странное жадное расширение - Odd greedy expansion

Нерешенная проблема в математике: Каждый рациональное число с нечетным знаменателем есть странное жадное расширение? (больше нерешенных задач по математике)

В теория чисел, то странное жадное расширение проблема касается метода формирования Египетские фракции в котором все знаменатели нечетные.

Если рациональное число Икс/y это сумма странный единицы измерения,

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

тогда y должно быть странно. И наоборот, известно, что всякий раз, когда y нечетное, каждая дробь Икс/y имеет представление этого типа, в котором все единичные дроби отличаются друг от друга. Например, такое представление можно найти, заменив дробь Икс/y от Топор/Ау где А число вида 35 × 3^я для достаточно большого я, а затем расширяя Топор как сумму делителей Ау.^[1]

Однако есть более простой жадный алгоритм который успешно нашел египетские дроби, в которых все знаменатели нечетны для всех случаев Икс/y (с нечетным y), на котором он был протестирован: пусть ты быть наименьшим нечетным числом, которое больше или равно y/Икс, включают дробь 1 /ты в расширении, и продолжайте таким же образом с оставшейся дробью Икс/y − 1/ты. Этот метод называется странный жадный алгоритм и создаваемые им расширения называются странные жадные расширения.

Штейн, Селфридж, Грэм, и другие поставили вопрос о том, завершается ли нечетный жадный алгоритм конечным расширением для каждого Икс/y с участием y странный.^[2] По состоянию на 2016 год^{[Обновить]}, этот вопрос остается открытым.

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

пример

Позволять Икс/y = 4/23.

23/4 = 5 3/4; следующее большее нечетное число - 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] Например,

${ displaystyle { 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 (пример, независимо найденный К. С. Брауном и Дэвидом Бейли), у которого есть 31 член. Хотя знаменатели этого расширения трудно вычислить из-за их огромного размера, последовательность числителя может быть найдена относительно эффективно, используя модульная арифметика. Новаковский (1999) описывает несколько дополнительных примеров этого типа, найденных Бродхерстом, и отмечает, что К. С. Браун описал методы нахождения дробей с произвольно длинными расширениями.

Заметки

использованная литература

• Бреуш, Р. (1954), «Частный случай египетских дробей, решение расширенной задачи 4512», Американский математический ежемесячный журнал, 61: 200–201, Дои:10.2307/2307234
• Гай, Ричард К. (1981), Нерешенные проблемы теории чисел, Springer-Verlag, стр. 88, ISBN  0-387-90593-6
• Гай, Ричард К. (1998), «Ничего нового в теории чисел?», Американский математический ежемесячный журнал, 105 (10): 951–954, Дои:10.2307/2589289, JSTOR  2589289
• Клее, Виктор; Вагон, Стан (1991), Нерешенные проблемы элементарной геометрии и теории чисел, Математические выставки Дольчиани, Математическая ассоциация Америки
• Новаковски, Ричард (1999), «Нерешенные проблемы, 1969–1999», Американский математический ежемесячный журнал, 106 (10): 959–962, Дои:10.2307/2589753, JSTOR  2589753
• Стюарт, Б.М. (1954), «Суммы различных делителей», Американский журнал математики, 76 (4): 779–785, Дои:10.2307/2372651, JSTOR  2372651, Г-Н  0064800
• Вагон, Стан (1991), Mathematica в действии, W.H. Фримен, стр.275–277, ISBN  0-7167-2202-X

внешние ссылки

• MathPages - Нечетно-жадное разложение на дробные единицы, К. С. Браун