Целочисленная сложность

В теории чисел сложность целого числа — это наименьшее количество единиц , которое можно использовать для его представления с помощью единиц и любого количества сложений , умножений и круглых скобок. Оно всегда находится в пределах постоянного множителя логарифма данного целого числа .

Пример

Например, число 11 можно представить с помощью восьми единиц:

11 = (1 + 1 + 1) × (1 + 1 + 1) + 1 + 1.

Однако он не имеет представления с использованием семи или менее единиц. Следовательно, его сложность равна 8.

Сложности чисел 1, 2, 3,... равны.

1, 2, 3, 4, 5, 5, 6, 6, 6, 7, 8, 7, 8, 8, 8, 8, 9, 8, ... (последовательность A005245 в OEIS )

Наименьшими числами сложности 1, 2, 3,... являются

1, 2, 3, 4, 5, 7, 10, 11, 17, 22, 23, 41, 47, ... (последовательность A005520 в OEIS )

Верхняя и нижняя границы

Вопрос о таком способе выражения целых чисел первоначально рассматривался Малером и Попкеном (1953). Они просили наибольшее число с заданной сложностью k ; ^[1] позже Селфридж показал, что это число

${\displaystyle 2^{x}3^{(k-2x)/3}{\text{ where }}x=-k{\bmod {3}}.}$

Например, когда k = 10 , x = 2 и наибольшее целое число, которое можно выразить с помощью десяти единиц, равно 2 ²  3 ² = 36 . Его выражение

(1 + 1) × (1 + 1) × (1 + 1 + 1) × (1 + 1 + 1).

Таким образом, сложность целого числа n не меньше 3 log ₃  n . Сложность n не превышает 3 log ₂  n (приблизительно 4,755 log ₃  n ): выражение такой длины для n можно найти, применив метод Хорнера к двоичному представлению n . ^[2] Почти все целые числа имеют представление, длина которого ограничена логарифмом с меньшим постоянным множителем, 3,529 log ₃ n . ^[3] 

Алгоритмы и контрпримеры

Сложности всех целых чисел до некоторого порога N можно вычислить за общее время O ( N  ^1,222911236 ) . ^[4]

Алгоритмы вычисления целочисленной сложности использовались для опровержения нескольких гипотез о сложности. В частности, не обязательно, что оптимальное выражение числа n получается либо путем вычитания единицы из n , либо путем выражения n как произведения двух меньших множителей. Наименьший пример числа, оптимальное выражение которого не имеет этой формы, — это 353942783. Это простое число и, следовательно, также опровергает гипотезу Ричарда К. Гая о том, что сложность каждого простого числа p равна единице плюс сложность p — 1 . ^[5] На самом деле, можно показать, что . Более того, Венеция Ванг привела несколько интересных примеров, т.е. , , , но . ^[6] ${\displaystyle \|p\|=\|p-1\|=63}$ ${\displaystyle \|743\times 2\|=\|743\|=22}$ ${\displaystyle \|166571\times 3\|=\|166571\|=39}$ ${\displaystyle \|97103\times 5\|=\|97103\|=38}$ ${\displaystyle \|23^{2}\|=20}$ ${\displaystyle 2\|23\|=22}$

Рекомендации

1. Малер, К .; Попкен, Дж. (1953), «О проблеме максимума в арифметике», Nieuw Archief voor Wiskunde , 1 : 1–15, MR  0053986.
2. Гай, Ричард К. (1986), «Некоторые подозрительно простые последовательности», Нерешенные проблемы, American Mathematical Monthly , 93 (3): 186–190, doi : 10.2307/2323338, JSTOR  2323338, MR  1540817.
3. Шрайвер, Кристофер Э. (2015), Применения анализа цепей Маркова к целочисленной сложности , arXiv : 1511.07842 , Bibcode : 2015arXiv151107842S.
4. Кордвелл, К.; Эпштейн, А.; Хеммади, А.; Миллер, С.; Палссон, Э.; Шарма, А.; Штайнербергер, С.; Ву, Ю. (2017), Об алгоритмах вычисления целочисленной сложности , arXiv : 1706.08424 , Bibcode : 2017arXiv170608424C
5. Фуллер, Мартин Н. (1 февраля 2008 г.), Программа для расчета A005245, A005520, A005421, OEIS , получено 13 декабря 2015 г..
6. Ван, Венеция (октябрь 2012 г.), «Контрпример к основной гипотезе о выражении чисел с использованием только единиц», Journal of Number Theory , JNT, 133 (2): 391–397, doi : 10.1016/j.jnt.2012.08. 003.

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

• Вайсштейн, Эрик В. «Целочисленная сложность». Математический мир .