0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Sangchul Lee Dec 30 '18 at 11:00
2
$\begingroup$

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)$$

$\endgroup$
  • $\begingroup$ Nuce work. Minor typo: oder -> order. $\endgroup$ – marty cohen Dec 30 '18 at 14:20
  • $\begingroup$ @martycohen. Thanks ! In fact, if you go to the edits, you would notice major differences and improvements. By the way, about typo's, what means nuce ? Happy New Year ! $\endgroup$ – Claude Leibovici Dec 30 '18 at 14:23
  • $\begingroup$ It means that I sometimes don't proofread well. $\endgroup$ – marty cohen Dec 30 '18 at 21:14
  • $\begingroup$ @ClaudeLeibovici, this is amazing, thank you! $\endgroup$ – Elisha Dec 31 '18 at 4:39
  • $\begingroup$ @Elisha. You are very welcome ! I had fun with it ! $\endgroup$ – Claude Leibovici Dec 31 '18 at 4:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.