Как наиболее эффективно найти первый элемент в i-й строке, когда A[i,j]=j*(A[i-1,j+1]-A[i-1,j])?

Question

Когда первая строка 1, 1/2, 1/3 .... Вот изображение, чтобы поддержать вопрос.

Существует ли более эффективный подход, чем наивный подход O(n^2)?

Я столкнулся с этим при изучении чисел Бернулли и, следовательно, при достижении "алгоритма Акияма – Танигава".

Одним из способов может быть простое предварительное вычисление результатов и сохранение их в таблице. Поскольку числа Бернулли растут очень быстро, для большинства практических целей нам не понадобятся числа Бернулли для гораздо большего n. Рассмотрим Бернулли (400)- его вокруг -(10^550).

Но если смотреть на это только алгоритмически, есть ли лучший подход, чем O(n^2)?

Answer 1

Первые элементы образуют последовательность чисел Бернулли. Числители и знаменатели для чисел Бернулли находятся с использованием последовательности A027641 и последовательности A027642 соответственно. Обе эти последовательности имеют суммы в замкнутой форме на соответствующих страницах, которые можно использовать для вычисления их терминов.