ADDCHAIN - Editorial

[anton_lunyov]

PROBLEM LINK:

Practice
Contest

DIFFICULTY:

Challenge

PREREQUISITES:

Arbitrary-precision arithmetic

PROBLEM:

An addition chain of length L for a positive integer N is defined to be an ascending sequence [A₀, A₁, …, A_L] such that the following properties hold:

• A₀ = 1, A_L = N.
• For all i > 0, there exist j and k less than i (not necessarily distinct) such that A_i = A_j + A_k.

The problem is to find relatively short addition chain for a given positive integer N. Your algorithm should be able to produce an addition chain of the length at most 500 for numbers up to 10¹⁰⁰.

QUICK EXPLANATION:

Several techniques could be used to produce relatively short addition chains for a given integer N:

• Method based on the representation of N in base M = 2^k. The case M = 4 supposed to be the easiest way to get AC. The standard and well-known approach with M = 2 supposed to get WA.
• Method based on factorization of N.

DETAILED EXPLANATION:

Many of you were curious how to store such large numbers, what data type to use. Just remember how you deal with numbers in a grade school. For example when you want to add two numbers you write them one under another like this:

1234567
   9871

and then consider each pair of digits written one under another, add them up, write the last digit of the sum to the result and carry first digit of the sum to the next position if the sum is greater than 9. In this example we at first add 7 and 1 to get 8 without any carries, then add 6 and 7 to get 13, write 3 to the result and carry 1 to the next position, then add 6 and 8 to get 14, but then add our carry 1 to get 15, write 5 to the result and again carry 1 to the next position and so on.

So in a childhood we deal with numbers like with arrays of digits. Let’s do the same here. We can read the given number character by character and fill the corresponding array by digits we read. For this problem we should be able to do some other basic operations with numbers like multiplication, subtraction, division. If you never deal with the problems of such type the best advice would be to remember how you perform all these operations in a grade school and analyze these procedures to produce algorithms that could be implemented at the language of your choice. Also I can suggest you to read the following tutorial where very clearly and in detail described how to multiply the large number by the small number. Another reference is Chapter 4. Arithmetic, Section 4.3. Multiple-Precision Arithmetic, Subsection 4.3.1. The Classical Algorithms, in Art of Computer Programming, Vol 2 (Seminumerical algorithms), written by Donald Knuth.

Some languages like Java or Python have built-in data types for dealing with such large numbers. If your language supports this then you can don’t worry about all the stuff written above and enjoy an advantage of your language.

Now as we know how to deal with numbers let’s return to our problem.

Firstly, there is an alternative way of looking at this problem – imagine we are given a variable x and we have to compute xⁿ for some given n. At any stage we can multiply two of the quantities that were already computed (initially we only have x) and create a new quantity, i.e., if we multiplied x^a and x^b, we now would have x^a+b. Our goal is to create xⁿ using minimum number of operations. This problem is identical to problem of addition chains. In this form however we see the deep connection of addition chains with computation of powers.

Before we see some approaches to solve this problem, let’s make an easy observation – we could remove the condition that numbers in addition chains should be in ascending order. Whatever addition chain we get, we can remove duplicates and sort the remaining numbers. Thus obtained sequence still be an addition chain. So in this discussion we would assume that there is no condition that numbers are in strictly ascending order.

---

1. Binary Representation Method:
Let’s look at the binary representation of N. We can write N as 2^h₁ + … + 2^h_K where h₁ > h₂ >…h_K >=0. So the actual binary representation of N has length M + 1 where we set for simplicity M = h₁. To obtain an addition chain for N we start with creating of all powers of 2 up to 2^M:
2 = 1 + 1,
4 = 2 + 2,
…,
2^M = 2^M-1 + 2^M-1.
This takes M steps. After this we can add those powers of 2 which appear in binary representation of N, that is, 2^h₁, …, 2^h_K. This takes K-1 additional steps. Thus we get addition chain of the length M + K - 1 for N.

Consider an example to illustrate this method. Let N = 999. Then we have N = 512 + 256 + 128 + 64 + 32 + 4 + 2 + 1. Hence we start our addition chain as:
2 = 1 + 1,
4 = 2 + 2,
8 = 4 + 4,
16 = 8 + 8,
32 = 16 +16,
64 = 32 + 32,
128 = 64 + 64,
256 = 128 + 128,
512 = 256 + 256.

