Xích cộng

Trong toán học, **xích cộng** cho số nguyên dương  là dãy số các số tự nhiên bắt đầu bằng 1 và kết thúc với , 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ố , 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ố  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:
:2 =  × 
:3 = 2 × 
:6 = 3 × 3
:12 = 6 × 6
:24 = 12 × 12
:30 = 24 × 6
:31 = 30 × 

## 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'=\lfloor n/2\rfloor. Nếu n chẵn thì nó có thể tính bằng tổng : n=n'+n'. Nếu n lẻ, phương pháp sử dụng hai tổng, tổng n-1=n'+n' 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\leq l(n) \leq \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
:
với  là độ dài chuỗi Brauer ngắn nhất.  Với một số giá giá trị *n*, đặc biệt là  thì bất đẳng thức trên thành đẳng thức: . Tuy nhiên, Hansen chứng minh rằng có một số giá trị *n* sao cho , ví dụ như  có . Số *n* nhỏ nhất có tính chất như vậy là 12509.

## Giả thuyết Scholz

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

*
*   Section C6.

## Liên kết ngoài
* http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html
* . 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"