TAOCP 4.6.3 Exercise 4
Consider the binary and octal ($m = 8$) methods for evaluating $x^n$.
Section 4.6.3: Evaluation of Powers
Exercise 4. [**] [M20] Find a number $n$ for which the octal ($2^3$-ary) method gives ten fewer multiplications than the binary method.
Verified: yes
Solve time: 1m38s
Consider the binary and octal ($m = 8$) methods for evaluating $x^n$. The number of multiplications required by the left-to-right $m$-ary method is
$t + \sum_{j=0}^t (d_j \neq 0)$
where $n = d_t m^t + \cdots + d_0$ is the base-$m$ expansion and $d_j \neq 0$ counts the nonzero digits. For the binary method ($m = 2$), the number of multiplications is $\lfloor \lg n \rfloor + \nu(n)$, where $\nu(n)$ counts ones in the binary representation of $n$.
We seek $n$ such that the octal method reduces the multiplication count by ten relative to binary. Let us examine powers of two slightly less than a power of eight, because in such cases the octal representation has many zeros while the binary representation has mostly ones. One minimal solution arises at $n = 2^9 - 1 = 511$. Then $\nu(n) = 9$ and $\lfloor \lg 511 \rfloor = 8$, so the binary method requires $8 + 9 = 17$ multiplications. The octal expansion of $511$ is $7\ 7\ 7$ in base 8, so $t = 2$ and all digits are nonzero, giving $2 + 3 = 5$ multiplications. The difference is exactly $17 - 5 = 12$, which exceeds ten. Adjusting slightly to $n = 2^8 - 1 = 255$, we have $\lfloor \lg 255 \rfloor = 7$, $\nu(255) = 8$, so the binary method requires $15$ multiplications. In octal, $255 = 3\ 7\ 7$ (base 8), so $t = 2$ and two nonzero digits beyond the leading $3$ yield $2 + 3 = 5$ multiplications. The difference is $15 - 5 = 10$. Therefore $n = 255$ satisfies the condition.
The octal method requires ten fewer multiplications than the binary method when $n = 255$. $\boxed{255}$