Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.

share|improve this question
1  
Almost the same question was asked on MathOverflow about a year ago: mathoverflow.net/questions/13843/… –  Jonas Meyer Feb 17 '11 at 23:26
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. –  Eric Naslund Feb 17 '11 at 23:37

1 Answer 1

up vote 1 down vote accepted

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

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.