yaworsw/euler-manager

---
:id: 101
:name: Optimum polynomial
:url: https://projecteuler.net/problem=101
:content: "If we are presented with the first <var>k</var> terms of a sequence it
  is impossible to say with certainty the value of the next term, as there are infinitely
  many polynomial functions that can model the sequence.\n\nAs an example, let us
  consider the sequence of cube numbers. This is defined by the generating function,
  \  \n<var>u</var><sub><var>n</var></sub> = <var>n</var><sup>3</sup>: 1, 8, 27, 64,
  125, 216, ...\n\nSuppose we were only given the first two terms of this sequence.
  Working on the principle that \"simple is best\" we should assume a linear relationship
  and predict the next term to be 15 (common difference 7). Even if we were presented
  with the first three terms, by the same principle of simplicity, a quadratic relationship
  should be assumed.\n\nWe shall define OP(<var>k</var>, <var>n</var>) to be the <var>n</var><sup>th</sup>
  term of the optimum polynomial generating function for the first <var>k</var> terms
  of a sequence. It should be clear that OP(<var>k</var>, <var>n</var>) will accurately
  generate the terms of the sequence for <var>n</var> ≤ <var>k</var>, and potentially
  the _first incorrect term_ (FIT) will be OP(<var>k</var>, <var>k</var>+1); in which
  case we shall call it a _bad OP_ (BOP).\n\nAs a basis, if we were only given the
  first term of sequence, it would be most sensible to assume constancy; that is,
  for <var>n</var> ≥ 2, OP(1, <var>n</var>) = <var>u</var><sub>1</sub>.\n\nHence we
  obtain the following OPs for the cubic sequence:\n\n| OP(1, <var>n</var>) = 1 |
  1, **1** , 1, 1, ... |\n| OP(2, <var>n</var>) = 7<var>n</var>−6 | 1, 8, **15** ,
  ... |\n| OP(3, <var>n</var>) = 6<var>n</var><sup>2</sup>−11<var>n</var>+6&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
  | 1, 8, 27, **58** , ... |\n| OP(4, <var>n</var>) = <var>n</var><sup>3</sup> | 1,
  8, 27, 64, 125, ... |\n\nClearly no BOPs exist for <var>k</var> ≥ 4.\n\nBy considering
  the sum of FITs generated by the BOPs (indicated in **red** above), we obtain 1
  + 15 + 58 = 74.\n\nConsider the following tenth degree polynomial generating function:\n\n<var>u</var><sub><var>n</var></sub>
  = 1 − <var>n</var> + <var>n</var><sup>2</sup> − <var>n</var><sup>3</sup> + <var>n</var><sup>4</sup>
  − <var>n</var><sup>5</sup> + <var>n</var><sup>6</sup> − <var>n</var><sup>7</sup>
  + <var>n</var><sup>8</sup> − <var>n</var><sup>9</sup> + <var>n</var><sup>10</sup>\n\nFind
  the sum of FITs for the BOPs.\n\n"