Now we need to add all powers of two that are presented in the representation of N. This leads to the following further steps:
768 = 512 + 256,
896 = 768 + 128,
960 = 896 + 64,
992 = 960 + 32,
996 = 992 + 4,
998 = 996 + 2,
999 = 998 + 1.

Thus, we obtain an addition chain {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 768, 896, 960, 992, 996, 998, 999} of length 16 for N.

But this simple approach is not enough to get AC here. Indeed, the worst case for this method is the number N = 2³³² - 1 = 8.749e99 for which M = 331 and K = 332 so our addition chain will have length 331 + 332 – 1 = 662 which is much larger than the required bound 500.

---

2. 4-base Representation Method:
Now we consider a method that supposed to be the easiest way to get AC. Let N = D_K * 4^K + D_K-1 * 4^K-1 + … + D₁ * 4 + D₀ is 4-base representation of N. So 0 <= D_j <=3, 0 <= j <= K, and D_K > 0. The first two steps of addition chain will be
2 = 1 + 1,
3 = 2 + 1.
Now we have with us all digits D_K, D_K-1 , …, D₁, D₀. Since we already have D_K we can obtain 2 * D_K and 4 * D_K in two consecutive steps. Next we can obtain 4 * D_K + D_K-1 in one more step. Then again apply two doublings to this number and add D_K-2 and so on. In the final step we have D_K * 4^K-1 + D_K-1 * 4^K-2 + … + D₁ so by two more doublings and adding of D₀ we obtain N. Finally note that when D_i = 0 we should simply skip the step of adding D_i. This method allows us to get N only in at most 2 + 3 * (K-1) = 3 * K - 1 steps. Since N < 10¹⁰⁰ then K <= 166 and hence our addition chain has length at most 497.

Let’s see how this method performs for previously considered number N = 999. The 4-base representation of N is 999 = 3 * 256 + 3 * 64 + 2 * 16 + 1 * 4 + 3. According to the description we will consecutively obtain
3 * 4 + 3 = 15,
15 * 4 + 2 = 62,
4 * 62 + 1 = 249,
4 * 249 + 3 = 999.
Let’s see how exactly will look the corresponding addition chain. It starts as:
2 = 1 + 1,
3 = 2 + 1.
Now according to the description we get the following steps:
6 = 3 + 3,
12 = 6 + 6,
15 = 12 + 3,
30 = 15 + 15,
60 = 30 + 30,
62 = 60 + 2,
124 = 62 + 62,
248 = 124 + 124,
249 = 248 + 1,
498 = 249 + 249,
996 = 498 + 498,
999 = 996 + 3.

Thus, we obtain an addition chain {1, 2, 3, 6, 12, 15, 30, 60, 62, 124, 248, 249, 498, 996, 999} of length 14 for N which is by two shorter than for the previous method.

---

3. M-base Representation Method where M = 2^P:
We can easily generalize previous method for arbitrary base that is a power of two.
Let M = 2^P and write N in base M. So N = D_K * M^K + D_K-1 * M^K-1 + … + D₁ * M + D₀, where 0 <= D_j < M, 0 <= j <= K, and D_K > 0. The corresponding sequence of steps will be (we didn’t write from what numbers we get the particular number if it is clear enough):

2 = 1 + 1,
3 = 2 + 1,
4 = 3 + 1,
…
M-1 = (M-2) + 1,

2 * D_K = D_K + D_K,
4 * D_K = (2 * D_K) + (2 * D_K),
…
M * D_K = (M/2 * D_K) + (M/2 * D_K),
M * D_K + D_K-1,

2 * (M * D_K + D_K-1),
4 * (M * D_K + D_K-1),
…
M * (M * D_K + D_K-1),
M * (M * D_K + D_K-1) + D_K-2,

…

2 * (D_K * M^K-1 + … + D₂ * M + D₁),
…
M * (D_K * M^K-1 + … + D₂ * M + D₁),
M * (D_K * M^K-1 + … + D₂ * M + D₁) + D₀.

The length of this chain is M-2 + K * (P+1). Now scenario how to proceed further under the given approach now is clear. We simply need to check all values of P and choose the one that gives the shortest chain. Also note that in general this chain can have repetitions and numbers can be not in ascending order. To make it correct we can of course follow general suggestion described above. But here it is better to describe explicitly what need to be done in order to make this chain correct. At first if some D_j = 0 we can skip the step of adding D_j. Next if D_K < M/2 (first digit) then we can delete several numbers of the form 2^j * D_K from the second block of the chain that were already in the first block. Finally the most important observation is that in general we don’t need to obtain all numbers from 2 to M – 1 at the first block since we only need to have values D₀, D₁, …, D_K to perform future steps. It allows to use large values of P with big chances to get short addition chain if there is relatively small number of different digits in 2^P-base representation of N.

