Целочисленная сложность - Википедия - Integer complexity

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

Пример

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

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

Однако он не может быть представлен семью или меньшим числом. Следовательно, его сложность равна восьми.

Сложности чисел 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] позже Селфридж показал, что это число

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

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

Таким образом, сложность целого числа п по крайней мере 3 журнала3 п. Сложность п самое большее 3 журнала2 п (примерно 4.755 журнал3 п): выражение этой длины для п можно найти, применив Метод Хорнера к двоичное представление из п.[2] Почти все целые числа имеют представление, длина которого ограничена логарифмом с меньшим постоянным множителем, 3.529 журнал3 п.[3]

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

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

Алгоритмы вычисления целочисленной сложности были использованы для опровержения нескольких предположений о сложности, в частности, не обязательно, чтобы оптимальное выражение для числа п получается либо вычитанием единицы из п или выражая п как результат двух меньших факторов. Наименьший пример числа, оптимальное выражение которого не имеет этой формы, - 353942783. Это число простое число, а значит, и опровергает гипотезу о Ричард К. Гай что сложность каждого простого числа п это один плюс сложности п − 1.[5]

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

  1. ^ Малер, К.; Попкен, Дж. (1953), "О задаче на максимум в арифметике", Nieuw Archief voor Wiskunde, 1: 1–15, МИСТЕР  0053986.
  2. ^ Гай, Ричард К. (1986), «Некоторые подозрительно простые последовательности», «Нерешенные проблемы», Американский математический ежемесячный журнал, 93 (3): 186–190, Дои:10.2307/2323338, МИСТЕР  1540817.
  3. ^ Шрайвер, Кристофер Э. (2015), Приложения анализа цепей Маркова к целочисленной сложности, arXiv:1511.07842, Bibcode:2015arXiv151107842S.
  4. ^ Cordwell, K .; Эпштейн, А .; Hemmady, A .; Miller, S .; Palsson, E .; Sharma, A .; Steinerberger, S .; Ву Ю. (2017), Об алгоритмах вычисления целочисленной сложности, arXiv:1706.08424, Bibcode:2017arXiv170608424C
  5. ^ Фуллер, Мартин Н. (1 февраля 2008 г.), Программа для расчета A005245, A005520, A005421, OEIS, получено 2015-12-13.

внешняя ссылка