ในทางคณิตศาสตร์ลำดับการบวกสำหรับการคำนวณจำนวนเต็มบวกnสามารถแสดงได้ด้วยลำดับของจำนวนธรรมชาติที่เริ่มต้นด้วย 1 และสิ้นสุดด้วยnโดยที่แต่ละจำนวนในลำดับเป็นผลรวมของจำนวนก่อนหน้าสองจำนวนความยาวของลำดับการบวกคือจำนวนผลรวมที่จำเป็นในการแสดงจำนวนทั้งหมด ซึ่งน้อยกว่าจำนวนสมาชิกของลำดับอยู่ หนึ่ง ^{[ 1 ]}

ตัวอย่างเช่น (1,2,3,6,12,24,30,31) เป็นลำดับการบวกสำหรับ 31 ที่มีความยาว 7 เนื่องจาก

2 = 1 + 1

3 = 2 + 1

6 = 3 + 3

12 = 6 + 6

24 = 12 + 12

30 = 24 + 6

31 = 30 + 1

สามารถใช้การบวกแบบลูกโซ่สำหรับการยกกำลังแบบลูกโซ่ ได้ วิธีนี้ช่วยให้ สามารถ ยกกำลังด้วยเลขชี้กำลังจำนวนเต็มได้โดยใช้จำนวนการคูณเท่ากับความยาวของลูกโซ่การบวกสำหรับเลขชี้กำลังนั้น ตัวอย่างเช่น ลูกโซ่การบวกสำหรับ 31 นำไปสู่วิธีการคำนวณกำลังที่ 31 ของจำนวนใดๆnโดยใช้การคูณเพียงเจ็ดครั้ง แทนที่จะใช้การคูณ 30 ครั้งที่ได้จากการคูณซ้ำๆ และแปดครั้งสำหรับการยกกำลังโดยการยกกำลังสอง :

n ² = n × n

n ³ = n ² × n

n ⁶ = n ³ × n ³

n ¹² = n ⁶ × n ⁶

n ²⁴ = n ¹² × n ¹²

n ³⁰ = n ²⁴ × n ⁶

n ³¹ = n ³⁰ × n

การคำนวณสายโซ่การบวกที่มีความยาวน้อยที่สุดไม่ใช่เรื่องง่าย เวอร์ชันทั่วไปของปัญหานี้ ซึ่งต้องหาสายโซ่ที่สร้างค่าแต่ละค่าในลำดับพร้อมกันนั้น เป็นปัญหาNP-complete [ ^{2 ] ไม่มี}อัลกอริทึมใดที่ทราบกันว่าสามารถคำนวณสายโซ่การบวกที่สั้นที่สุดสำหรับจำนวนที่กำหนดได้โดยมีการรับประกันเวลาที่เหมาะสมหรือการใช้หน่วยความจำน้อย อย่างไรก็ตาม มีเทคนิคหลายอย่างที่ทราบกันว่าสามารถคำนวณสายโซ่ที่ค่อนข้างสั้นได้ แต่ก็ไม่ได้เหมาะสมที่สุดเสมอไป^{[ 3 ]}

