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

• Go over all values of $x$, and for each one, compute the best $n$. Then choose the best answer. – Yuval Filmus Aug 2 '17 at 9:13

If $n$ and $x$ are both less than 100, there are only 10,000 combinations to check (including duplicates like $2^4 = 4^2$). That's nothing. You could precompute all of them and then implement the lookup using binary search.
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 > m$ then there is no point to check any $b_0 > 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.