101 Optimum Polynomial

如果我们看到一个序列的前 $k$ 项，也不能确定下一项的值，因为有无限多的多项式函数可以模拟这个序列。

比如立方函数产生的序列： $u_n=1,8,27,64,125,216\dots$ 如果只给出前两项，最佳匹配（最简单）是线性函数，那么下一项是 15。如果给出前三项，那么最佳匹配是二次多项式。

我们定义 $OP(k, n)$ 为序列前 $k$ 项的最优多项式函数的第 $n$ 项。如果 $n\leq k$ ，那么能够精确表示序列的第 $n$ 项。潜在的第一个不匹配项 FIT（first incorrect term）是 $OP(k, k+1)$ ，这种情况称为称作 bad OP（BOP）。

如果只给出一项，最明智的选择是常数函数。

因此，对于立方函数的序列来说，OP如下所示： $\begin{aligned} OP(1,n)&=1&&1,1,1,1\dots\\ OP(2,n)&=7n-6&&1,8,15\dots\\ OP(3,n)&=6n^2-11n+6&&1,8,27,58,\dots\\ OP(4,n)&=n^3&&1,8,27,64,125\dots \end{aligned}$ $k\geq 4$ 就没有BOP了。

所有的 FIT 之和是 $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}$ 求所有 BOP 对应的 FIT 之和。

其实题目挺简单的。需要做的就是找出函数的前 11 项，然后用小于十阶的函数取拟合，找到第一个 FIT 求和就可以了。

或许可以编程来完成这个题目，但是还需要解线性方程组求系数。鉴于数值计算的知识都快还给老师了，matlab 也都忘到脑后了；同时工作中不涉及这些，不知道有哪些类库可以用，所以使用 wolframalpha 来解决这个题目。

输入公式 $1 − n + n^2 − n^3 + n^4 − n^5 + n^6 − n^7 + n^8 − n^9 + n^{10}$ 可以得到前几项的值

1	2	3	4	5	6	7	8	9	10	11	12	13	14
1	683	44287	838861	8138021	51828151	247165843	954437177	3138105961	9090909091	23775972551	57154490053	128011456717	269971011311

下面以 $OP(6,n)$ 为例。

输入前 6 项得到一个五阶多项式函数：get 5 degree polynomial for 1, 683, 44287, 838861, 8138021, 51828151 $-14707439 + 34305227 x - 29116967 x^2 + 11535788 x^3 - 2175668 x^4 + 159060 x^5$ 再找到前几项

1	2	3	4	5	6	7
1	683	44287	838861	8138021	51828151	205015603

第一项不同的就是 205015603。

按照同样的做法可以完成其他小于十阶的情况，然后就和即可。

下面是 $k=1\cdots 10$ 的情况。

OP(1,n) = 1
1, 1
1

OP(2,n) = -681 + 682 x
https://www.wolframalpha.com/input/?i2d=true&i=get+1+degree+polynomial+for+1%5C%2844%29+683
1, 683, 1365
1365

OP(3,n) = 42241 - 63701 x + 21461 x^2
https://www.wolframalpha.com/input/?i2d=true&i=get+2+degree+polynomial+for+1%5C%2844%29+683%5C%2844%29+44287
1, 683, 44287, 130813
130813

OP(4,n) = -665807 + 1234387 x - 686587 x^2 + 118008 x^3
https://www.wolframalpha.com/input/?i2d=true&i=get+3+degree+polynomial+for+1%5C%2844%29+683%5C%2844%29+44287%5C%2844%29+838861
n | 1 | 2 | 3 | 4 | 5
118008 n^3 - 686587 n^2 + 1234387 n - 665807 | 1 | 683 | 44287 | 838861 | 3092453
3092453

OP(5,n) = 4379761 - 9277213 x + 6671533 x^2 - 1984312 x^3 + 210232 x^4
https://www.wolframalpha.com/input/?i2d=true&i=get+4+degree+polynomial+for+1%5C%2844%29+683%5C%2844%29+44287%5C%2844%29+838861%5C%2844%29+8138021
n | 210232 n^4 - 1984312 n^3 + 6671533 n^2 - 9277213 n + 4379761
1 | 1
2 | 683
3 | 44287
4 | 838861
5 | 8138021
6 | 32740951
32740951

OP(6,n) = -14707439 + 34305227 x - 29116967 x^2 + 11535788 x^3 - 2175668 x^4 + 159060 x^5
https://www.wolframalpha.com/input/?i2d=true&i=get+5+degree+polynomial+for+1%5C%2844%29+683%5C%2844%29+44287%5C%2844%29+838861%5C%2844%29+8138021%5C%2844%29+51828151

