Check if a given number N is a power of k

Question

I am trying to solve a problem to check whether a given number N is a power of k.

Example:

• Input 9, 3> True // 3**2 = 9
• Input 10, 2> False
• Input 4096, 16> True // 16**3 = 4096

I want to know if there is a better solution for this problem.

def check_Power(N,k):
 if N <= 0 or k <=0:
 print "not a valid input"
 else:
 for i in range (1,20):
 x = k**i
 if x == N :
 print " True "
 print k, "power ", i , "is", N
 break
 elif x> N:
 print "false"
 break
check_Power(244140625,5)
check_Power(4096, 16)
check_Power(0, 16)
check_Power(1,1)

• CiaPan: For N to be a multiple of k it must be not less than k and must give an integer result when divided by k. If it is a power of k then the result of division must be either 1 of a multiple of k. So, you can just iterate dividing N by k as long as N is greater or equal k. Then, if it became 1, the initial value was a power of k, otherwise it wasn't.
• CiaPan: One more note: test for k equal 1 — no number (except 1 itself) can be a power of 1...
• dberm22: Duplicate of codereview.stackexchange.com/questions/160924/… ?

Answer 1

Major

print " True "

• Don't print but return variables from functions, that makes them usable later on

print "not a valid input"

• You should raise an Exception with invalid input instead of printing it

for i in range (1,20):

• This line will limit the input range from the function

if N <= 0 or k <=0:

• Your guard clause does not cover all edge cases

Minor

• Use better variable names, x doesn't say much
• That else block is redundant, your if actually is a guard clause, remove the redundant indenting.
• You have a few PEP8 issues

Revised code

def check_pow(N, k):
 if k < 0 or N < 0:
 raise ValueError("k and N must be greater than 0")
 if k == 0 and N == 1:
 return True
 if k in (0, 1) and N != 1:
 return False
 num = k
 while num < N:
 num *= k
 return num == N

• CiaPan: Still not safe — verify check_pow (4, 1).
• Ludisposed: @CiaPan All edge cases are now accounted for
• Olivier Grégoire: Replace greater then with greater than
• amalloy: num isn't any more meaningful than x.
• amalloy: Nothing. I think x was perfectly fine. But a more meaningful name would be something like product, or perhaps acc.

Answer 2

I'd follow Ludisposed's answer.

Except, there's a simple way to do this. Use logarithms. Since the equation is \$N = k^a\$ you can change it to \$a = \log_k N\$. And so if \$a\$ is an integer, then you know that \$N\$ is a power of \$k\$.

import math
def check_power(N, k):
 return math.log(N, k).is_integer()

Since the above can error, and if there's an error it's definately not a power, then you can use:

def check_power(N, k):
 try:
 return math.log(N, k).is_integer()
 except Exception:
 return False

---

This has the some problems with floating point precision, so your can round the number to the closest integer, as you want to know if the \$a\$ is an integer. And so you can sub it back into the original equation to ensure that the numbers are right.

def check_power(N, k):
 return N == k**round(math.log(N, k))

Or if you're on Python 2:

def check_power(N, k):
 return N == k**int(round(math.log(N, k)))

---

This has a problem with some inputs, such as when \$N\$ and \$k\$ are \0ドル\$ or \1ドル\$. And so we can handle these special cases.

def check_power(N, k):
 if N == k:
 return True
 return N == k**round(math.log(N, k))

---

And so merging all the above, we can use the following:

def check_power(N, k):
 if N == k:
 return True
 try:
 return N == k**int(round(math.log(N, k)))
 except Exception:
 return False

• Veedrac: You still need special cases for N == 0 or k in {0, 1}.
• Peilonrayz: @Veedrac How do you mean? They raise exceptions, which are handled in the second code snippet above.
• Veedrac: @Peilonrayz Ah, I was ignoring the earlier snippets since they're wrong, and just looking at the latter ones. Even in that case, check_power(1, 1) is wrong.
• Graipher: @Veedrac Maybe the easiest fix for this would be if N == k: return True.

