2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Как быстро вычислить целую часть гармонического числа [H_n]?
Сообщение14.04.2013, 19:57 
Как быстро вычислить $[H_n]=\left[1+\frac{1}{2}+\ldots+\frac{1}{n}\right]$? Т.е. можно ли быстрее, чем подсчет по определению за $O(n\ln n)$? По идее, формула суммирования Эйлера-Маклорена нам помочь не может, поскольку ряд лишь обертывающий, т.е. у нее остаточный член $O(n^{-2m})$, а знаменатель растет как $\exp(\psi(n))$, у которой старший член - экспонента.
Чего-то вот нагуглил, но не сильно помогло.
Или я туплю?

 
 
 
 Re: Как быстро вычислить целую часть гармонического числа [H_n]?
Сообщение14.04.2013, 20:13 
Аватара пользователя
А в "вилку" двумя интегралами не выйдет?

 
 
 
 Re: Как быстро вычислить целую часть гармонического числа [H_n]?
Сообщение14.04.2013, 20:17 
Евгений Машеров в сообщении #710172 писал(а):
А в "вилку" двумя интегралами не выйдет?
Так?:
$\int\limits_1^{n}\frac{dx}{x}<H_n<\int\limits_2^{n+1}\frac{dx}{x}$
Если да, то я ж говорю, что формула Эйлера-Маклорена, видимо, ничего не дает:
$$H_n = \ln n + \gamma +\frac{1}{2n}+\sum\limits_{k=1}^m \frac{B_{2k}}{2kn^{2k}}-\theta _{m,n}\frac{B_{2m+2}}{(2m+2)n^{2m+2}}$$
Т.е., конечно, если вычислить $H_n$ по этой формуле, оценить погрешность и полученный интервал явно не накрывает ни одну целую точку, то тогда $[H_n]$ мы знаем, и так будет почти всегда. А если интервал накрывает целую точку? Точное значение мы вычислить так не можем, потому что соответствующий ряд только обертывающий (расходится).

 
 
 
 Re: Как быстро вычислить целую часть гармонического числа [H_n]?
Сообщение15.04.2013, 07:53 
Аватара пользователя
Если бы это была прикладная задача - искал бы оценку через интегралы, проверял бы, нет ли целой точки в вилке и тогда считал бы суммированием, но это приходилось бы делать редко.

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group