How can we represent any number as a series of exponents?

Question

Say I have a positive integer that is one-thousand digits long. What math could I use to represent this number as a series of exponents in a significantly shorter form than the original number? The number is rather random.

For example, $(4^5)^6$ makes 1152921504606846976. What steps can I use to deduce that 1152921504606846976 can be composed of $(4^5)^6$?

If we tried to "compress" the integer $x$ and found that $a^n = x$ for some integers $a$ and $n$, then we could simply factorize $n$ to write $a^n$ in iterated exponentiation. So, is it correct to reduce your question to "how do I detect what is the maximum $n$ such that $\sqrt[n]{x}$ is an integer?" — Herng Yi, Jan 20 '13 at 05:19
@HerngYi, I'm afraid I don't really know what you mean. Sorry! I don't have a strong background in math. — Jason, Jan 20 '13 at 05:52

score 3 · Accepted Answer · answered Jan 20 '13 at 05:51

3

Fundamental Theorem of Arithmetic

Your number factors to $2^{60}$

You can use the factorization however you'd like to create a smaller number of numbers by multiplying factors together.

Regards

answered Jan 20 '13 at 05:51

Amzoti

56,093

Will I be able to generate any number this way? Like a 1000-digit long sort of random number? – Jason Jan 20 '13 at 05:53
As long as the 1000-digit number is not prime. Regards – Amzoti Jan 20 '13 at 05:55
Also note, your number could be made up of many small primes or few large ones. For example, just two 500-digit primes, so that would be the smallest factorization. Regards – Amzoti Jan 20 '13 at 06:12
Great, quick, observation! – amWhy May 07 '13 at 02:15

score 2 · Answer 2 · answered Jan 20 '13 at 05:41

Given $x_0$ you are trying to find $x_1$ and $y_1$ such that $x_0={y_1}^{x_1}$. And then you want to repeat the process with $x_1$. Most often this process has only the trivial solution of $y_1=x_0$ and $x_1=1$. Otherwise you can attempt the following:First: Find the prime factorization of $x_0={P_1}^{\alpha_1}\cdots{P_n}^{\alpha_n}$. Second Step: Find GCD of exponents $\alpha_1 \cdots \alpha_n$. This will be your $x_1$. Now you repeat the process.

score 1 · Answer 3 · answered Jan 20 '13 at 05:55

If it is hard to find the factorization of the number into primes, then you can instead test whether it is a perfect square, cube, 5th power, 7th power, etc. There are efficient ways to do that --- a websearch for "integer square root" will get you started. If your number is $n$, and it turns out to be a perfect square, say, $n=m^2$, then you look at $m$, testing to see whether it is a square cube, etc.

For your particular number, this approach would find $n=m^2$, $m=p^2$, $p=q^3$, $q=2^5$, from which you can put together your short representation.

How can we represent any number as a series of exponents?

3 Answers3