Xích cộng

Trong toán học, xích cộng cho số nguyên dương n là dãy số các số tự nhiên bắt đầu bằng 1 và kết thúc với n, 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ố n, nhỏ hơn một so với số lực lượng của dãy.^[1]

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ố n 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:

n² = n × n

n³ = n² × n

n⁶ = n³ × n³

n¹² = n⁶ × n⁶

n²⁴ = n¹² × n¹²

n³⁰ = n²⁴ × n⁶

n³¹ = n³⁰ × n

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 đủ.^[2] 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.^[3]

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 ${\displaystyle n}$ được tính đệ quy từ xích cộng cho ${\displaystyle n'=\lfloor n/2\rfloor }$. Nếu ${\displaystyle n}$ chẵn thì nó có thể tính bằng tổng : ${\displaystyle n=n'+n'}$. Nếu ${\displaystyle n}$ lẻ, phương pháp sử dụng hai tổng, tổng ${\displaystyle n-1=n'+n'}$ rồi tổng của tổng đó với 1^[3]

Độ dài chuỗi

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

${\displaystyle \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 ${\displaystyle \nu (n)}$ là trọng số Hamming (số các bit 1) trong biểu diễn nhị phân của ${\displaystyle n}$.^[4]

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.^[5]

Brauer chứng minh rằng

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

với ${\displaystyle l^{*}}$ là độ dài chuỗi Brauer ngắn nhất. Với một số giá giá trị n, đặc biệt là n < 12509 thì bất đẳng thức trên thành đẳng thức:^[6] l(n) = l^*(n). Tuy nhiên, Hansen chứng minh rằng có một số giá trị n sao cho l(n) ≠ l^*(n), ví dụ như n = 2⁶¹⁰⁶ + 2³⁰⁴⁸ + 2²⁰³² + 2²⁰¹⁶ + 1 có l^*(n) = 6110, l(n) ≤ 6109. Số n nhỏ nhất có tính chất như vậy là 12509.

Giả thuyết Scholz

Bài chi tiết: 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

${\displaystyle l(2^{n}-1)\leq 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 ${\displaystyle n\leq 5784688}$ là số Hansen (số 5784689 thì không phải số Hansen).^[7] Hơn nữa Clift còn kiểm chứng được thêm rằng ${\displaystyle l(2^{n}-1)=n-1+l(n)}$ với mọi ${\displaystyle n\leq 64}$.^[5]

Xem thêm

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

Tham khảo

1. D. E. Knuth, The Art of Computer Programming, Vol 2, "Seminumerical Algorithms", Section 4.6.3, 3rd edition, 1997
2. Downey, Peter; Leong, Benton; Sethi, Ravi (1981), “Computing sequences with addition chains”, SIAM Journal on Computing, 10 (3): 638–646, doi:10.1137/0210047. 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.
3. ^ Otto, Martin (2001), Brauer addition-subtraction chains (PDF), Diplomarbeit, University of Paderborn, Bản gốc (PDF) lưu trữ ngày 19 tháng 10 năm 2013, truy cập ngày 19 tháng 10 năm 2013.
4. Schönhage, Arnold (1975), “A Lower Bound for the Length of Addition Chains”, Theoretical Computer Science, 1 (1): 1–12, doi:10.1016/0304-3975(75)90008-0
5. ^ Guy (2004) p.169
6. Achim Flammenkamp , Shortest Addition Chains
7. Clift, Neill Michael (2011). “Calculating optimal addition chains” (PDF). Computing. 91 (3): 265–284. doi:10.1007/s00607-010-0118-8.

• Brauer, Alfred (1939). “On addition chains”. Bulletin of the American Mathematical Society. 45 (10): 736–739. doi:10.1090/S0002-9904-1939-07068-7. ISSN 0002-9904. MR 0000245.
• Richard K. Guy (2004). Unsolved Problems in Number Theory. Springer-Verlag. ISBN 978-0-387-20860-2. OCLC 54611248. Zbl 1058.11001. 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"