Closest harmonic number to an integer

I mentioned harmonic numbers in a previous post h_n There are never integers for n > 1. In the spirit of that post, I would like to know the value of n such that h_n is closest to a given integer m,

We have two problems to solve. First of all, how do we calculate harmonic numbers accurately and efficiently? for small n We can apply the definition directly. for big nThe direct approach will be slow and will accumulate floating point error. But in that case we can use asymptotic approximation

From this post. As is often the case, the direct approach turns out to be worse. n increases, but the asymptotic approximation gets better n Increases. Here γ is the Euler–Mascheroni constant.

The second problem to solve is how to find the value of n So that h_n comes closest to m without trying many possible values ​​of nWe can discard the above higher order terms and see n is roughly exp(m -γ).

Here is the code.

import numpy as np

gamma = 0.57721566490153286

def H(n):
    if n < 1000:
        return sum([1/k for k in range(1, n+1)])
    else:
        n = float(n)
        return np.log(n) + gamma + 1/(2*n) - 1/(12*n**3)
    
# return n such that H_n is closest harmonic number to m
def nearest_harmonic_number(m):
    
    if m == 1:
        return 1

    guess = int(np.exp(m - gamma))    
    if H(guess) < m:
        i = guess
        while H(guess) < m: guess += 1 j = guess else: j = guess while H(guess) > m:
            guess -= 1
        i = guess
        
    x = np.array([abs(H(k) - m) for k in range(i, j+1)])
    return i + np.argmin(x)

For example, we can use it to find the nearest harmonic number to 10.

>>> nearest_harmonic_number(10)
12366
>>> H(12366)
9.99996214846655

I wrote code with integer values m Keeping that in mind, but the code works fine with real numbers. For example, we can find the nearest harmonic number to √20.

>>> nearest_harmonic_number(20**0.5)
49
>>> H(49)**2
20.063280462918804

related posts