## Monday, January 25, 2016

### Check if a number can be expressed as x raised to power y

Check if a number can be expressed as x^y (x raised to power y) - GeeksforGeeks
Given a positive integer n, find if it can be expressed as xy where y > 1 and x > 0. x and y both are integers.

Check if the number is even or odd, initialize X with 2 or 3 based on that, and then increment X by 2. It will directly reduce the calculations to half.
Also, better approach is to find the prime factors of N, and then use them to find all the X such that X^Y=N.
An alternative approach to the problem could be finding the prime factorization of number n,
i.e. say the prime factorization of n= p1^x1*p2^x2*.......*pk^xk ,
then the number could only be expressed as x^y if and only if gcd(x1,x2,....,xk)!=1;
i.e. if the gcd is 1 or number is prime then it can't be expressed as x^y .
Moreover the time complexity of finding prime factorization is O(sqrt(n)) and gcd is log(n).Finding prime factorization could be improved using some sieve like erasthothenes.
int gcd(int a,int b){
if(a<b){
int t=a;a=b;b=t;
}
if(b==0)
return a;
return gcd(b,a%b);
}
int test_if_power(int n){
bool flag=true;
int t=n;
int curr_gcd=INT_MAX;
// if n==1 then it can't be expresses as x^y for y>1
if(n==1)
flag=false;
if(n%2==0){
int p=0;
while(n%2==0)
{
n=n/2;
p++;
}
// find the power of 2 in the prime factorization of n
if(p==1)
flag=false;
if(curr_gcd==INT_MAX)
curr_gcd=p;
}

for(int i=3;i<=sqrt(n);i+=2){
if(n%i==0){
int p=0;
while(n%i==0){
n/=i;
p++;
}
// if for any prime factor p the power is 1 then n can not be expressed as x^y
if(p==1)
flag=false;
// if i is the first prime factor of p then set the gcd to power of i;
if(curr_gcd==INT_MAX)
curr_gcd=p;
else
curr_gcd=gcd(p,curr_gcd);
//find the gcd of curr_gcd and the power of prime factor i;

}
}
if(n>2){
flag=false;
}
if(!flag){
// return in case flag is false or curr_gc is 1;
return 0;
}
if(curr_gcd!=1)
cout<<t<<" ";
}

One optimization in above solution is to avoid call to pow() by multiplying p with x one by one.
`bool` `isPower(unsigned ``int` `n)`
`{`
`    ``// Base case`
`    ``if` `(n <= 1) ``return` `true``;`
`    ``// Try all numbers from 2 to sqrt(n) as base`
`    ``for` `(``int` `x=2; x<=``sqrt``(n); x++)`
`    ``{`
`        ``unsigned  p = x;`
`        ``// Keep multiplying p with x while is smaller`
`        ``// than or equal to x`
`        ``while` `(p <= n)`
`        ``{`
`            ``p *= x;`
`            ``if` `(p == n)`
`                ``return` `true``;`
`        ``}`
`    ``}`
`    ``return` `false``;`
`}`
The idea is simple try all numbers x starting from 2 to square root of n (given number). For every x, try x^y where y starts from 2 and increases one by one until either x^y becomes n or greater than n.
`// Returns true if n can be written as x^y`
`bool` `isPower(unsigned n)`
`{`
`    ``if` `(n==1)  ``return` `true``;`
`    ``// Try all numbers from 2 to sqrt(n) as base`
`    ``for` `(``int` `x=2; x<=``sqrt``(n); x++)`
`    ``{`
`        ``unsigned y = 2;`
`        ``unsigned p = ``pow``(x, y);`
`        ``// Keep increasing y while power 'p' is smaller`
`        ``// than n. `
`        ``while` `(p<=n && p>0)`
`        ``{`
`            ``if` `(p==n)`
`                ``return` `true``;`
`            ``y++;`
`            ``p = ``pow``(x, y);`
`         ``}`
`    ``}`
`    ``return` `false``;`
`}`
Check if a number can be expressed as x raised to power y
Given a positive integer, find if it can be expressed by integers x and y as x^y where
y > 1 and x > 0.

Example:
Consider the number: 125
Since 125 can be written as x^y where x = 5, y = 3, so return true.
Consider the number: 120
As 120 cannot be expressed as x^y for any integers x > 0 and y > 1, so return false.

`    ``public static boolean isPower(int a) {`
`        ``int factor = 2;`
`        ``while` `(factor <= Math.sqrt(a)) {`
`            ``int number = a;`
`            ``while` `(number % factor == 0) {`
`                ``number /= factor;`
`            ``}`
`            ``if` `(number == 1) {`
`                ``return` `true``;`
`            ``} ``else` `{`
`                ``factor++;`
`            ``}`
`        ``}`
`        ``return` `false``;`
`    ``}`
http://www.ideserve.co.in/learn/check-if-a-number-can-be-expressed-as-x-raised-to-power-y-set-2
Instead of repeated divisions as given in previous method, we can apply mathematical formula as described:
Given a number a, we have to find integers x and y, such that:
a = x^y
If we take log on both sides, we get:
log a = log (x^y)
log a = y log x
y = log a / log x
Hence, we have to find an integer x for which RHS gives an integer y.

Algorithm:
1: Starting with i = 2, if (log a / log i) is an integer then return true.
2: Else increment i by 1 till i < √a.
3: If no such i is found, return false.
`    ``public static boolean isPowerMath(int a) {`
`        ``if` `(a == 1)`
`            ``return` `true``;`
`        ``for` `(int i = 2; i <= Math.sqrt(a); i++) {`
`            ``double value = Math.log(a) / Math.log(i);`
`            ``if` `((value - (int) value) < 0.000000001) {`
`                ``return` `true``;`
`            ``}`
`        ``}`
`        ``return` `false``;`
`    ``}`
Read full article from Check if a number can be expressed as x^y (x raised to power y) - GeeksforGeeks