Lets say there is a positive number (integer) given ($N$). What should be the simplest way to find the $K^p$ (where $K$ and $p$ both $>1$) which is closest to $N$ amongst all the possible combinations of $K$ and $p$?
When we say closest, it means the difference between $N$ and $K^p$ is less than any other possible combination of $K$ and $p$.
Example: If $N=25$ then $5^2$ is the closest solution. If $N=150$ then $12^2$ is the closest you can get to $N$. And so on.
Most perfect powers are squares, so a good way would be to find $a$ such that $a^2\le N\le (a+1)^2$, and then test all the numbers between $a^2$ and $(a+1)^2$ to see whether there are any perfect powers there.
Another way is to first calculate the integer part $k$ of $\log_2N$, so you know that (in your notation) $k+1$ is an upper bound for the $p$ you are looking for. Then you can calculate $N^{1/r}$ (or $(1/r)\log N$) for $2\le r\le k+1$ and pick out the best answer.