Solving an equation involving floor/ceiling as a summation bound

688 Views Asked by At

Is it possible to solve the following equation for $\alpha$?

$$ M = \lfloor \alpha \rfloor + \alpha \sum_{k=\lfloor \alpha \rfloor +1}^N \frac{1}{k}$$

where $\alpha \geq 1$.

Intuitively, $M$ is a harmonic number (scaled by $\alpha$) and with the first $\lfloor \alpha \rfloor$ summands replaced by $1$. Or you can say that the summands are "capped at 1" after scaling by $\alpha$. For $\alpha=1$, $M$ is simply equal to the $N$th harmonic number. The summation may also be written as the difference of the harmonic numbers $H_N - H_{\lfloor \alpha \rfloor}$. However, I'm not yet quite sure how to approach this problem.

1

There are 1 best solutions below

2
On

This feels like a problem that will need a numeric solution, so we can make some approximations. As you say, the summation can be written as $H_N - H_{\lfloor \alpha \rfloor} \approx \log N - \log {\lfloor \alpha \rfloor}$. Making that substitution, we have $M={\lfloor \alpha \rfloor}+\alpha(\log N- \log {\lfloor \alpha \rfloor})$ or $\alpha=\frac M{\log N−\log\lfloor \alpha \rfloor-1}$, which is a very nice form for iteration. $\log\lfloor \alpha \rfloor$ changes very slowly, so start by setting it to zero, calculating a guess at $\alpha$ and iterate to convergence. Then, if you want, tune it up by using the actual sum.