Now let’s estimate the length M-2 + K * (P+1) of obtained chain in terms of N and P. Clearly, K is about log_MN = log N / log M = log N / P, where log X = log₂X. (Note that in math log usually stands for natural logarithm.) Hence length of the constructed chain is about 2^P + log N / P * (P + 1) = log N + 2^P + log N / P. One can see that the best theoretical value of P is near log (log N) – log (log (log N)). But in practice it is better to check all values of P.

Finally we note that this method can be improved further. The length of the chain can be made M/2 + K * (P+1). We left this as an exercise to the reader. This modification is called a Sliding Window Method.

Now let’s consider how this method performs on our usual N = 999. We consider M = 8. The 8-base representation for N is 999 = 512 + 7 * 64 + 4 * 8 + 7. The steps according to the general rule will be:
2 = 1 + 1,
3 = 2 + 1,
4 = 3 + 1,
5 = 4 + 1,
6 = 5 + 1,
7 = 6 + 1,

2 = 1 + 1,
4 = 2 + 2,
8 = 4 + 4,
15 = 8 + 7,

30 = 15 + 15,
60 = 30 + 30,
120 = 60 + 60,
124 = 120 + 4,

248 = 124 + 124,
496 = 248 + 248,
992 = 496 + 496,
999 = 992 + 7.

So we get addition chain of length 18. Deleting repetitions we decrease length to 16. But we can do more. Note that we need only 1, 4 and 7 for further steps. Hence we can delete from our addition chain, for example, 3 and 6 to obtain a chain {1, 2, 4, 5, 7, 8, 15, 30, 60, 120, 124, 248, 496, 992, 999} of the length 14.

---

4. Factor Method:
Note that if A is addition chain for N of length p, and B is addition chain for M of length q, we can write an addition chain for N * M of length p + q. Indeed, let A = [1, a₁, a₂, …, a_p] and B = [1, b₁, b₂, …, b_q]. Consider L = [ 1, a₁, a₂, …, a_p = N, N * b₁, …, N * b_q = N * M]. This is a valid addition chain since equality b_i = b_j + b_k implies N * b_i = N * b_j + N * b_k which means that last q numbers of L satisfy definition of addition chain.

General method to create an addition chain based on this observation is the following. If N is composite then take the smallest prime divisor of N, say P, find recursively by this method an addition chain for P and N / P and concatenate them using above scheme. If N is prime then simply find addition chain for N – 1 using this method and add one more step of adding 1 and N – 1 in the end of this addition chain.

However in this problem you had to use this method wisely since it is hard to factorize such large number. So a hack is to consider N as “prime” if it has no divisors smaller than 1000 or 10000. such modified Factor Method incidentally is sufficient to get Accepted, however possibly there exists N < 10¹⁰⁰ for which it produces an addition chain with length > 500.

Let’s apply this method to N = 999. We have 999 = 3 * 3 * 3 * 37. Hence we need to find addition chain for 3, 37 and then combine them. The only addition chain for 3 is [1, 2, 3]. Let’s consider 37. It is a prime number. Hence we need to deal with 37 – 1 = 36 = 2 * 2 * 3 * 3. The only addition chain for 2 is [1, 2]. Thus combining four addition chains (two chains for 2 and two chain for 3) we get the following addition chain for 36 of the length 6: [1, 2, 4, 8, 12, 24, 36]. The corresponding addition chain for 37 is [1, 2, 4, 8, 12, 24, 36, 37]. Thus combining this addition chain with three addition chains for 3 we get the following addition chain for 999: [1, 2, 4, 8, 12, 24, 36, 37, 74, 111, 222, 333, 666, 999]. The length of this addition chain is 13 and in fact there are no shorter addition chains for N = 999 (see for example here).

Thus among all considered methods the best one for considered example is Factor Method.

---

5. Very short addition chains for numbers of the form 2^N - 1:

Let’s introduce some notation. An addition chain C = [A₀, A₁, …, A_L] is called a star chain if A_i = A_i-1 + A_j for all i > 0 where j < i is some index depending on i. The length of the shortest addition chain for a given N is denoted as l(N). The length of the shortest star chain is denoted as l’(N) (in literature the star * is used but Markdown do not allow to make this properly :))

