Как посчитать сумму ряда С[n]=1/(a+0)+1/(a+1)+1/(a+2)+...+1/(a+n) за O(1)?

Question

[Сергей П]

Нужно, собственно, посчитать сумму ряда С[n]=1/(a+0)+1/(a+1)+1/(a+2)+...+1/(a+n) за O(1).
Вопрос связан с вот этим вопросом: Как можно заменить способ выбора случайной величины с меньшим потреблением памяти, или есть ли альтернатива random.choises()?
Как альтернативу, можно попробовать решить другую, более полезную задачу:
За O(1) определить min(i) для которого C[i] > X.

Comments

[Griboks]

Могу только дать ссылку преобразования суммы в дигамма-функции.
Можете использовать заранее известные таблицы.
Можете аппроксимировать степенной функцией, откуда найти обратную функцию и вычислить i из X. Самый адекватный вариант.
Поиск i лучше делать не последовательным перебором, а половинным делением.
Добавка на каждом шаге уменьшается, значит, вы можете аппроксимировать 3-4 прямыми.

[Сергей П]

Griboks, в random.choices как раз bisect используется для поиска i. И да, если избавиться от хранения огромного массива для больших N в памяти, то логарифмическая сложность поиска i была бы уже достаточно хорошим решением.

[Griboks]

Сергей Паньков, ок, давайте подумаем.
1. C[n] - это смещённая частичная сумма гармонической прогрессии. Значит C[n] = H[n+a]-H[n]=ln(1+n/a). Отлично, это уже О(1) по количеству базовых операций.
2. Из этого можно найти формулу n=ceil(a*(exp(X)-1)) и обойтись без вероятностей.

Answer 1

[lamerok]

Приближенно можно так: ln(a+n) + 1/((a+n)*2) - ln(a-1) - 1/((a-1)*2), если более точно, ошибку можно уменьшить, посчитав её через числа Бернули.