An **addition chain** is a sequence of integers starting from 1, where each subsequent number is obtained by adding any two previous numbers in the sequence. The goal of an addition chain is to reach a specific target number using the fewest possible additions. For example, an addition chain for the number 15 could be: 1. Start with 1. 2. Add 1 + 1 to get 2. 3. Add 1 + 2 to get 3.
Articles by others on the same topic
An addition chain for a positive integer is , where each is the sum of two earlier entries, which may coincide. It computes in multiplications by reusing previously computed powers. For example, computes in five multiplications.