Странное жадное расширение

Нерешенная задача по математике :

Каждое ли рациональное число с нечетным знаменателем имеет нечетное жадное разложение?

(еще нерешенные задачи по математике)

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

Описание

Египетская дробь представляет данное рациональное число как сумму различных единичных дробей . Если рациональное число $x/y$ представляет собой сумму единичных дробей с нечетными знаменателями,

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

затем $y$ должно быть странным. И наоборот, каждая дробь $x/y$ с $y$ нечетное можно представить как сумму различных долей нечетных единиц. Один из методов нахождения такого представления заменяет $x/y$ к $Ax/Ay$ где $A=35\cdot 3^{i}$ для достаточно большого $i$, а затем расширяется $Ax$ как сумма различных делителей $Ay$.

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

Стайн, Селфридж , Грэм и другие поставили открытую проблему : завершается ли нечетный жадный алгоритм конечным разложением для каждого $x/y$ с $y$ странный.

Пример

Позволять $x/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.

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

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

Нечетный жадный алгоритм может создавать разложения, которые короче обычного жадного разложения, с меньшими знаменателями. Например, $${\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, 2, 3, 4, 1.

Аналогичное явление происходит и с другими числами, такими как 5/5809 (пример, найденный независимо К.С. Брауном и Дэвидом Бейли), которое имеет 27-членное разложение. Хотя знаменатели этого разложения трудно вычислить из-за их огромного размера, последовательность числителя можно относительно эффективно найти с помощью модульной арифметики . Новаковски (1999) описывает несколько дополнительных примеров этого типа, найденных Бродхерстом, и отмечает, что К. С. Браун описал методы поиска дробей с произвольно длинным разложением.

В четных знаменателях

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

Ссылки

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

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

• MathPages — Разложение нечетно-жадных единичных дробей , К.С. Браун