Answer 3

This answer will focus on cleaning up the algorithm you used although, as other answers have shown, there are better algorithms for this problem. I will also answer how to loop over the infinite list of natural numbers with a generator. (Although I will refer to these as the counting numbers to clarify that I am not including 0.)

"Flat is better than nested"

An if statement that is checking a precondition for a function should avoid else because the else makes the entire function more deeply nested and adds little to the understandability when it is clear that the if statement is there to check if the provided arguments are valid.

Misc

I recommend returning True or False instead of printing so that you can reuse this function in later problems. As a slight benefit, returning a value also removes the need for break.

I also recommend using from __future__ import print_function so that you can be forwards compatible with Python3. Note that you will have to use parentheses with print and the new version below doesn't use print so this was left out of the code below.

Generators

Answering your question about how to loop over all the counting numbers, you could use a while loop or you could use generators. To show what your code might look like with a generator, see the following.

def counting_numbers():
 i = 1
 while True:
 yield i
 i += 1
def check_power(N, k):
 # Note that you could include 0 if you're careful about it.
 if N <= 0 or k <= 0:
 raise ValueError("N and k should be greater than 0")
 # We need to catch 1 as a special case because 1 ** n = 1 for all n
 # and thus 1 ** n will never be greater than N causing an infinite loop
 if k == 1: # If the power is one
 return N == 1 # Then N is a power only if it is 1
 for i in counting_numbers():
 x = k ** i
 if x == N :
 return True
 elif x > N:
 return False

As you can see, you write what looks like a normal function and then use yield wherever you want to give a value to the for loop. The generator you are writing will yield control over to the loop whenever it hits a yield statement which is why this generator doesn't cause the program to seize up in an infinite loop. You can read more about generators in their original PEP 255 or in various online tutorials. Just know that they will stop upon hitting the end of their block like a function would or a return statement. (Sidenote: don't try using return x in a generator, this is related to sending a StopIteration and doesn't make the generator return a value like you might expect.)

In this case, we actually don't have to write counting_numbers because itertools already has this builtin as itertools.count but because we want to start from 1 instead of 0 we will have to call count(1) instead of count() which would start from 0. We can now rewrite the above solution to

from itertools import count
def check_power(N, k):
 if N <= 0 or k <= 0:
 raise ValueError("N and k should be greater than 0")
 # This special case is to avoid an infinite loop
 if k == 1:
 return N == 1
 for i in count(1):
 x = k ** i
 if x == N :
 return True
 elif x > N:
 return False

Answer 4

I recommend @Ludisposed's answer for the Pythonic comments.

The algorithm itself can be improved to get logarithmic complexity (ie, a logarithmic number of multiplies and comparisons).

The idea is to use:

1. A galloping search to locate the two powers of 2 between which log_k(N) would be if N was a power of 2.
2. A binary search between the last smaller power of 2 and its successor to locate the exact exponent.

Visualizing it in code may be easier:

def check_pow(N, k):
 if k < 0 or N < 0:
 raise ValueError("k and N must be greater then 0")
 if k == 0 and N == 1:
 return True
 if k in (0, 1) and N != 1:
 return False
 powers = [1, k] # powers[i] = k ** (2**i)
 # Galloping search:
 # With e = log-k(N),
 # find a and b such that 2**a <= e < 2**b
 while powers[-1] < N:
 powers.append(powers[-1] * powers[-1])
 # Binary search:
 # Narrow down the gap to find the closest power of k
 # that is <= to N.
 powers.pop()
 cursor = powers.pop()
 while len(powers) > 0:
 candidate = cursor * powers.pop()
 if candidate <= N:
 cursor = candidate
 return cursor == N

There are minor performance improvements possible still, short-circuitings notably, however they do not improve the worst-case complexity so I left them out to avoid mucking the algorithm.

Answer 5

