Аддитивные цепочки и их обобщения

Какое минимальное число операций умножения достаточно
для возведения $x$ в степень $n$? Или, в аддитивной
постановке, какова минимальная длина $r$ цепочки натуральных
чисел
$$
a_0=1, a_1, a_2, \ldots, a_r=n,
$$
начинающейся с $1$ и заканчивающейся числом $n$, в которой
каждое число $a_i$, $i=1, 2, \ldots, r$, является суммой
двух предыдущих (не обязательно различных)?
Если $n=2^k$, то ответ очевиден: $k$. В общем случае
простейшие оценки этой величины снизу и сверху отличаются вдвое
($\log_2 n$ и $2 \log_2 n$, соответственно). Оказывается,
что эта величина растет как $\log_2 n + \alpha_n$, где
$\lim\limits_{n \to \infty} \frac{\alpha_n}{\log_2 n} = 0$.

Как уточнить эту оценку?

Что можно сказать про минимальное число операций умножения, достаточное для
вычисления по переменным $x_1, x_2, \ldots, x_m$ одночлена
$x_1^{n_1} x_2^{n_2} \ldots x_m^{n_m}$ (задача Ричарда Беллмана)?

Что можно сказать про минимальное число операций умножения, достаточное для
вычисления по переменной $x$ набора степеней
$x^{n_1}, x^{n_2}, \ldots, x^{n_m}$ (задача Дональда Кнута)?

Об этих и близких задачах пойдет речь в курсе.

Предварительных знаний не требуется.