เทคนิคที่รู้จักกันดีอย่างหนึ่งในการคำนวณสายโซ่การบวกที่ค่อนข้างสั้นคือวิธีไบนารีซึ่งคล้ายกับการยกกำลังโดยการยกกำลังสองในวิธีนี้ สายโซ่การบวกสำหรับจำนวนจะได้รับแบบเรียกซ้ำจากสายโซ่การบวกสำหรับถ้าเป็นจำนวนคู่ จะสามารถหาได้จากการบวกเพียงครั้งเดียว เช่นถ้าเป็นจำนวนคี่ วิธีนี้จะใช้การบวกสองครั้งเพื่อให้ได้ โดยการคำนวณแล้วบวกหนึ่งเข้าไป^{[ 3 ]}${\displaystyle n}$${\displaystyle n'=\lfloor n/2\rfloor }$${\displaystyle n}$${\displaystyle n=n'+n'}$${\displaystyle n}$${\displaystyle n-1=n'+n'}$

วิธีการแยกตัวประกอบสำหรับการค้นหาสายโซ่การบวกนั้นขึ้นอยู่กับการแยกตัวประกอบเฉพาะของจำนวนที่จะแสดง หากมีจำนวนหนึ่งเป็นตัวประกอบเฉพาะตัวหนึ่ง สายโซ่การบวกสำหรับสามารถหาได้โดยเริ่มจากสายโซ่สำหรับแล้วต่อสายโซ่สำหรับ เข้ากับสายโซ่ดังกล่าว โดยปรับเปลี่ยนโดยการคูณตัวเลขแต่ละตัวด้วยแนวคิดของวิธีการแยกตัวประกอบและวิธีการไบนารีสามารถรวมเข้าด้วยกันเป็นวิธีการ m-ary ของ Brauerโดยการเลือกจำนวนใดๆ(โดยไม่คำนึงว่าจะหาร ลงตัวหรือไม่) สร้างสายโซ่สำหรับซ้ำๆ ต่อสายโซ่สำหรับ(ปรับเปลี่ยนในลักษณะเดียวกันกับข้างต้น) เพื่อให้ได้แล้วบวกเศษที่เหลือ การปรับปรุงเพิ่มเติมของแนวคิดเหล่านี้ทำให้เกิดวิธีการต่างๆ ที่เรียกว่า วิธี การหน้าต่างเลื่อน^{[ 3 ]}${\displaystyle n}$${\displaystyle n}$${\displaystyle p}$${\displaystyle n}$${\displaystyle n/p}$${\displaystyle p}$${\displaystyle n/p}$${\displaystyle m}$${\displaystyle n}$${\displaystyle \lfloor n/m\rfloor }$${\displaystyle m}$${\displaystyle m\lfloor n/m\rfloor }$

ให้แทนค่าที่เล็กที่สุดเพื่อให้มีโซ่การบวกที่มีความยาวซึ่งคำนวณได้เป็นที่ทราบกันว่า โดยที่คือน้ำหนักแฮมมิง (จำนวนหนึ่ง) ของการขยายเลขฐานสองของ^{[ 4 ]}${\displaystyle l(n)}$${\displaystyle s}$${\displaystyle s}$${\displaystyle n}$$${\displaystyle \log _{2}n+\log _{2}\nu (n)-2.13\leq l(n)\leq \log _{2}n+\nu (n)-1,}$$$${\displaystyle l(n)\leq \log _{2}n+{\bigl (}1+o(1){\bigr )}{\frac {\log _{2}n}{\log _{2}\log _{2}n}},}$$${\displaystyle \nu (n)}$${\displaystyle n}$

เราสามารถสร้างสายโซ่การบวกสำหรับจากสายโซ่การบวกสำหรับได้โดยการรวมผลรวมเพิ่มเติมหนึ่งรายการซึ่งส่งผลให้เกิดความไม่เท่าเทียมกันในความยาวของสายโซ่สำหรับและอย่างไรก็ตาม นี่ไม่ใช่ความเท่าเทียมกันเสมอไป เนื่องจากในบางกรณีอาจมีสายโซ่ที่สั้นกว่าสายโซ่ที่ได้มาด้วยวิธีนี้ ตัวอย่างเช่นสังเกตโดย Knuth ^{[ 5 ]}เป็นไปได้ที่สำหรับจะมีสายโซ่ที่สั้นกว่าดังนั้น; ค่าที่เล็กที่สุดที่เกิดเหตุการณ์นี้คือ^[6]ซึ่ง^{ตามมา}ด้วย, , และอื่นๆ (ลำดับA230528ในOEIS ) ${\displaystyle 2n}$${\displaystyle n}$${\displaystyle 2n=n+n}$${\displaystyle l(2n)\leq l(n)+1}$${\displaystyle n}$${\displaystyle 2n}$${\displaystyle 2n}$${\displaystyle l(382)=l(191)=11}$${\displaystyle 2n}$${\displaystyle n}$${\displaystyle l(2n)<l(n)}$${\displaystyle n}$${\displaystyle n=375494703}$${\displaystyle 602641031}$${\displaystyle 619418303}$

โซ่Brauerหรือโซ่การบวกแบบดาวคือโซ่การบวกที่ผลรวมแต่ละผลที่ใช้ในการคำนวณตัวเลขจะใช้ตัวเลขก่อนหน้าทันทีตัวเลข Brauerคือตัวเลขที่โซ่ Brauer เหมาะสมที่สุด^{[ 5 ]}

บราวเออร์พิสูจน์ว่า

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

โดยที่⁠ ⁠${\displaystyle l^{*}}$คือความยาวของโซ่ดาวที่สั้นที่สุด^{[ 7 ]} สำหรับค่าของ จำนวนมากและโดยเฉพาะอย่างยิ่งสำหรับพวกมันจะเท่ากัน: ^{[ 8 ]} l ( n ) =  l ^* ( n )แต่ Hansen แสดงให้เห็นว่ามีค่าของn บางค่า ที่l ( n ) ≠  l ^* ( n )เช่นn  = 2 ⁶¹⁰⁶  + 2 ³⁰⁴⁸  + 2 ²⁰³²  + 2 ²⁰¹⁶  + 1ซึ่งมีl ^* ( n ) = 6110, l ( n ) ≤ 6109 ค่า nที่เล็กที่สุดดังกล่าวคือ 12509 ${\displaystyle n}$${\displaystyle n<12509}$

สมมติฐาน ของชอลซ์ (บางครั้งเรียกว่า สมมติฐาน ชอลซ์-บราวเออร์หรือสมมติฐานบราวเออร์-ชอลซ์ ) ซึ่งตั้งชื่อตามอาร์โนลด์ ชอลซ์และอัลเฟรด ที. บราวเออร์ เป็นสมมติฐานจากปี 1937 ที่ระบุว่า

${\displaystyle l(2^{n}-1)\leq n-1+l(n).}$

ความไม่เท่าเทียมกันนี้ทราบกันว่าใช้ได้กับจำนวน Hansen ทั้งหมด ซึ่งเป็นการขยายความของจำนวน Brauer; Neill Clift ตรวจสอบด้วยคอมพิวเตอร์ว่าทั้งหมดเป็น Hansen (ในขณะที่ 5784689 ไม่ใช่) ^{[ 6 ]} Clift ได้ตรวจสอบเพิ่มเติมว่าในความ เป็น จริงแล้วใช้ได้กับทั้งหมด^{[ 5 ]}${\displaystyle n\leq 5784688}$${\displaystyle l(2^{n}-1)=n-1+l(n)}$${\displaystyle n\leq 64}$

• ลำดับการบวกและการลบ
• โซ่การบวกเวกเตอร์
• โซ่ลูกัส

• ลำดับ OEIS A003313 (ความยาวของสายโซ่การบวกที่สั้นที่สุดสำหรับ n)โปรดทราบว่า "1" ตัวแรกจะไม่ถูกนับ (ดังนั้นองค์ประกอบหมายเลข 1 ในลำดับคือ 0)
• F. Bergeron, J. Berstel, S. Brlek "การคำนวณสายโซ่การบวกที่มีประสิทธิภาพ"