0
$\begingroup$

Wondering what the way of producing the shortest length string form of the natural numbers $\mathbb{N}$. I am thinking about this in terms of a binary representation (base 2 representation), but I think I could figure that out starting from a standard base 10 representation. It seems like this has something to do with polynomial equations, so I started with that. (Not totally sure I'm doing it right)....

$1 = 0^1$

$2 = 2^1$

$3 = 3^1$

$4 = 2^2 = 4^1$

$10000 = 10^4 = 100^2 = 10000^1$

$1000000 = 10^6$

At larger numbers it becomes apparent that you can represent them with smaller "strings" than the original number. So 1000000 is 7 digits, but $10^6$ is only 3. If the number was large like $10^{50}$ then it would be $10000000000000000000000000000000000000000000000000000...$, so there is a big gain.

Some other thoughts...

For even larger numbers you can perhaps start nesting the exponents, so $10^{50^{50}}$, and gain an even larger advantage.

Basically I would like to know if there are any equations or systems for figuring out the ideal "smallest" representation of the number as a polynomial equation, where the number could be represented as any base. So $1000000$ is better represented as the more compact $10^6$ since it's only 3 digits instead of 7. But I don't see any equations here on how to figure this out (yet).

$\endgroup$
  • $\begingroup$ If there is such an algorithm then it implies there is a way to quickly factor the product of two large primes which is NP-hard. Therefore this problem is at least NP hard. $\endgroup$ – cr001 Feb 12 at 8:49
  • $\begingroup$ Didn't you ask it about a week ago, and someone rightfully stated that you still need at least $\log n$ bits to represent numbers from $1$ to $n$? Which leads to conclusion, that some of the numbers use more bits to be represented, than they do now in any system, that succeeds in saving bits for representing $10^{50^{30}}$. $\endgroup$ – dEmigOd Feb 12 at 10:33
  • $\begingroup$ Google "Kolmogerov-complexity". There are infinite many numbers that cannot be expressed "way shorter" than by simply printing it. But there is no algorithm to determine the complexity in general because this would imply that the halting problem is solveable which is not the case. $\endgroup$ – Peter Feb 12 at 13:35
  • $\begingroup$ If you choose , lets say, a $10^9$-digit number randomly, the probability that it can be significantly compressed (lets say, at $90$% of the original length) is almost $0$. $\endgroup$ – Peter Feb 12 at 13:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.