algorithm - What is the most efficient way of finding the first element of the ith row when A[i,j]=j*(A[i-1,j+1]-A[i-1,j])?

Question

When the first row is 1, 1/2 , 1/3 .... Here's an image to support the question.

Does there exist a more efficient approach than the naive O(n^2) approach?

I came across this when studying Bernoulli numbers and then consequently on reaching "Akiyama–Tanigawa algorithm".

One of the ways could be simple precomputing the results and storing them in a table. Since Bernoulli numbers grow very quickly, for most practical purposes we wouldn't need Bernoulli numbers for much larger n. Consider Bernoulli(400)- its around -(10^550).

But looking at it only algorithmically, is there a better approach than the O(n^2) one?

Answer 1

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