algorithm - 当 A[i,j]=j*(A[i-1,j+1]-A[i-1,j]) 时，找到第 i 行第一个元素的最有效方法是什么？

Question

当第一行是 1, 1/2 , 1/3 ....这是支持该问题的图像。

是否存在比朴素的 O(n^2) 方法更有效的方法？

我在研究伯努利数时遇到了这个问题，然后在研究“Akiyama-Tanigawa 算法”时遇到了这个问题。

其中一种方法可能是简单地预先计算结果并将它们存储在表中。由于伯努利数增长非常快，对于大多数实际用途，我们不需要伯努利数来获得更大的 n。考虑 Bernoulli(400) - 它大约是 -(10^550)。

但仅从算法上看，是否有比 O(n^2) 更好的方法？

Answer 1

第一个元素构成 Bernoulli numbers 的序列.使用 A027641 找到伯努利数的分子和分母。序列和A027642序列，分别。这两个序列在​​各自的页面上都有封闭形式的总和，可用于计算它们的项。