Énoncé:
La façon la plus naïve de calculer $n^{15}$ nécessite quatorze multiplications :
$\qquad n \times n \times \dots \times n = n^{15}$
Mais en utilisant une méthode "binaire", vous pouvez le calculer en six multiplications :
$\qquad n \times n = n2$
$\qquad n^2 \times n2 = n^4$
$\qquad n^4 \times n4 = n^8$
$\qquad n^8 \times n4 = n^{12}$
$\qquad n^12 \times n2 = n^{14}$
$\qquad n^14 \times n = n^{15}$
Cependant, il est encore possible de le calculer en seulement cinq multiplications :
$\qquad n \times n = n^2$
$\qquad n^2 \times n = n^3$
$\qquad n^3 \times n^3 = n^6$
$\qquad n^6 \times n^6 = n^{12}$
$\qquad n^{12} \times n^3 = n^{15}$
Nous définirons $m(k)$ comme étant le nombre minimal de multiplications pour calculer $n^k$ ; par exemple $m(15) = 5$.
Pour $1 \le k \le 200$, trouve $\sum m(k)$.
Lien du problème originel