# Can we decide if a number is a power of any given $K$ in polynomial-time?

It is simple to decide powers of 2 in $$O(n)$$ time because it's just "0-bit Unary" after bit-1. (eg. $$1000$$ is a power of 2 in binary).

I haven't found many other trivial powers of $$K$$ that can be decided in polynomial-time with the binary-length of the input.

## Question

Can we decide if a number is a power of any given $$K$$ in polynomial-time and in a practical amount of time?

Something not naive such as keep dividing $$N$$ by $$K$$ until you reach the smallest value $$2$$ for deciding a power of 2.

• This also allows a special case of factorization in $P$. Just simply delete the 0-bit one by one at a time until you reach $1$. Each iteration is a factor of a power of $2$. Use binary factors, not integer factors. Integer factors would be slower! – Travis Wells Jul 13 '20 at 23:33
• Yes. Use binary search on the value of the exponent. See cs.stackexchange.com/q/48033/755. – D.W. Jul 13 '20 at 23:36
• @D.W. Seems like a $O(n log n)$ algorithm (integer factorization of powers of 2). If I could guess, I'm just an amateur tinkering in college algebra and lots of python practice. – Travis Wells Jul 13 '20 at 23:37
• I don't understand your problem. You are given a number N and number K and want to check whether N is a power of K? Why no just divide N by K repeatedly? It will be polynomial in the length of N. – user114966 Jul 13 '20 at 23:49
• Instead of dividing by $K$ each time, I would compute $K, K^2, K^{2^2},K^{2^3},...$ and divide by the largest such that is not larger than $N$. Repeat the same procedure with the resulting quotient. It would take about $\log_2(\log_K(N))$ divisions, same number of multiplications (squaring). Then you can count each of these big int operations how fast they are in bit operations. – plop Jul 14 '20 at 1:26