0

I am trying to find an equilibrium point of two algorithms, parametrized by $k$. The performance of the two algorithms:

  • $\frac{c}{k+1}$ (where $c$ is some given positive constant)
  • $H_k$ (the $k$-th harmonic number)

I am looking for a value $k$ such that $H_k=\frac{c}{k+1}$. I was able find a relatively close approximation using product-log (Lambert W function). Set $k=e^{W(c)}-1$. This yields (using $e^{W(x)}=\frac{x}{W(x)}$):

  • $\frac{c}{k+1}=\frac{c}{e^{W(c)}-1+1}=\frac{c}{e^{W(c)}}=\frac{c}{\frac{c}{W(c)}}=W(c)$
  • $H_k=H_{e^{W(c)}-1}\approx\ln(e^{W(c)}-1)+ 1\approx W(c) + 1$

I wonder if there is a way to reach an exact solution, or, to have a solution that minimizes the difference between the two expressions.

Elisha
  • 103
  • It is hard to believe that there is a closed-form solution using well-known special functions, but at least we can tell that $k \approx c/\log c$ as $c\to\infty$. – Sangchul Lee Dec 30 '18 at 11:00

1 Answers1

2

Let us make to problem more general considering the equation to be $$H_k=\frac c {k+a}$$ First, in order to limit the expansions to a single term, let $n=k+a$ making the equation $$H_{n-a}=\frac c {n}$$ Assuming that $n$ is large, using $$H_{n-a}=\gamma +\log \left({n}\right)+\frac{1-2a}{2n}+O\left(\frac{1}{n^2} \right)$$ and ignoring the higher order terms, we end with the equation $$\gamma +\log \left({n}\right)+\frac{1-2a}{2n}=\frac c {n}$$ the solution of which being $$n=\frac{2 a+2 c-1}{2 W\left(\frac{1}{2} (2 a+2 c-1)e^{\gamma } \right)}\implies \color{red}{k=\frac{2 a+2 c-1}{2 W\left(\frac{1}{2} (2 a+2 c-1)e^{\gamma } \right)}-a} \tag 1$$

As shown below for the case where $a=1$, the approximation is quite good even for small values of $c$.

$$\left( \begin{array}{ccc} c & (1) & \text{exact} \\ 1 & 0.51307 & 0.53917 \\ 2 & 0.98203 & 1.00000 \\ 3 & 1.40552 & 1.41932 \\ 4 & 1.80033 & 1.81156 \\ 5 & 2.17472 & 2.18420 \\ 10 & 3.86345 & 3.86884 \\ 15 & 5.37830 & 5.38209 \\ 20 & 6.79327 & 6.79621 \\ 25 & 8.14014 & 8.14254 \\ 30 & 9.43626 & 9.43830 \\ 35 & 10.6924 & 10.6942 \\ 40 & 11.9159 & 11.9174 \\ 45 & 13.1119 & 13.1133 \\ 50 & 14.2843 & 14.2856 \\ 55 & 15.4362 & 15.4373 \\ 60 & 16.5698 & 16.5709 \\ 65 & 17.6873 & 17.6883 \\ 70 & 18.7901 & 18.7910 \\ 75 & 19.8795 & 19.8804 \\ 80 & 20.9568 & 20.9576 \\ 85 & 22.0228 & 22.0236 \\ 90 & 23.0785 & 23.0793 \\ 95 & 24.1246 & 24.1253 \\ 100 & 25.1616 & 25.1623 \end{array} \right)$$

Claude Leibovici
  • 260,315