Finding how many terms of the harmonic series must be summed to exceed x?

The DiGamma function (the derivative of the logarithm of the Gamma function) is directly related to the harmonic numbers: ψ(n) = Hn-1 - γ, where γ is Euler's constant (0.577...).

You can use one of the approximations in the Wikipedia article to compute an approximate value for Hn, and then use that in a standard root finding algorithm like bisection to locate the solution.


If you replace the sum by an integral you get the logarithm function so that $\ln(n)$ is a first approximation.

In fact the Euler $\gamma$ constant ($.577215664901532860606512090$) may be defined by the following formula : $\displaystyle \gamma=\lim_{n \to \infty} \left(H_n-\ln(n+1/2)\right)$

From this you may deduce the equivalence as $n \to \infty$ : $$H_n \thicksim \gamma + \ln(n+1/2) $$
(for $n=10^6$ we get about 14 digits of precision)

And revert this (David Schwartz proposed a similar idea) to get the value $n$ required to get a sum $s$ : $$n(s) \approx e^{s-\gamma} -\frac12$$

The first integer to cross the $s$ should be given by $\lfloor e^{s-\gamma}+\frac12\rfloor\;$ ('should be' because of the little error made on $H_n$ compensated by the low probability of people testing values much higher than 20 :-)).

Example : the sum will cross the value $20$ for $n$ evaluated at $\rm floor(\rm exp(20-gamma)+0.5)= \rm round(\rm exp(20-gamma))= 272400600$ and indeed (this is not a proof!) :
$H_{272400599}=19.9999999977123$
$H_{272400600}=20.0000000013833$


See also http://oeis.org/A002387 and references there.