Ł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,\mathrm{\forall }i>0,\mathrm{\forall }j⩽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\ge {\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\le 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\ne 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 ℂ$ 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