# Check a number of form $a^b$.

Given a number $n$, what is best efficient way to check if it is of $a^b$ form for some $a,b\geqslant2$.
Provided $n$ can be as large as $10^{16}$.

-
Note that more efficient algorithms exist, but they are more complicated. For example cr.yp.to/papers/powers-ams.pdf – fkraiem Jan 4 '14 at 15:43
@fkraiem i cant download the paper right now because of internet problem.Could you provide me algorithm here? – user3001932 Jan 4 '14 at 15:43

The idea is that there are very few possible values for $b$ (only about $\log n$), so it is okay to just brute force through them. And then for each $b$ the array $[1^b, 2^b, 3^b, \dots, n^b]$ is sorted in ascending order, so we can do a binary search for a value in it which is equal to $n$. Using fast exponentiation, this gives an algorithm which runs in $O(\log^2n\log\log n)$ multiplications mod $n$.