How to find i-th root of n whose remainder is the smallest?
You want to write $n$ as $b^x + r$ with $x,r \ge 0$ and $b \in \{2, \dots, 2^{31} - 1\}$.

Since you're asking for the asymptotic complexity and the base $b$ is in a set of constant size, you can just focus on a single value of $b$. 
The exponent is then $x = \lfloor \log_b n \rfloor$ and can be found using $O(\log \log n)$ operations (search for the first $y$ such that $b^y &gt; n$ by trying $b, b^2, b^4, b^8, \dots$, where each term is the product of the previous term by itself, then binary search for the last $x \in \{y/2, \dots, y\}$ such that $b^x \le n $).

The above procedure already gives you $b^x$, from which you can compute $r = n - b^x$. Return the triple $(b, x, r)$ that minimizes $r$.

If the time of each arithmetic operation is constant, the above requires $O(\log \log n)$ time. If each arithmetic operation takes logarithmic time in the value of its operands, then the complexity is $O(\log n \cdot \log \log n)$.