✨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: :² = × :³ = ² × :⁶ = ³ × ³ :¹² = ⁶ × ⁶ :²⁴ = ¹² × ¹² :³⁰ = ²⁴ × ⁶ :³¹ = ³⁰ ×

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

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. . 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)\; \backslash 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\; \backslash 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\; \backslash le\; 64$.