Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
    
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 5: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 5:52

3 Answers 3

up vote 3 down vote accepted

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

share|improve this answer
    
Will I be able to generate any number this way? Like a 1000-digit long sort of random number? –  Jason Jan 20 '13 at 5:53
    
As long as the 1000-digit number is not prime. Regards –  Amzoti Jan 20 '13 at 5: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 6:12
    
Great, quick, observation! –  amWhy May 7 '13 at 2:15

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.