Check if one integer is an integer power of another

It means log_y(x) should be an integer. Don't need any loop. in O(1) time

public class PowerTest { public static boolean isPower(int x, int y) { double d = Math.log(Math.abs(x)) / Math.log(Math.abs(y)); if ((x > 0 && y > 0) || (x < 0 && y < 0)) { if (d == (int) d) { return true; } else { return false; } } else if (x > 0 && y < 0) { if ((int) d % 2 == 0) { return true; } else { return false; } } else { return false; } } /** * @param args */ public static void main(String[] args) { System.out.println(isPower(-32, -2)); System.out.println(isPower(2, 8)); System.out.println(isPower(8, 12)); System.out.println(isPower(9, 9)); System.out.println(isPower(-16, 2)); System.out.println(isPower(-8, -2)); System.out.println(isPower(16, -2)); System.out.println(isPower(8, -2)); } } 

This looks for the exponent in O(log N) steps:

#define MAX_POWERS 100 int is_power(unsigned long x, unsigned long y) { int i; unsigned long powers[MAX_POWERS]; unsigned long last; last = powers[0] = y; for (i = 1; last < x; i++) { last *= last; // note that last * last can overflow here! powers[i] = last; } while (x >= y) { unsigned long top = powers[--i]; if (x >= top) { unsigned long x1 = x / top; if (x1 * top != x) return 0; x = x1; } } return (x == 1); } 

Negative numbers are not handled by this code, but it can be done easyly with some conditional code when i = 1

This looks to be pretty fast for positive numbers as it finds the lower and upper limits for desired power and then applies binary search.

#include <iostream> #include <cmath> using namespace std; //x is the dividend, y the divisor. bool isIntegerPower(int x, int y) { int low = 0, high; int exp = 1; int val = y; //Loop by changing exponent in the powers of 2 and //Find out low and high exponents between which the required exponent lies. while(1) { val = pow((double)y, exp); if(val == x) return true; else if(val > x) break; low = exp; exp = exp * 2; high = exp; } //Use binary search to find out the actual integer exponent if exists //Otherwise, return false as no integer power. int mid = (low + high)/2; while(low < high) { val = pow((double)y, mid); if(val > x) { high = mid-1; } else if(val == x) { return true; } else if(val < x) { low = mid+1; } mid = (low + high)/2; } return false; } int main() { cout<<isIntegerPower(1024,2); } 

 double a=8; double b=64; double n = Math.log(b)/Math.log(a); double e = Math.ceil(n); if((n/e) == 1){ System.out.println("true"); } else{ System.out.println("false"); } 

I would implement the function like so:

bool IsWholeNumberPower(int x, int y) { double power = log(x)/log(y); return floor(power) == power; } 

This shouldn't need check within a delta as is common with floating point comparisons, since we're checking whole numbers.

On second thoughts, don't do this. It does not work for negative x and/or y. Note that all other log-based answers presented right now are also broken in exactly the same manner.

The following is a fast general solution (in Java):

static boolean isPow(int x, int y) { int logyx = (int)(Math.log(x) / Math.log(y)); return pow(y, logyx) == x || pow(y, logyx + 1) == x; } 

static int pow(int a, int b) { return (int)Math.pow(a, b); } 

The reason to go with logarithms instead of repeated division is performance: while log is slower than division, it is slower by a small fixed multiple. At the same time it does remove the need for a loop and therefore gives you a constant-time algorithm.

In cases where y is 2, there is a quick approach that avoids the need for a loop. This approach can be extended to cases where y is some larger power of 2.

If x is a power of 2, the binary representation of x has a single set bit. There is a fairly simple bit-fiddling algorithm for counting the bits in an integer in O(log n) time where n is the bit-width of an integer. Many processors also have specialised instructions that can handle this as a single operation, about as fast as (for example) an integer negation.

To extend the approach, though, first take a slightly different approach to checking for a single bit. First determine the position of the least significant bit. Again, there is a simple bit-fiddling algorithm, and many processors have fast specialised instructions.

