Given an integer, how can I detect the nearest integer perfect power efficiently?

Solution 1:

One algorithm is as follows. You know that the exponent will be at least $2$, so you won't have to take powers greater than $\log_2 N$. So loop over $k = 2, 3, \ldots, \lfloor \log_2 N \rfloor$; for each one examine the candidates $\lfloor N^{1/k} \rfloor^k$ and $\lceil N^{1/k} \rceil^k$. This finds perfect squares, cubes, 4th powers, ... near $N$. This is the algorithm

Another algorithm, obviously worse, is to find perfect powers of $2, 3, \ldots, \sqrt{N}$ near $N$. Loop over $j = 2, 3, \ldots, \sqrt{N}$, and for each one examine the candidates $j^{\lfloor x \rfloor}$ and $j^{\lceil x \rceil}$ where $x = \log_j N$.

You can improve by combining the two. Run the first algorithm for $k = 2, 3, \ldots, f(N)$, which will find cases where the exponent is small, at most $f(N)$. Then run the second for $j = 2, 3, \ldots, g(N)$, which will find cases where the exponent is large, at least $(\log N)/(\log g(N))$. So you need to test twice $f(N) + g(N)$ candidates; you want to minimize $f(N) + g(N)$ subject to $f(N) > (\log N)/(\log g(N))$, i. e. $g(N)^{f(N)} > N$.

For example if $N = 10^{100}$ you can compute (I don't know a good way to do this other than trial and error) that $f(N) = 21$, since $21^{76} > 10^{100}$, is optimal. So loop over $k = 2, 3, \ldots, 21$ and find the nearest $k$th powers; then loop over $j = 2, 3, \ldots, 76$ to find the nearest powers of $2, 3, \ldots, 76$. This only requires checking $2 \times (21 + 76 - 2) = 190$ candidates, compared to $2 \times 331 = 662$ for just using my first algorithm.