snippetMinor
How to find the closest N to the power of X to the given number?
Viewed 0 times
thenumberhowclosestpowerfindgiven
Problem
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)
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)
Solution
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.
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.
Context
StackExchange Computer Science Q#79595, answer score: 6
Revisions (0)
No revisions yet.