https://www.wolframalpha.com/input/?i2d=true&i=-14707439+%2B+34305227+n+-+29116967+Power%5Bn%2C2%5D+%2B+11535788+Power%5Bn%2C3%5D+-+2175668+Power%5Bn%2C4%5D+%2B+159060+Power%5Bn%2C5%5D

n | 159060 n^5 - 2175668 n^4 + 11535788 n^3 - 29116967 n^2 + 34305227 n - 14707439
1 | 1
2 | 683
3 | 44287
4 | 838861
5 | 8138021
6 | 51828151
7 | 205015603
205015603

OP(7,n) = 27442801 - 68962861 x + 65955241 x^2 - 31492582 x^3 + 8069182 x^4 - 1070322 x^5 + 58542 x^6
https://www.wolframalpha.com/input/?i2d=true&i=get+6+degree+polynomial+for+1%5C%2844%29+683%5C%2844%29+44287%5C%2844%29+838861%5C%2844%29+8138021%5C%2844%29+51828151%5C%2844%29+247165843

n | 58542 n^6 - 1070322 n^5 + 8069182 n^4 - 31492582 n^3 + 65955241 n^2 - 68962861 n + 27442801
1 | 1
2 | 683
3 | 44287
4 | 838861
5 | 8138021
6 | 51828151
7 | 247165843
8 | 898165577
898165577

OP(8,n) = -28828799 + 76941359 x - 80663539 x^2 + 44083303 x^3 - 13814218 x^4 + 2524808 x^5 - 254078 x^6 + 11165 x^7
https://www.wolframalpha.com/input/?i2d=true&i=get+7+degree+polynomial+for+1%5C%2844%29+683%5C%2844%29+44287%5C%2844%29+838861%5C%2844%29+8138021%5C%2844%29+51828151%5C%2844%29+247165843%5C%2844%29+954437177

n | 11165 n^7 - 254078 n^6 + 2524808 n^5 - 13814218 n^4 + 44083303 n^3 - 80663539 n^2 + 76941359 n - 28828799
1 | 1
2 | 683
3 | 44287
4 | 838861
5 | 8138021
6 | 51828151
7 | 247165843
8 | 954437177
9 | 3093310441
3093310441

OP(9,n) = 15966721 - 44806465 x + 50572225 x^2 - 30669221 x^3 + 11126621 x^4 - 2514688 x^5 + 352528 x^6 - 28831 x^7 + 1111 x^8
https://www.wolframalpha.com/input/?i2d=true&i=get+8+degree+polynomial+for+1%5C%2844%29+683%5C%2844%29+44287%5C%2844%29+838861%5C%2844%29+8138021%5C%2844%29+51828151%5C%2844%29+247165843%5C%2844%29+954437177%5C%2844%29+3138105961

n | 1111 n^8 - 28831 n^7 + 352528 n^6 - 2514688 n^5 + 11126621 n^4 - 30669221 n^3 + 50572225 n^2 - 44806465 n + 15966721
1 | 1
2 | 683
3 | 44287
4 | 838861
5 | 8138021
6 | 51828151
7 | 247165843
8 | 954437177
9 | 3138105961
10 | 9071313571
9071313571

OP(10,n) = -3628799 + 10628639 x - 12753575 x^2 + 8409499 x^3 - 3416929 x^4 + 902054 x^5 - 157772 x^6 + 18149 x^7 - 1319 x^8 + 54 x^9
https://www.wolframalpha.com/input/?i2d=true&i=get+9+degree+polynomial+for+1%5C%2844%29+683%5C%2844%29+44287%5C%2844%29+838861%5C%2844%29+8138021%5C%2844%29+51828151%5C%2844%29+247165843%5C%2844%29+954437177%5C%2844%29+3138105961%5C%2844%29+9090909091

n | 54 n^9 - 1319 n^8 + 18149 n^7 - 157772 n^6 + 902054 n^5 - 3416929 n^4 + 8409499 n^3 - 12753575 n^2 + 10628639 n - 3628799
1 | 1
2 | 683
3 | 44287
4 | 838861
5 | 8138021
6 | 51828151
7 | 247165843
8 | 954437177
9 | 3138105961
10 | 9090909091
11 | 23772343751
23772343751

$23772343751+9071313571+3093310441+898165577+205015603+32740951+3092453+130813+1365+1$