Brauer proved that l(2^N - 1) <= N-1 + l’(N) which is very outstanding since 2^N - 1 is the toughest case for binary method mentioned above and this estimate provides really short addition chain for 2^N - 1. You can read about how Brauer constructed an addition chain for such numbers in his paper. Here we discuss two simple approaches that also produce quite short addition chains for numbers of such form.

The first one is a simple method that uses recursion. Here is the algorithm:

If N is odd:
     Find out addition chain for 2^N-1 - 1. Double last number and add 1.
Else if N is even:
     Find out addition chain for 2^N/2 - 1. Double its last number N/2 times and finally add 2^N/2 - 1 again.

It can be seen that this method uses one additional step for zero digit of N in binary and three additional steps for unit digit. Hence this method produces an addition chain of length N + M + 2 * K - 4 in notations introduced in binary method explanation.

We can get rid of this annoying factor 2 near K. The next method is in fact the actual Brauer method where instead of the shortest star chain for N we use the chain produced by the binary method.

Recall the notations introduced in binary method explanation: N = 2^h₁ + … + 2^h_K where h₁ > h₂ > … > h_K >=0. We denote M = h₁. Put N(0) = N and N(j) = N(j-1) - 2^h_j for j = 1, 2, …, K. Note that N(K-1) = 2^h_K and N(K) = 0. Next write

2^N - 1 = (2^N(0) - 2^N(1)) + (2^N(1) - 2^N(2)) + … + (2^N(K-1) - 2^N(K)).         (1)

Clearly 2^N(j-1) - 2^N(j) = 2^N(j) * (2^2h_j - 1) where N(j) < 2^h_j since h₁ > h₂ > … > h_K.

Now we proceed as follows. The main formula in use is 2^{2X + 1} - 1 = (2^2X - 1) * (2^2X + 1). We will have M steps. At the beginning we have 1 = 2²⁰ - 1. Now assume that we have 2^2X - 1 for some X. Then we double it 2^X times to get 2^{2X + 1} - 2^2X and then add 2^2X - 1 to this number to get 2^{2X + 1} - 1.

Note that during these calculations we obtain all numbers of the form 2^k * (2^2X - 1) with 0 <= k <= 2^X. So if X = h_j then since N(j) < 2^h_j the number 2^N(j-1) - 2^N(j) = 2^N(j) * (2^2h_j - 1) was obtained during this process.

Finally after the last step we will have the number 2^2M - 1. We make additional N(1) doublings to obtain number 2^N(1) * (2^2M - 1). Now we have all summands in the sum given in equation (1) and can obtain 2^N - 1 in K-1 more additions.

The total number of steps in this addition chain is N + M + K - 2.

First three tests among 50 was created to encourage this approach.

---

6. Method of Continued Fractions:

Introduced here, this method can generate some short star chains. Setter and tester did not check performance of this method and it might be a fun post-contest exercise to try and implement this method. It hopefully would produce very short addition chains for most of the tests in the input data.

---

We kindly ask contestants that have other approaches to describe them in the answers to this editorial.

---

Test Data:

Test data for this problem were created very carefully and have many different special hand tests that were created to fail or to encourage different approaches. Though Codechef policy is to keep test data in secret we decided to make them public for this problem. You can download the whole of the test suite used for this problem here. The detailed description of test data is contained here. You can test several of the described approaches on these test cases.

SETTER’S SOLUTION:

Can be found here. Setter used 4-base method described above.

TESTER’S SOLUTION:

Can be found here. Tester used M-base method described above for different values of M and chose one which gave the best results.

REFERENCES:

For curious of the mind, here are some references that one could look at for understanding all content of this editorial / learning new stuff.

1. Wiki-page about addition chains.
2. l(N) sequence at OEIS. Contains many useful links and tables.
3. Introduction to Addition Chains.
4. Chapter 4 Arithmetic, Section 4.6 Polynomial Arithmetic, Subsection 4.6.4 : evaluation of powers, in Art of Computer Programming, Vol 2 (Seminumerical algorithms), written by Donald Knuth.
5. The paper by Brauer where he present 2^k-ary Method and extremely short addition chains for the numbers of the form 2^N - 1.
6. The method of computing star addition chains based on the continued fractions expansion. Read here.
7. Paper written by Thurber that has a theoretical importance. In this paper, author solved the Scholz-Brauer Problem for m = 3. Namely it was proved that if N has at least 9 unit digits in binary representation then l(N) >= floor(log N) + 4.