Łańcuch dodawania

W matematyce łańcuch dodawania do obliczania dodatniej liczby całkowitej n można przedstawić jako ciąg liczb naturalnych zaczynający się od 1 i kończący na n , tak że każda liczba w ciągu jest sumą dwóch poprzednich liczb. Długość łańcucha dodawania to liczba sum potrzebnych do wyrażenia wszystkich jego liczb, czyli o jeden mniej niż liczność ciągu liczb .

Przykłady

Na przykład: (1,2,3,6,12,24,30,31) jest łańcuchem dodawania dla 31 o długości 7, ponieważ

2 = 1 + 1

3 = 2 + 1

6 = 3 + 3

12 = 6 + 6

24 = 12 + 12

30 = 24 + 6

31 = 30 + 1

Łańcuchy dodawania mogą być używane do potęgowania łańcucha dodawania . Ta metoda umożliwia potęgowania z wykładnikami całkowitymi przy użyciu liczby mnożeń równej długości łańcucha dodawania dla wykładnika. Na przykład łańcuch dodawania dla 31 prowadzi do metody obliczania 31. potęgi dowolnej liczby n przy użyciu tylko siedmiu mnożeń, zamiast 30 mnożeń, które można by uzyskać z wielokrotnego mnożenia, i ośmiu mnożeń z potęgowaniem przez podniesienie do kwadratu :

n ² = n × n

n ³ = n ² × n

n ⁶ = n ³ × n ³

n ¹² = n ⁶ × n ⁶

n ²⁴ = n ¹² × n ¹²

n ³⁰ = n ²⁴ × n ⁶

n ³¹ = n ³⁰ × N

Metody obliczania łańcuchów dodawania

Obliczenie łańcucha dodawania o minimalnej długości nie jest łatwe; uogólniona wersja problemu, w której należy znaleźć łańcuch tworzący jednocześnie każdą z sekwencji wartości, jest NP-zupełna. Nie ma znanego algorytmu, który mógłby obliczyć minimalny łańcuch dodawania dla danej liczby z jakąkolwiek gwarancją rozsądnego czasu lub małego wykorzystania pamięci. Jednak znanych jest kilka technik obliczania stosunkowo krótkich łańcuchów, które nie zawsze są optymalne.

Jedną z bardzo dobrze znanych technik obliczania stosunkowo krótkich łańcuchów dodawania jest metoda binarna , podobna do potęgowania przez podnoszenie do kwadratu . W tej metodzie łańcuch dodawania dla liczby ${$ uzyskiwany rekurencyjnie z łańcucha dodawania dla $\ Displaystyle n'= \ lfloor n/2 \ rfloor}$ . Jeśli $parzysta$ można ją uzyskać w jednej dodatkowej sumie, ponieważ ${\ Displaystyle n = n'+ n'}$ . Jeśli $a$$nieparzysta$ ją uzyskać, obliczając, dodając

Metoda czynnikowa $rozkładzie na$ do znajdowania łańcuchów dodawania opiera się na czynniki pierwsze liczby, która ma być reprezentowana. Jeśli $dla$$n / p}$ jest liczba , to łańcuch dodawania dla można uzyskać, zaczynając od łańcucha $n$$displaystyle$ , a następnie łącząc z nim łańcuch dla ${\ displaystyle p}$ , zmodyfikowany przez pomnożenie każdej z jej liczb przez ${\ displaystyle n/p}$ . Idee metody czynnikowej i metody binarnej można połączyć w $-$ ary Brauera, wybierając dowolną liczbę niezależnie od tego, czy dzieli $,$ rekurencyjnie konstruując łańcuch dla ${\ Displaystyle \ lfloor n/m \ rfloor}$ , łącząc łańcuch dla ${\ Displaystyle m}$ (zmodyfikowany w taki sam sposób jak powyżej), $uzyskać$ dodać Dodatkowe udoskonalenia tych pomysłów prowadzą do powstania rodziny metod zwanych metodami przesuwanego okna .

Długość łańcucha

Niech $l (n)}$$Displaystyle$ oznacza najmniejszy , tak aby istniał łańcuch dodawania o długości $displaystyle$ który oblicza $n$ . Wiadomo, że

