Computing different terms for a given pair of exponentiation having the same result

Question

To understand the problem,let us consider these examples first:

                                 4⁶ = (2²)⁶ = 2¹² = (2³)⁴ = 8⁴ = 16³ = 4096.

Thus,we can say that 4⁶,2¹²,8⁴ and 16³ are same.

                                 27³ = 3⁹ = 19683

so, both 27³ and 3⁹ are identical.

Now the problem is, for any given pair of a^b how to compute all others possible (if any)x^y where, a^b = x^y.I am interested in an algorithm that can be efficiently implemented in C/C++.

For example:

If the inputs are like this:

4,6 desired output :(2,12),(8,4)

8,4 desired output :(2,12),(2,6)

27,3 desired output :(3,9)

12,6 desired output :(144,3),(1728,2)

7,5 desired output : No duplicate possible

Answer 1

This is mostly a math problem. You can extract all the prime factors of a number, and you'll get a list of prime numbers and their exponents, i.e., 216000 = 2⁶ * 3³ * 5³. Then take the GCD of the exponents: GCD(6,3,3) = 3. Divide the exponents by the GCD to get the smallest root of the number, 2² * 3¹ * 5¹ = 60. Then factor the GCD — factors of 3 are 1 and 3. There is one way to express the number as an integral power for each factor of the GCD. You can express it as (60³)¹ or (60¹)³.

EDIT: fixed math error.

Answer 2

If integers is the only thing you're interested in, you could just start extracting integer roots from the target number, and checking if the result is an integer.

You even have a convenient stop condition - whenever the root is below 2 you can stop. That is, the algorithm:

• Given a result
• N <- 2
• Compute Nth root.
• • If it's an integer: add to answers
• • If it's < 2, exit loop
• N += 1, back to previous step

This algorithm will always terminate.