yaworsw/euler-manager

---
:id: 122
:name: Efficient exponentiation
:url: https://projecteuler.net/problem=122
:content: "The most naive way of computing _n_<sup>15</sup> requires fourteen multiplications:\n\n_n_
  × _n_ × ... × _n_ = _n_<sup>15</sup>\n\nBut using a \"binary\" method you can compute
  it in six multiplications:\n\n_n_ × _n_ = _n_<sup>2</sup>  \n_n_<sup>2</sup> × _n_<sup>2</sup>
  = _n_<sup>4</sup>  \n_n_<sup>4</sup> × _n_<sup>4</sup> = _n_<sup>8</sup>  \n_n_<sup>8</sup>
  × _n_<sup>4</sup> = _n_<sup>12</sup>  \n_n_<sup>12</sup> × _n_<sup>2</sup> = _n_<sup>14</sup>
  \ \n_n_<sup>14</sup> × _n_ = _n_<sup>15</sup>\n\nHowever it is yet possible to compute
  it in only five multiplications:\n\n_n_ × _n_ = _n_<sup>2</sup>  \n_n_<sup>2</sup>
  × _n_ = _n_<sup>3</sup>  \n_n_<sup>3</sup> × _n_<sup>3</sup> = _n_<sup>6</sup>  \n_n_<sup>6</sup>
  × _n_<sup>6</sup> = _n_<sup>12</sup>  \n_n_<sup>12</sup> × _n_<sup>3</sup> = _n_<sup>15</sup>\n\nWe
  shall define m(_k_) to be the minimum number of multiplications to compute _n_<sup><i>k</i></sup>;
  for example m(15) = 5.\n\nFor 1 ≤ _k_ ≤ 200, find ∑ m(_k_).\n\n"