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.D. E. Knuth, The Art of Computer Programming, Vol 2, "Seminumerical Algorithms", Section 4.6.3, 3rd edition, 1997

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 đủ.. A number of other papers state that finding a shortest addition chain for a single number is NP-complete, citing this paper, but it does not claim or prove such a result. 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  được tính đệ quy từ xích cộng cho . Nếu  chẵn thì nó có thể tính bằng tổng : . Nếu  lẻ, phương pháp sử dụng hai tổng, tổng  rồi tổng của tổng đó với 1

Độ dài chuỗi
Ký hiệu  là số tự nhiên  nhỏ nhất sao cho tồn tại xích cộng
độ dài  tính ra .
Ta chứng minh được rằng
,
với  là trọng số Hamming (số các bit 1) trong biểu diễn nhị phân của .

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:Achim Flammenkamp , Shortest Addition Chains . 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

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  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  với mọi .Guy (2004) p.169

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"

Thể loại:Chuỗi cộng
Thể loại:Bài toán NP-đủ