Is there a fast way to find a representation of an integer $N$ of an arbitrary length as $x^a y^b$ ?
I thought I could find it quickly using some kind of log operations, but I can't come up with a solution.
For example: let's say we want to find such representation for $N = 1944$. The answer would be $1944 = 3^5 2^3$.
What is the algorithm to find $x^a y^b$ for, let's say, $N = 73625$?
Ideally, I would want it to be in a compact form, hence: $a,b,x,y<999$.
Rob and lulu basically answered it in the comments.
1) Find the prime factorization of $N = p_1^{n_1}*p_2^{n_2}.....*p_m^{n_m}$
2) If any of the $n_i$ are equal to one it can not be done. This will happen about $60\%$ of the time!
3) If you only have two prime you are done: $N = p_1^{n_1}*p_2^{n_2}$.
4) If you have only one prime less than or equal to $3$ i.e. $N= p^3$ or $p^2$ it can not be done but other wise you are done: $N = p^n = p^a*p^b$ for any $a+b=n$.
5) If all then $n_i$ are even then you are done $N=(p_1)^{n_1}*(p_2^{n_2/2}*....p_m^{n_m/2})^2$.
6) Separate the even $n_i$ from the odd from the odd so that
$N = p_l^{2k_l}...p_j^{2k_j}*p_h^{2k_h + 3}...p_i^{2k_n + 3}$
7) Break this into $N = (p_1^{k_1}..... p_n^{k_n})^2*(p_h....p_i)^3$.
8) The only case not covered above is if $N= p_1^3.....p_n^3$. In this case $N = (p_1)^3*(p_2.....p_3)^3$.
So for example, if I take $N=16810159716000$
Prime factorization is $N=2^5 * 3^6 * 5^3 * 7^8$
$= (2^2*3^6*7^8)*(2^3*5^3) = (2*3^3*7^4)^2*(2*5)^3 = 129654^2*10^3$
Which is not the only way to do it. Ex. $(2*7)^2(2*3^2*5*7^2)^3$ will also work. It's just a matter of splitting the prime factors so that all the exponents are all multiples of one of two numbers. Which sounds hard but is easy to do in practice. That is if it can be done at all, Which it usually won't, but will be easy to see when it can't.