寻找整数序列的闭合形式函数的一些算法是什么？

Question

寻找整数序列的闭合形式函数的一些算法是什么？

algorithmlanguage-agnosticmath

6

我正在寻找一种编程方法，可以将整数序列转换为闭合形式函数。就像这样：

给定：1、3、6、10、15

返回：n(n+1)/2

示例可能很有用；语言不重要。

- wkf

可能只是缺乏数学知识，但这个问题似乎不够有界。 - Brian

建议边界：如果可能的话，找到一个封闭形式函数，给出确切的10个整数，否则返回null。不幸的是，这样的东西过于简单化了这个问题，以至于它几乎变得毫无价值。 - Sev

1

我的主要担忧是我过于考虑这个问题，而且可能有一些众所周知的方法来解决它。结果证明并非如此，事实上，我需要比已经投入的更多的思考。 - wkf

7个回答

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$
这只是一个线性方程组。

- ephemient

你给出了一个算法示例，而“正确”的答案声称不存在这样的算法。有趣。你的答案假设序列是有限的，我认为这是正确的假设。 - Martin Hock

1

@Martin：ephemient 明确指出，解决方案状态限制为 n 次多项式，这些多项式始终可以适合于有限的 n 个点。 - Autoplectic

1

小修正：一个n次多项式总是可以拟合到一个有限的n+1个点的集合。 - ephemient

+1. 在我看来，这应该是正确的答案。最重要的一点是，这个问题缺乏约束力，而你给出的1、3、6、10、15五个不同可信函数的列表很好地证明了这一点。 - j_random_hacker

3

如果你的数据可以表示为一个多项式，我认为你可以使用R（或任何提供数据回归拟合的套件）。如果你的相关性恰好为1，则该线条是一个完美的拟合来描述该系列。

回归分析涉及到很多统计学知识，我对计算的基础知识都不太熟悉，无法给你提供更多详细信息。

但是，这个链接可能会对在R中进行回归分析有所帮助。

- Mark Rushakoff

你可以通过取所有给定的根，比如a、b和c，将其写成f(x)=(x-a)(x-b)(x-c)的形式来形成多项式。但这并不意味着没有其他满足条件的多项式。 - Bill Lynch

2

Axiom计算机代数系统包括一个专门用于此目的的软件包。您可以在这里阅读其文档。

以下是您的示例序列在FriCAS（Axiom的一个分支）中的输出：

(3) -> guess([1, 3, 6, 10, 15])

                 2
                n  + 3n + 2
(3)  [[function= -----------,order= 0]]
                     2
Type: List(Record(function: Expression(Integer),order: NonNegativeInteger))

- jmbr

1

没有通用的答案；可以通过使用Pade逼近来实施一个简单的方法；简而言之，假设你的序列是一个未知函数的Taylor展开系数序列，然后应用一个算法（类似于连分数算法）来“简化”这个Taylor展开式（更准确地说：找到一个非常接近初始（并截断的）函数的有理函数）。Maxima程序可以做到这一点：看看页面上的“pade”：http://maxima.sourceforge.net/docs/manual/maxima_28.html 另一个答案提到了Axiom的FriCAS分支中的“guess”包（请参阅jmbr的先前答案）。如果我没有错的话；这个包本身受到Christian Krattenthaler的Rate程序的启发；你可以在这里找到它：http://www.mat.univie.ac.at/~kratt/rate/rate.html也许查看它的源代码可以告诉你其他方法。

- Thomas Baruchel

1

我认为你的问题是不适当的。如果没有生成函数，给定任意有限数量的整数序列，下一个元素可以是任何东西。

你需要对这个序列做出一些假设。它是否是等比的？还是等差的？

- SplittingField

各种序列。也许有一个“序列”，但没有生成函数。我希望能够处理这种情况。我现在处于起点，如果您认为我应该重新构思问题的方式，请提供您的意见。 - wkf

1

如果您的序列来自于一个多项式，那么差商将会找到该多项式在牛顿基或二项式基下的表达式。请参见this。

- lhf

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jason · Accepted Answer

这涉及到数学中一个非常深奥、复杂而且活跃的领域。对于某些情况，解决方案几乎是微不足道的（比如线性递归），而对于其他情况则几乎是不可能的（例如2、3、5、7、11、13……）。你可以从查看生成函数等方面入手，查看Herb Wilf的令人难以置信的书籍（参见该主题的第1页（2e）），但这只能帮助你走得更远一些。

但我认为你最好放弃，需要了解答案时查询Sloane's全面整数序列百科全书，并花时间阅读这个深奥学科中最古怪的个性之一的观点。

任何告诉你这个问题是可解的人都是在向你兜售蛇油（请参见Wilf书（2e）的第118页）。