Crthuky

Is there a general method for testing numbers to see if they are perfect $n$th powers?

For example, suppose that I did not know that $121$ was a perfect square. A naive test in a code might be to see if
$$lfloorsqrt121rfloor=sqrt121$$

But I imagine there are much more efficient ways of doing this (if I'm working with numbers with many digits).

See Detecting perfect powers in essentially linear time - Daniel J. Bernstein:

https://cr.yp.to/papers/powers-ams.pdf

In the specific case where you already know not only the number being checked but also the power, as the question's comment by the OP to Servaes states, then you have something like

$$k = a^n tag1labeleq1$$

where $k$ and $n$ are known integers, but with $a$ being an unknown value to check whether or not it's an integer. In this case, taking natural logarithms of both sides (you could use any base, but I suspect that implementation wise $e$ will likely at least be the fastest one, if not also the most accurate) gives

$$ln(k) = nln(a) ; Rightarrow ; ln(a) = fracln(k)n ; Rightarrow ; a = e^fracln(k)n tag2labeleq2$$

On a computer, this will give a floating point value that would be, even for large values of $k$, relatively close to the correct value of $a$.

You can now use any number of algorithms to relatively quickly & easily determine $a$ if it's an integer, or show it's not an integer. For example, you can start with the integer part obtained in eqrefeq2, call it $a_1$, to determine $k_1$. If $k_1$ is not correct, then if it's less than $k$, check $a_2 = a_1 + 1$, else check $a_2 = a_1 - 1$, and call the new result $k_2$. If $k_2$ is still not correct, add or subtract the integer amount (making sure it's at least 1) of $left|frack -k_2k_1 - k_2right|$ to $a_2$ to get a new $a_1$ value to check. Then repeat these steps as many times as needed. In almost all cases, I believe it should take very loops to find the correct value. However, note you should also include checks in case there is no such integer $a$, with this usually being seen when one integer value gives a lower result & the next higher gives a higher result (or higher result & next lower integer gives a lower result).

My suggestion on a computer is to run a root finder.

Given a value $y$, one way is to hard-code the first couple and then use an integer-valued binary search starting with $y/2$, which is logarithmic in $y$ and thus linear (since input takes $ln y$.

You can also write down the Newton's method recurrence and see if it converges to an integer or not, should become clear after the first couple of steps, once the error becomes small enough.

There are many powerful codes that factorize a number to its prime factors in a non-polynomial time (for more information you can refer to Integer Factorization on Wikipedia) . Once an integer was factorized as follows$$n=p_1^alpha_1times p_2^alpha_2timescdots times p_m^alpha_m$$then by defining $d=gcd(alpha_1,alpha_2,cdots ,alpha_m)$ we can say that $n$ is a full $d$-th power.

It is at least possible to do this in polynomial time. Assume $n$ is a $k$-bit number and you want to find positive integers $a$ and $b$ such that $$a^b=ntag1$$ or prove that such numbers don't exists.

We have $$n<2^k$$ because $n$ is a $k$-bit number and so $$blt k$$

We can simply check for all possible $b$ if there is an $a$ such that $(1)$ holds. For given $b$ we can try to find $a$ by bisection. This bisection checks $O(log n)=O(k)$ different $a$. A check is the calculation of $a^b$. This can be achieved by multiplying powers of $a$ by $a$. These powers of $a$ are smaller than $n$. So we multiply $k$-bit numbers at most $b(lt k)$ times. A multiplication of two $k$-bit numbers needs $O(k^2)$ time. So all in all the algorithm needs $O(k^2)$ multiplications o $k$-bit numbers, which means $O(k^4)$ time.