0

65536= 4^8------( how can i find the base and power for a number.)

Now, if I am randomly given a number. Say, 4096 and I need to find a common base having some power. I mean a^n. Where a is the base and n is its power. So, accordingly answer for above number shall be 8^4.

Can you please give me some trick to find such bases and powers for a given number condition- Not to use factorization method or something which could be time consuming.

T.J. Gaffney
  • 1,568
Faaria Shaikh
  • 9
  • 2
    Does $4096$ have to be $8^4$, or can it be $4^6$ or $2^{12}$ as well? – Arthur Dec 03 '19 at 07:22
  • 1
    Note that the powers are generally not unique. For example, $65536=2^{16}=4^8=16^4=256^2=65536^1$. But a simple way to find a power (though surely not what you had in mind) is: For any number $n$, we have $n=n^1$. – celtschk Dec 03 '19 at 07:23
  • 3
    The only way to do it without factorisation is to look for integer-valued logarithm ratios. – J.G. Dec 03 '19 at 07:36
  • Since $65536=2^{12}$ is the factorization of $65536$, I wonder how a method (that results in anything better than a trivial $n^1$) could be less complex than factorization. Even if a method merely finds $256^2$, we see that repeating it with the much smaller input $256$ will ultimately end up with the above factorization with little extra effort. – Hagen von Eitzen Dec 03 '19 at 07:39
  • 1
    See https://cstheory.stackexchange.com/q/2077/1993 – Bjørn Kjos-Hanssen Dec 03 '19 at 07:39
  • So, all the comments here mean I have to use Factorization. – Faaria Shaikh Dec 03 '19 at 12:39
  • @FaariaShaikh No, see J.G. ' s comment. PARI/GP has a function ispower(n) , which finds the power with the highest possible exponent (assuming the number is a perfect power). The function is very fast even for huge numbers, so surely does not use factorization algorithms. – Peter Dec 21 '19 at 16:46
  • @ Peter, can you please elaborate more. I mean you said about a function. So, can you tell me more about it. – Faaria Shaikh Dec 23 '19 at 11:21

0 Answers0