Problem 101

Optimum polynomial

If we are presented with the first $k$ 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.

As an example, let us consider the sequence of cube numbers. This is defined by the generating function,

$$u_n = n^3: 1, 8, 27, 64, 125, 216, \ldots$$

Suppose 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.

We shall define $\text{OP}(k, n)$ to be the $n$^th term of the optimum polynomial generating function for the first $k$ terms of a sequence. It should be clear that $\text{OP}(k, n)$ will accurately generate the terms of the sequence for $n \le k$, and potentially the first incorrect term (FIT) will be $\text{OP}(k, k+1)$; in which case we shall call it a bad OP (BOP).

As a basis, if we were only given the first term of sequence, it would be most sensible to assume constancy; that is, for $n \ge 2$, $\text{OP}(1, n) = u_1$.

Hence we obtain the following OPs for the cubic sequence:

$$\begin{aligned}
&\text{OP}(1,n)=1 &&1, \mathbf{\color{red}1}, 1, 1, \ldots\\
&\text{OP}(2,n)=7n-6 &&1, 8, \mathbf{\color{red}15}, \ldots\\
&\text{OP}(3,n)=6n^2-11n+6 &&1, 8, 27,\mathbf{\color{red}58}, \ldots\\
&\text{OP}(4,n)=n^3 &&1, 8, 27, 64, 125, \ldots
\end{aligned}$$

Clearly no BOPs exist for $k \ge 4$.

By considering the sum of FITs generated by the BOPs (indicated in ${\color{red}\textbf{red}}$ above), we obtain $1 + 15 + 58 = 74$.

Consider the following tenth degree polynomial generating function:

$$u_n = 1-n+n^2-n^3+n^4-n^5+n^6-n^7+n^8-n^9+n^{10}$$

Find the sum of FITs for the BOPs.

最优多项式

给定一个数列的前$k$项，我们并不能确定其下一项的值，因为描述这个数列已知项的多项式生成函数有无数种可能。

例如，考虑如下的立方数数列：

$$u_n = n^3: 1, 8, 27, 64, 125, 216, \ldots$$

如果我们只知道数列的前两项，根据“简单优先”的原则，我们应当猜测数列由某个一次函数生成（也即数列为等差数列），其下一项为$15$（公差为$7$）。如果我们只知道数列的前三项，根据同样的原则，我们应当猜测数列由某个二次函数生成。

类似地，给定数列的前$k$项，我们可以猜测数列由某个最优多项式函数生成，并定义$\text{OP}(k, n)$是由这个函数给出的第$n$项的值。显然，若$n\le k$，$\text{OP}(k, n)$可以准确地给出这些已知项的值，而第一个不正确项最早可能出现在$\text{OP}(k, k+1)$，此时称这个最优多项式为坏最优多项式。

特别地，如果我们只知道数列的第一项，我们应当猜测数列为常数，也就是说，对于$n \ge 2$，$\text{OP}(1, n) = u_1$。

对于立方数数列，给定不同项数时的最优多项式如下所示：

显然，当$k \ge 4$时，不会有坏最优多项式。

所有坏最优多项式的第一个不正确项（用${\color{red}\textbf{红色}}$标示的数）之和为$1 + 15 + 58 = 74$。

考虑下面这个十阶多项式函数生成的数列：

$$u_n = 1-n+n^2-n^3+n^4-n^5+n^6-n^7+n^8-n^9+n^{10}$$

求其所有坏最优多项式的第一个不正确项之和。