6
$\begingroup$

Given a integer $n$, we want to know if $n=m^k$ for some $m$ and $k>1$. What is the fastest method? (Suppose the factors of $n$ are not given).

The best method I can think of is to try to calculate $n^\frac{1}{k}$ to a certain precision, for $k$ from $2$ to $\log_2 n$. Determine if $n^\frac{1}{k}$ is a integer by test if $\lfloor n^\frac{1}{k} \rfloor ^k = n$.

  • 1
    Almost the same question was asked on MathOverflow about a year ago: http://mathoverflow.net/questions/13843/how-to-quickly-determine-whether-a-given-natural-number-is-a-power-of-any-other-n2011-02-17
  • 1
    The method you wrote down is __very__ fast. (Except there is no need to reraise it to the power $k$, just check the distance to nearest integer, and see if that is within the error tolerance of the $k^{th}$ rooting algorithmP) What are you doing that needs this to be faster? Whatever your program, it seems unlikely that this is the limiting factor for computation speed.2011-02-17

1 Answers 1

2

Like Jonas Meyer said, the mathoverflow post contains all the information.

The problem can be solved in almost linear time by this paper.