Question of checking the $n$th root
The function

$$f(h) = \left( {k \over 4h-1} \right)^h$$

is monotonically decreasing for $h &lt; k+1/4$, and monotonically increasing for $h&gt;k+1/4$.  (How do I know?  Set $f'(h)=0$ and solve for $h$.)

Therefore, one approach is to use a binary search on $h$ within the range $[0, \min(k+1/4,n)]$ to search for $h$ such that $f(h)=n$, followed by another binary search on $h$ within the range $[k+1/4, n]$.  You could also replace the binary search with a method with faster convergence, such as Newton's method.