TAOCP 4.6.3 Exercise 21

**Solution to Exercise 4.

taocpmathematicsalgorithmsvolume-2math-hard

Section 4.6.3: Evaluation of Powers

Exercise 21. ▶ [M26] (W. Hansen.) Let $q$ be any positive integer. Find a value of $n$ such that $l(n) \le l^F(n) - q$.

Verified: yes
Solve time: 6m23s

Solution to Exercise 4.6.3.21 [M26]

We wish to show that, for any positive integer $q$, there exists an integer $n$ such that

$$ l(n) \le l^F(n) - q, $$

where $l(n)$ is the length of a minimal addition chain for $n$, and $l^F(n)$ is the number of multiplications used by the factor method minus one.

Step 1. Factor method

Let $F(n) = l^F(n) + 1$ denote the number of multiplications used by the factor method for $n$. Then $F$ satisfies

$$ F(1) = 0, $$

and for $n>1$,

$$ F(n) = \begin{cases} F(p) + F(q), & n = pq,\ p,q > 1,\[1mm] n, & n \text{ prime}. \end{cases} $$

Equivalently,

$$ l^F(1) = -1,\qquad l^F(n) = \begin{cases} l^F(p) + l^F(q) + 1,& n = pq,\ p,q>1,\[1mm] n - 1,& n \text{ prime}. \end{cases} $$

The factor method is completely multiplicative on composite numbers.

Step 2. Construction of $n$

Let $q$ be given. We first handle the cases $q \ge 3$.

Choose $n$ to be the product of the first $q$ primes:

$$ n = \prod_{i=1}^{q} p_i, $$

where $p_1 = 2, p_2 = 3, p_3 = 5, \dots, p_q$ is the $q$-th prime.

Then, by complete multiplicativity of $F$ on composite numbers,

$$ F(n) = \sum_{i=1}^{q} F(p_i) = \sum_{i=1}^{q} p_i, $$

so

$$ l^F(n) = \sum_{i=1}^{q} p_i - 1. $$

Step 3. Constructing an ordinary addition chain

We construct an addition chain for $n$ as follows:

  1. Reach the largest prime $p_q$.

Begin with $1$ and construct each prime successively by repeated addition:

$$ 1 \rightsquigarrow 2 \rightsquigarrow 3 \rightsquigarrow 5 \rightsquigarrow \cdots \rightsquigarrow p_q. $$

Reaching $p_q$ requires at most $p_q - 1$ steps. This is an upper bound and suffices for our purpose. 2. Multiply the primes sequentially.

After obtaining the primes, form their product sequentially:

$$ p_1, \quad p_1 p_2, \quad p_1 p_2 p_3, \dots, \prod_{i=1}^{q} p_i = n. $$

This requires $q-1$ additional multiplications.

Hence, we obtain the estimate

$$ l(n) \le (p_q - 1) + (q - 1) = p_q + q - 2. $$

Step 4. Compare $l^F(n)$ and $l(n)$

We have

$$ l^F(n) - l(n) \ge \left(\sum_{i=1}^{q} p_i - 1\right) - (p_q + q - 2) = \sum_{i=1}^{q-1} p_i - q + 1. $$

Using the bound $p_i \ge i+1$ for the first $q-1$ primes, we get

$$ \sum_{i=1}^{q-1} p_i \ge \sum_{i=1}^{q-1} (i+1) = \frac{(q-1)q}{2} + (q-1) = \frac{q(q+1)}{2} - 1. $$

Thus,

$$ l^F(n) - l(n) \ge \frac{q(q+1)}{2} - q - 1 + 1 = \frac{q(q-1)}{2}. $$

For $q \ge 4$, we have $\frac{q(q-1)}{2} \ge q$, so

$$ l(n) \le l^F(n) - q. $$

Step 5. Small cases

  • Case $q=1$: Take $n = 15 = 3 \cdot 5$. Then

$$ l^F(15) = (3 + 5) - 1 = 7,\qquad l(15) = 5 \le 7 - 1. $$

  • Case $q=2$: Take $n = 105 = 3 \cdot 5 \cdot 7$. Then

$$ l^F(105) = (3+5+7) - 1 = 14,\qquad l(105) \le 10 \implies l^F(105)-l(105) \ge 4 > 2. $$

  • Case $q=3$: Take $n = 30 = 2 \cdot 3 \cdot 5$. Then

$$ l^F(30) = (2+3+5) - 1 = 9,\qquad l(30) = 5 \implies l^F(30) - l(30) = 4 > 3. $$

Thus all small cases are explicitly covered.

Step 6. Conclusion

For any positive integer $q$, we have constructed an integer $n$ such that

$$ \boxed{l(n) \le l^F(n) - q}. $$

∎

This argument fixes the previous error for $q=3$ and clarifies that the addition chain bound is an existence argument rather than an exact minimal chain.