Xích cộng

Trong toán học, xích cộng cho số nguyên dương Bản mẫu:Mvar là dãy số các số tự nhiên bắt đầu bằng 1 và kết thúc với Bản mẫu:Mvar, sao cho mỗi số trong dãy là tổng của hai số trước đó trong dãy. Hai số trước đó không nhất thiết phải phân biệt. Độ dài của xích cộng là số tổng cần tính để ra số Bản mẫu:Mvar, nhỏ hơn một so với số lực lượng của dãy.

Các ví dụ

Để lấy ví dụ: (1,2,3,6,12,24,30,31) là xích cộng cho 31 có độ dài bằng 7 bởi

2 = 1 + 1

3 = 2 + 1

6 = 3 + 3

12 = 6 + 6

24 = 12 + 12

30 = 24 + 6

31 = 30 + 1

xích cộng có thể dùng để tính lũy thừa xích cộng. Phương pháp này cho phép tính lũy thừa với số mũ nguyên với số phép nhân bằng độ dài của chuỗi. Lấy ví dụ trên, sử dụng xích cộng trên ta chỉ cần sử dụng 7 phép nhân để lũy thừa bậc 31 của số Bản mẫu:Mvar tùy ý, thay vì 30 nếu phải nhân liên tiếp hoặc 8 nếu tính lũy thừa bằng chia nhị phân:

Bản mẫu:Mvar² = Bản mẫu:Mvar × Bản mẫu:Mvar

Bản mẫu:Mvar³ = Bản mẫu:Mvar² × Bản mẫu:Mvar

Bản mẫu:Mvar⁶ = Bản mẫu:Mvar³ × Bản mẫu:Mvar³

Bản mẫu:Mvar¹² = Bản mẫu:Mvar⁶ × Bản mẫu:Mvar⁶

Bản mẫu:Mvar²⁴ = Bản mẫu:Mvar¹² × Bản mẫu:Mvar¹²

Bản mẫu:Mvar³⁰ = Bản mẫu:Mvar²⁴ × Bản mẫu:Mvar⁶

Bản mẫu:Mvar³¹ = Bản mẫu:Mvar³⁰ × Bản mẫu:Mvar

Các phương pháp tính xích cộng

Tính xích cộng có độ dài tối thiểu cho số n không phải là dễ; dạng tổng quát của bài toán tính chuỗi có thể tính giá trị cho mỗi phần tử trong một dãy số cho trước là NP-đầy đủ. Chưa có thuật toán nào được biết để có thể tính xích cộng có độ dài tổi thiểu cho số n mà đảm bảo thời gian hoặc bộ nhớ hợp lý. Tuy nhiên, các kỹ thuật tính xích cộng với độ dài ngắn thì vẫn có nhưng sẽ không tối ưu.

Một trong những phương pháp phổ biến để tính là phương pháp nhị phân, tương tự với tính lũy thừa bằng bình phương.Trong phương pháp này, xích cộng cho $n$ được tính đệ quy từ xích cộng cho $n^{\prime }=\lfloor n/2\rfloor$. Nếu $n$ chẵn thì nó có thể tính bằng tổng : $n=n^{\prime }+n^{\prime }$. Nếu $n$ lẻ, phương pháp sử dụng hai tổng, tổng $n-1=n^{\prime }+n^{\prime }$ rồi tổng của tổng đó với 1

Độ dài chuỗi

Ký hiệu $l(n)$ là số tự nhiên $s$ nhỏ nhất sao cho tồn tại xích cộng độ dài $s$ tính ra $n$. Ta chứng minh được rằng

${\log }_2(n)+{\log }_2(\nu (n))-2.13\le l(n)\le {\log }_2(n)+{\log }_2(n)(1+o(1))/{\log }_2({\log }_2(n))$,

với $\nu (n)$ là trọng số Hamming (số các bit 1) trong biểu diễn nhị phân của $n$.

Chuỗi Brauer

Chuỗi Brauer hoặc xích cộng sao là xích cộng mà mỗi phần tử có tổng sử dụng số ngay trước nó. Số Brauer là số sao cho chuỗi Brauer tối ưu.

Brauer chứng minh rằng

Bản mẫu:Math

với Bản mẫu:Tmath là độ dài chuỗi Brauer ngắn nhất. Với một số giá giá trị n, đặc biệt là Bản mẫu:Math thì bất đẳng thức trên thành đẳng thức: Bản mẫu:Math. Tuy nhiên, Hansen chứng minh rằng có một số giá trị n sao cho Bản mẫu:Math, ví dụ như Bản mẫu:Math có Bản mẫu:Math. Số n nhỏ nhất có tính chất như vậy là 12509.

Giả thuyết Scholz

Bản mẫu:Main Giả thuyết Scholz ((đôi khi còn được gọi là Scholz–Brauer hoặc Brauer–Scholz), đặt tên theo Arnold Scholz và Alfred T. Brauer) là giả thuyết từ năm 1937 phát biểu rằng

$l(2^n-1)\le n-1+l(n).$

Bất đẳng thức này thỏa mãn với mọi số Hansen, dạng tổng quát của số Brauer; Neill Clift đã kiểm tra bằng máy tính cho mọi $n\le 5784688$ là số Hansen (số 5784689 thì không phải số Hansen). Hơn nữa Clift còn kiểm chứng được thêm rằng $l(2^n-1)=n-1+l(n)$ với mọi $n\le 64$.

Xem thêm

• xích cộng trừ
• xích cộng vectơ
• Chuỗi Lucas

Tham khảo

• Bản mẫu:Cite journal
• Bản mẫu:Cite book Section C6.

Liên kết ngoài

• http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html
• Bản mẫu:OEIS el. Note that the initial "1" is not counted (so element #1 in the sequence is 0).
• F. Bergeron, J. Berstel. S. Brlek "Efficient computation of addition chains"