Łańcuch dodawania

Łańcuch dodawania dla obliczenia liczby naturalnej $n$ to sekwencja liczb naturalnych $a_{0}=1,a_{1},\dots ,a_{r}=n$ taka, że każdy jej element jest sumą elementów poprzednich, co można zapisać jako:

$a_{i}=a_{j}+a_{k},\quad \forall i>0,\quad \forall j\leqslant k<i$.

Pierwszym krokiem tworzenia łańcucha dodawania dla $n$ jest zawsze $a_{1}=1+1=2$. Drugim krokiem może być $a_{2}=1+1=2$, $a_{2}=1+2=3$, bądź $a_{2}=2+2=4$. Tym samym, długość $s$ łańcucha dodawania dla $n$ jest ograniczona od dołu przez $s\geq \log _{2}(n)$ co ma miejsce dla $n=2^{s}$. Jak łatwo zauważyć długość łańcucha dodawania dla $n$ jest również ograniczona od góry przez $s\leq n-1$.

Oznaczmy przez $l(n)$ najkrótszą długość łańcucha dodawania dla $n$. Jej określenie (sekwencja OEIS A003313) nie jest łatwe; udowodniono, że uogólniona wersja tego problemu jest problemem NP-zupełnym. Ponadto dla $n\neq 2^{s}$ może istnieć wiele różnych łańcuchów o najkrótszej długości.

Łańcuchy dodawania o najkrótszej długości $l(n)$ można wykorzystać do optymalizacji potęgowania przeprowadzając potęgowanie z wykładnikami całkowitymi przy użyciu liczby iloczynów równej najkrótszej długości łańcucha dodawania dla wykładnika. Na przykład łańcuch $\{1,2,3,6,12,24,30,31\}$ zapewnia minimalną długość siedmiu kroków dla $n=31$, ponieważ

2 = 1 + 1

3 = 2 + 1

6 = 3 + 3

12 = 6 + 6

24 = 12 + 12

30 = 24 + 6

31 = 30 + 1

Tym samym, obliczenie 31. potęgi dowolnej liczby $x\in \mathbb {C}$ wymaga tylko siedmiu, a nie 30 iloczynów:

$x^{2}=x\cdot x$,

$x^{3}=x^{2}\cdot x$,

$x^{6}=x^{3}\cdot x^{3}$,

$x^{12}=x^{6}\cdot x^{6}$,

$x^{24}=x^{12}\cdot x^{12}$,

$x^{30}=x^{24}\cdot x^{6}$,

$x^{31}=x^{30}\cdot x$,

przy wykorzystaniu iloczynów przeprowadzonych wcześniej. Niezależnie od liczby części elementarnych, minimalny indeks złożenia obiektu składającego się z $n$ takich części jest zadany najkrótszym łańcuchem dodawania dla $n$.

Linki zewnętrzne

• A003313