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

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.

Answer 2

The smallest base that makes sense is 2. Also, the smallest exponent that makes sense is 2.

Given the result, you can determine the largest possible exponent.

Example: 4096 = 2^12, biggest exponent is 12.

This also works with results that aren't powers of 2: 19683 is a bit bigger than 2^14, so you won't be seeing any exponents bigger than 14.

Now you can take your number and work your way down from the top exponent toward 2 (the smallest exponent). For every trial exponent exp, take the exp-th root of the result; if that comes out as a clean integer, then you've found one solution.

You can use logarithms to calculate the log2 of a result, and to take the n-th root of a number. But you will need to watch out for rounding errors.

The advantage of this approach is that once you've set things up, you can just run down a simple loop, and once done you have all your results.

Answer 3

I believe that this problem is equivalent to the Integer factorization problem.

I said this because we can convert any composite number to a unique product of prime numbers
(see Fundamental theorem of arithmetic) and then start creating combinations with the factors and the powers.

Update: for example: 4⁶

we convert it to a power of a prime factor, so we have 2¹².
Now we increase the base exponentially and we have: 4⁶, 8⁴ ... until the exponent becomes 1.

Answer 4

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 5

I finally solved it myself.Using a naive integer factorization algorithm my solution look like this.It can be optimized further by using Pollard's rho algorithm

EDIT: Code updated, now it can handle composite bases.Please point if it has certain other bugs too :)