How to find the closest N to the power of X to the given number? Let's say we have number 4920 and we want to find the closest $n^x$ to 4920

2 ^ 12 = 4096 but it's not the closest possible $n^x$, for example 17 ^ 3 = 4913 is closer to 4920

The question is, how do we find the closest $n^x$, where $n$ and $x$ are less than 2 digits long? (because $4913^1$ is not what I want)
Here is a general solution for the following problem:


  Given a positive integer $m$, find positive integers $a,b \geq 2$ such that $a^b$ is as close as possible to $m$.


Let $n$ be the length of $m$ in bits (so $n = \Theta(\log m)$). If $2^b &gt; m$ then there is no point to check any $b_0 &gt; b$, hence we only need to check $O(\log m) = O(n)$ many different values of $b$ (we can find the maximal $b$ by comparing $2^b$ to $m$). For each value of $b$, we can find the best value of $a$ using binary search; this takes polynomial time for each $b$, and so polynomial time overall. Finally, we choose the optimal solution among the $O(\log m)$ possibilities.