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

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

• 1 Пример
• 2 Верхняя и нижняя границы
• 3 Алгоритмы и контрпримеры
• 4 Ссылки
• 5 Внешние ссылки

Например, число 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 )

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

$2\; x\; 3\; (k\; -\; 2\; x)\; /\; 3,\; где\; x\; =\; -\; k\; mod\; 3.\; \{\backslash \; displaystyle\; 2\; ^\; \{x\}\; 3\; ^\; \{(k-2x)\; /\; 3\}\; \{\backslash \; text\; \{where\}\}\; x\; =\; -k\; \{\backslash \; bmod\; \{3\}\}.\}$

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

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

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

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

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

• Weisstein, Eric W. «Целочисленная сложность». MathWorld.