This can be done without looping. The idea is to rearrange $$N=k^c$$ to $$c = \log_k N = \frac{\log N}{\log k}.$$ If the exponent is an integer, then it is a perfect power. In the below code, some extra work is done to avoid floating-point rounding errors.

import math
def check_Power(N,k):
 # input validation
 if N < 0:
 raise Exception('N must be non-negative')
 if k < 0:
 raise Exception('k must be non-negative')
 # 1 to any power can only equal 1
 if k == 1:
 return N == 1
 # Only raising 0 to a non-zero power results in zero
 if N == 0 or k == 0:
 return k == N
 # Use math.floor to make the exponent an integer
 # that is within 1 of the actual answer
 exponent = math.floor(math.log(N)/math.log(k))
 # Test whether the integer exponent solves
 # the problem and adjust the exponent as needed
 testN = k**exponent
 if testN < N:
 exponent += 1
 elif testN > N:
 exponent -= 1
 else:
 return True # testN == N
 return k**exponent == N # check adjusted exponent

• Martin R: Isn't that essentially what codereview.stackexchange.com/a/184267/35991 suggests?
• Mark H: @MartinR Now that I look at it more carefully, yes.

Answer 6

I'm going to assume you mean integers since that's what your test data suggests. I'm also assuming the powers are non-negative integers so as not to involve roots ^(a).

In that case, there's no need to do all those power calculations, you just need to realise that, if n is a power of k, then continuously multiplying an accumulator (initially k) by k will either:

• reach n exactly (if it's a power).
• exceed n (if it's not a power).
• never satisfy either of those conditions because the accumulator never gets any closer to n (see below code for those conditions).

In any case, the code you have only checks if n is a power of k with an exponent less than or equal to twenty, it won't return true for k = 2, n = 2**31 for example.

The code to do it a a less limited way is a stunningly simple:

def isPower(n, k):
 # Special cases.
 if k == 0: return n == 0 # 0^not-0 always 0, 0^0 undefined
 if k == 1: return n == 1 # 1^n always 1
 if k == -1: return abs(n) == 1 # -1^n alternates +/-1
 # abs(k) is now >= 2 so it will always increase in magnitude.
 acc = k
 while abs(acc) < abs(n):
 acc = acc * k
 return acc == n

---

^(a) If you decide to use floating point values, it gets a little more complicated. You then have to cater for more possibilities:

• if the power is allowed to be fractional, you'll have to cater for roots as well as powers;
• where k is be between -1 and 1, it will always approach zero rather than getting larger, so you'll need to adapt for that;
• the adaptation for that must also take into account whether n is in that range or whether its absolute value is greater than or equal to one;

There's may well be other issues that haven't sprung immediately to mind, I won't think too much about them as, in the absence of further information, they're probably unnecessary.

• Martin R: Isn't that essentially the solution suggested in this answer codereview.stackexchange.com/a/184266/35991 ?
• user7649: The fact that the five lines of calculation loop is pretty much the same does not, I believe make the answer as a whole identical. There is no reason to limit the input variables to positive integers, my answer allows for either sign. It also details what would be needed to make it work for non-integers as well.
• Martin R: For which negative input? Your isPower(-8, -2) returns False.
• user7649: @MartinR, good catch, I believe I've fixed that now, it was a slight bug in the terminating condition for the loop.
• Martin R: Your isPower(1, -1) returns False.

Answer 7

first it will validate the both Base Number and Result are not equal to zero and both numbers are divisible are not.

Here Count is iterating variable it will check condition for each pass.

BaseNumber = 16
Result = 4096
count = 1
power = 0
if Result and BaseNumber != 0 and Result % BaseNumber == 0:
while count != Result:
 count = BaseNumber * count
 power += 1
print(power)
else:
print("wrong input")

• dfhwze: Please don't just dump code. Try to explain why your solution works and how it improves the OP. Visit our help center for more info: codereview.stackexchange.com/help/how-to-answer.