Дополнительная цепочка

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

Примеры

Например: (1,2,3,6,12,24,30,31) — цепочка сложения для 31 длины 7, так как

2 = 1 + 1

3 = 2 + 1

6 = 3 + 3

12 = 6 + 6

24 = 12 + 12

30 = 24 + 6

31 = 30 + 1

Цепочки сложения можно использовать для возведения в степень цепочки сложения . Этот метод позволяет выполнять возведение в степень с целочисленными показателями, используя количество умножений, равное длине цепочки сложения показателя степени. Например, цепочка сложения числа 31 приводит к методу вычисления 31-й степени любого числа n с использованием только семи умножений вместо 30 умножений, которые можно было бы получить при повторном умножении, и восьми умножений с возведением в степень путем возведения в квадрат :

н ² = п × п

н ³ = п ² × н

н ⁶ = п ³ × н ³

н ¹² = п ⁶ × н ⁶

н ²⁴ = п ¹² × н ¹²

н ³⁰ = п ²⁴ × н ⁶

н ³¹ = п ³⁰ × н

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

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

Одним из очень хорошо известных методов расчета относительно коротких цепочек сложения является бинарный метод , аналогичный возведению в степень возведением в квадрат . В этом методе цепочка сложения числа $n$ получается рекурсивно, из цепочки сложения для $n'=\lfloor n/2\rfloor$. Если $n$ четно, его можно получить в одну дополнительную сумму, как $n=n'+n'$. Если $n$ нечетно, этот метод использует две суммы для его получения путем вычисления $n-1=n'+n'$ а затем добавив один.

Факторный метод нахождения цепочек сложения основан на простой факторизации числа $n$ быть представленным. Если $n$ есть номер $p$ в качестве одного из его главных множителей, то цепочка сложения для $n$ можно получить, начав с цепочки для $n/p$, а затем соединив с ним цепочку для $p$, модифицированный путем умножения каждого из его чисел на $n/p$. Идеи факторного метода и бинарного метода можно объединить в m-арный метод Брауэра, выбрав любое число. $m$ (независимо от того, делит ли оно $n$), рекурсивно строя цепочку для $\lfloor n/m\rfloor$, объединяя цепочку для $m$ (модифицировано так же, как указано выше), чтобы получить $m\lfloor n/m\rfloor$, а затем прибавляем остаток. Дополнительные усовершенствования этих идей привели к созданию семейства методов, называемых методами скользящего окна .

Длина цепи

Позволять $l(n)$ обозначаю самый маленький $s$ так что существует цепочка сложениядлины $s$ который вычисляет $n$.Известно, что

$\log _{2}(n)+\log _{2}(\nu (n))-2.13\leq l(n)\leq \log _{2}(n)+\log _{2}(n)(1+o(1))/\log _{2}(\log _{2}(n))$,

где $\nu (n)$ - вес Хэмминга (число единиц) двоичного разложения $n$.

Можно получить цепочку сложения для $2n$ из цепочки сложения для $n$ включив одну дополнительную сумму $2n=n+n$, откуда следует неравенство $l(2n)\leq l(n)+1$ от длины цепей для $n$ и $2n$. Однако это не всегда равенство,как в некоторых случаях $2n$ может иметь более короткую цепочку, чем полученная таким способом. Например, $l(382)=l(191)=11$, заметил Кнут. Это возможно даже для $2n$ иметь более короткую цепочку, чем $n$, так что $l(2n)<l(n)$; самый маленький $n$ для чего это происходит $n=375494703$, за которым следует $602641031$, $619418303$и так далее (последовательность A230528 в OEIS ).

Цепь Брауэр

Цепь Брауэра или цепочка звездчатого сложения — это цепочка сложения, в которой каждая из сумм, используемых для расчета ее чисел, использует непосредственно предыдущее число. Число Брауэра — это число, для которого оптимальна цепочка Брауэра.

Брауэр доказал, что

л ^* (2 ^н −1) ≤ n − 1 + l ^* ( н )

где ⁠ $l^{*}$⁠ — длина самой короткой звездной цепочки. Для многих значений n , и в частности для n < 12509 , они равны: л ( п )= л ^* ( н ) . Но Хансен показал, что существуют некоторые значения n , для которых l ( n ) ≠ l ^* ( n ) , например n = 2 ⁶¹⁰⁶  + 2 ³⁰⁴⁸  + 2 ²⁰³²  + 2 ²⁰¹⁶ + 1, который имеет l ^* ( п ) знак равно 6110, л ( п ) ≤ 6109 . Наименьшее такое n равно 12509.

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

Основная статья: гипотеза Шольца

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

$l(2^{n}-1)\leq n-1+l(n).$

Известно, что это неравенство справедливо для всех чисел Хансена, являющихся обобщением чисел Брауэра; Нил Клифт проверил с помощью компьютера, что все $n\leq 5784688$ являются Хансеном (а 5784689 — нет). Клифт далее подтвердил, что на самом деле $l(2^{n}-1)=n-1+l(n)$ для всех $n\leq 64$.

См. также

• Цепочка сложения-вычитания
• Векториальная цепочка сложения
• цепь Лукаса

Ссылки

• Брауэр, Альфред (1939). «О цепочках сложения» . Бюллетень Американского математического общества . 45 (10): 736–739. дои : 10.1090/S0002-9904-1939-07068-7 . ISSN   0002-9904 . МР   0000245 .
• Ричард К. Гай (2004). Нерешенные проблемы теории чисел . Спрингер-Верлаг . ISBN  978-0-387-20860-2 . OCLC   54611248 . Збл   1058.11001 . Раздел С6.

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

• http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html
• Последовательность OEIS A003313 (Длина кратчайшей цепи присоединения для n) . Обратите внимание, что начальная «1» не учитывается (поэтому элемент №1 в последовательности равен 0).
• Ф. Бержерон, Ж. Берстель. С. Брлек «Эффективное вычисление цепочек сложения»