${\ Displaystyle \ log _ {2} (n) + \ log _ {2} (\ nu (n)) -2,13 \ równoważnik l (n) \ równoważnik \ log _ {2} (n) +\log _{2}(n)(1+o(1))/\log _{2}(\log _{2}(n))}$ ,

gdzie $n$ wagą (liczbą jedynek) rozwinięcia binarnego $}$ n .

Można uzyskać łańcuch dodawania dla z łańcucha dodawania dla $,$$z$ jedną dodatkową sumę , której wynika $displaystyle 2n = n + n}$ nierówność ${\ Displaystyle l (2n) \ równoważnik l (n) + 1}$ na długości łańcuchów dla i ${\ displaystyle n}$${\ Displaystyle 2n}$ . $zawsze$ jest to równość, ponieważ w niektórych przypadkach może mieć krótszy łańcuch niż ten uzyskany w ten sposób Na przykład, zaobserwowane przez Knutha ${\ Displaystyle l (382) = l (191) = 11} .$ Możliwe jest nawet, że $displaystyle n}$ będzie krótszy niż ${\$ , więc ${\ Displaystyle l (2n) <l (n)}$ ; Najmniejszy ${\ displayStyle n}$ , dla którego to się dzieje, to ${\ displayStyle n = 375494703}$ , a następnie ${\ displayStyle 602641031}$ , ${\ wyświetla się 619418303}$ i SO ON (SO ON (SOCENCE AL (sekwencja A230528 w in . OEIS ).

Łańcuch Brauera

Łańcuch Brauera lub łańcuch dodawania gwiazd to łańcuch dodawania, w którym każda z sum użytych do obliczenia jego liczb wykorzystuje bezpośrednio poprzednią liczbę. Liczba Brauera to liczba, dla której łańcuch Brauera jest optymalny.

Brauer to udowodnił

l ^* (2 ⁿ −1) ≤ n - 1 + l ^* ( n )

gdzie $gwiazdy$ długością najkrótszego łańcucha Dla wielu wartości n , aw szczególności dla n < 12509 , są one równe: l ( n ) = l ^* ( n ) . Ale Hansen pokazał, że istnieją pewne wartości n , dla których l ( n ) ≠ l ^* ( n ) , takie jak n = 2 · ⁶¹⁰⁶ + 2 ³⁰⁴⁸ + 2 ²⁰³² + 2 ²⁰¹⁶ + 1 co ma l ^* ( n ) = 6110, l ( n ) ≤ 6109 . Najmniejsze takie n to 12509.

przypuszczenie Scholza

Główny artykuł: hipoteza Scholza

Przypuszczenie Scholza (czasami nazywane przypuszczeniem Scholza – Brauera lub Brauera – Scholza ), nazwane na cześć Arnolda Scholza i Alfreda T. Brauera ), jest przypuszczeniem z 1937 r. Stwierdzającym, że

${\ Displaystyle l (2 ^ {n} -1) \ równoważnik n-1 + l (n).}$

Wiadomo, że ta nierówność obowiązuje dla wszystkich liczb Hansena, uogólnienia liczb Brauera; Neill Clift sprawdził komputerowo, że wszyscy $5784689$ nie jest $l (n)}$ + dla wszystkich ${\ Displaystyle n \ równoważnik 64}$ .

Zobacz też

• Łańcuch dodawania i odejmowania
• Wektorowy łańcuch dodawania
• Łańcuszek Lucasa

•    Brauera, Alfreda (1939). „O łańcuchach dodawania” . Biuletyn Amerykańskiego Towarzystwa Matematycznego . 45 (10): 736–739. doi : 10.1090/S0002-9904-1939-07068-7 . ISSN 0002-9904 . MR 0000245 .
•     Richard K. Guy (2004). Nierozwiązane problemy w teorii liczb . Springer-Verlag . ISBN 978-0-387-20860-2 . OCLC 54611248 . Zbl 1058.11001 . Sekcja C6.

Linki zewnętrzne

• http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html
• OEIS A003313 (Długość najkrótszego łańcucha dodawania dla n) . Zauważ, że początkowa „1” nie jest liczona (więc elementem nr 1 w sekwencji jest 0).
• F. Bergeron, J. Berstel. S. Brlek "Efektywne obliczanie łańcuchów dodawania"