在给定整数序列的情况下,有哪些算法可以找到闭合函数？

Question

在给定整数序列的情况下,有哪些算法可以找到闭合函数？

wkf*_*wkf 6 language-agnostic algorithm math

我正在寻找采用整数序列并吐出封闭形式函数的编程方式.就像是:

鉴于:1,3,6,10,15

返回:n(n + 1)/ 2

样品可能有用; 语言不重要.

Answer 1

jas*_*son 17

这触及了极其深刻,复杂和活跃的数学领域.在某些情况下,解决方案几乎是微不足道的(线性复发),而在其他情况下该死的几乎不可能(想想2,3,5,7,11,13 ......)你可以从生成函数开始,例如看在Herb Wilf 关于这个主题的令人难以置信的书(参见第1页(2e)),但这只会让你到目前为止.

但我认为你最好的选择是放弃,在你需要知道答案时查询Sloane全面的整数序列百科全书,而是花时间阅读这个深层主题中最古怪的人物之一的观点.

任何告诉你这个问题的人都可以卖给你卖蛇油(参见Wilf书(第21页)第118页.)

您可能还想看一下"混凝土数学"一书.你可能会发现它比Wilf的书更容易理解. (4认同)

Answer 2

eph*_*ent 10

一般来说没有一个功能.

对于您指定的序列,整数序列的在线百科全书在其有趣的整数序列的数据库中找到133个匹配项.我在这里复制了前5个.

A000217三角数:a(n)= C(n + 1,2)= n(n + 1)/ 2 = 0 + 1 + 2 + ... + n.
0,1,3,6,10,15,21,28,36,45,55,66,78,91,105,120,136,153,171,190,210,231,253,276,300, 325,351,378,406,435,465,496,528,561,595,630,666,703,741,780,820,861,903,946,990,1035,1081,1128,1176,1225, 1275,1326,1378,1431

A130484求和{0 <= k <= n,k mod 6}(A010875的部分和).
0,1,3,6,10,15,15,16,18,21,25,30,30,31,33,36,40,45,45,46,48,51,55,60,60, 61,63,66,70,75,75,76,78,81,85,90,90,91,93,96,100,105,105,106,108,111,115,120,120,121, 123,126,130,135,135,136,138,141,145,150,150,151,153

A130485求和{0 <= k <= n,k mod 7}(A010876的部分和).
0,1,3,6,10,15,21,21,22,24,27,31,36,42,42,43,45,48,52,57,63,63,64,66,69, 73,78,84,84,85,87,90,94,99,105,105,106,108,111,115,120,126,126,127,129,132,136,141,147,147, 148,150,153,157,162,168,168,169,171,174,178,183

A104619将基数为16的自然数写入第k行中k个数字的三角形中,如下所示.序列给出了前导对角线.
1,3,6,10,15,2,1,1,14,3,2,2,5,12,4,4,4,13,6,7,11,6,9,9,10, 7,12,13,1,0,1,10,5,1,12,8,1,1,14,1,9,7,1,4,3,1,2,2,1,3, 4,2,7,9,2,14,1,2,8,12,2,5,10,3,5,11,3,8,15,3,14,6,3,7,0, 4,3,13,4,2,13,4,4,0,5,9,6,5,1,15,5,12,11,6

A037123 a(n)= a(n-1)+ n的位数之和.
0,1,3,6,10,15,21,28,36,45,46,48,51,55,60,66,73,81,90,100,102,105,109,114,120, 127,135,144,154,165,168,172,177,183,190,198,207,217,228,240,244,249,255,262,270,279,289,300,312,325, 330,336,343,351,360,370,381

如果你将自己限制在多项式函数中,这很容易编码,只需要手工解决就有点繁琐.

让 $F(X)= + A_0 + a_1x ^ a_2x 2个+\cdots + A_ {N-1}的x ^ {N-1} + a_nx ^ N$ ,对于一些未知的 $a_0\ldots a_n$

现在解决方程式
$y_0=f(0)=a_0$
$Y_1 = F(1)= + A_0 A_1 + A_2 +\cdots + A_ {N-1} + A_N$
$Y_2 = F(2)= A_0 + 2A_1 + 4a_2 +\cdots + 2 ^ {N - 1} {A_ N-1} + 2 ^ na_n$
...
$y_n = F(N)= + A_0 na_1 + N ^ 2a_2 +\cdots + N ^ {N-1} {A_ N-1} + N ^ na_n$
这只是一个线性方程组.

归档时间：	16 年，4 月前
查看次数：	3876 次
最近记录：	9 年，12 月前