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)

  • $\begingroup$ Go over all values of $x$, and for each one, compute the best $n$. Then choose the best answer. $\endgroup$ – 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.


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 > 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.