If this bit is the only bit, then (1 << pos) == x. The advantage here is that if you're testing for a power of 4, you can test for pos % 2 == 0 (the single bit is at an even position). Testing for a power of any power of two, you can test for pos % (y >> 1) == 0.

In principle, you could do something similar for testing for powers of 3 and powers of powers of 3. The problem is that you'd need a machine that works in base 3, which is a tad unlikely. You can certainly test any value x to see if its representation in base y has a single non-zero digit, but you'd be doing more work that you're already doing. The above exploits the fact that computers work in binary.

Probably not worth doing in the real world, though.

Here is a Python version which puts together the ideas of @salva and @Axn and is modified to not generate any numbers greater than those given and uses only simple storage (read, "no lists") by repeatedly paring away at the number of interest:

def perfect_base(b, n): """Returns True if integer n can be expressed as b**e where n is a positive integer, else False.""" assert b > 1 and n >= b and int(n) == n and int(b) == b # parity check if not b % 2: if n % 2: return False # b,n is even,odd if b == 2: return n & (n - 1) == 0 if not b & (b - 1) and n & (n - 1): return False # b == 2**m but n != 2**M elif not n % 2: return False # b,n is odd,even while n >= b: d = b while d <= n: n, r = divmod(n, d) if r: return False d *= d return n == 1 

# This version is robust with positive or negative integers. def is_power_of(number, multiplier): """test if number is exactly multiplier^(some integer), inputs are positive or negative integers""" if number == 1: return True # Anything^0 == 1 if multiplier == 0: return number in (0,1) # 0^Positive == 0 # 0^0 == 1 # 0^Negative == illegal if multiplier == 1: return number == 1 # 1^0 == 1 # 1^Positive == 1 # 1^Negative == 1 if multiplier == -1: return number in (-1,1) # -1^Odd == -1 # -1^Even == 1 # now that multiplier >=2, accumulator will grow (might alternate sign) abs_number = abs(number) accumulator = multiplier while abs(accumulator) < abs_number: accumulator = accumulator * multiplier return accumulator == number 

Previous answers are correct, I liked Paul's answer the best. It's Simple and clean. Here is the Java implementation of what he suggested:

public static boolean isPowerOfaNumber(int baseOrg, int powerOrg) { double base = baseOrg; double power = powerOrg; while (base % power == 0) base = base / power; // return true if base is equal 1 return base == 1; } 

in the case the number is too large ... use log function to reduce time complexity:

import math base = int(input("Enter the base number: ")) for i in range(base,int(input("Enter the end of range: "))+1): if(math.log(i) / math.log(base) % 1 == 0 ): print(i) 

I found this Solution

//Check for If A can be expressed as power of two integers int isPower(int A) { int i,a; double p; if(A==1) return 1; for(int a=1; a<=sqrt(A);++a ) { p=log(A)/log(a); if(p-int(p)<0.000000001) return 1; } return 0; } 

binarycoder.org

If you have access to the largest power of y, that can be fitted inside the required datatype, this is a really slick way of solving this problem.

Lets say, for our case, y == 3. So, we would need to check if x is a power of 3.

Given that we need to check if an integer x is a power of 3, let us start thinking about this problem in terms of what information is already at hand.

1162261467 is the largest power of 3 that can fit into an Java int.
1162261467 = 3^19 + 0

The given x can be expressed as [(a power of 3) + (some n)]. I think it is fairly elementary to be able to prove that if n is 0(which happens iff x is a power of 3), 1162261467 % x = 0.

So, to check if a given integer x is a power of three, check if x > 0 && 1162261467 % x == 0.

Generalizing. To check if a given integer x is a power of a given integer y, check if x > 0 && Y % x == 0: Y is the largest power of y that can fit into an integer datatype.

The general idea is that if A is some power of Y, A can be expressed as B/Ya, where a is some integer and A < B. It follows the exact same principle for A > B. The A = B case is elementary.