Введение

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

Методы вычисления цепочек сложения

Вычисление цепи сложения минимальной длины – непростая задача; обобщённая версия этой задачи, в которой требуется найти цепь, одновременно формирующую каждое значение из заданной последовательности, является NP-полной. Не существует известного алгоритма, способного вычислить минимальную цепь сложения для заданного числа с гарантией разумного времени работы и небольшого расхода памяти. Однако известно несколько методов для вычисления относительно коротких цепей, которые не всегда оптимальны. Одним из наиболее известных методов вычисления относительно коротких цепей сложения является бинарный метод, аналогичный возведению в степень через квадраты. В этом методе цепь сложения для числа получается рекурсивно из цепи сложения для . Если чётно, его можно получить одним дополнительным сложением, как . Если нечётно, этот метод использует два сложения для его получения, вычисляя и затем прибавляя единицу. Цепь сложения для можно получить из цепи сложения для путем добавления одного дополнительного сложения , из чего следует неравенство для длин цепей и . Однако это не всегда равенство, поскольку в некоторых случаях может иметь более короткую цепь, чем полученная таким образом. Например, , как заметил Кнут. 1=l(n) = l*(n). Но Хансен показал, что существуют значения n, для которых l(n) ≠ l*(n), например, 1=n = 2^(6106) + 2^(3048) + 2^(2032) + 2^(2016) + 1, для которого 1=l*(n) = 6110, l(n) ≤ 6109. Наименьшее такое n равно 12509.

Гипотеза Шолца

Предположение Шолца (иногда называемое предположением Шолца — Брауэра или Брауэра — Шолца), названное в честь Арнольда Шолца и Альфреда Т. Брауэра, — это предположение 1937 года, утверждающее, что

Это неравенство, как известно, выполняется для всех чисел Хансена, являющихся обобщением чисел Брауэра; Нилл Клифт с помощью компьютера проверил, что все числа являются числами Хансена (а 5784689 — нет). Клифт дополнительно подтвердил, что на самом деле это верно для всех .