Shrink a Chain of Decimal Digits Assume that we have a 100-digit number, made of 0 to 9. Is there a way we can actually 'shrink' this number?
As a first thought, I tried to decompose the number to prime factors. But, in many cases, the space required to save the resulting prime numbers, is even more.
I'm looking for mathematical approaches.Any ideas are welcome. Thanks.
PS: I mentioned the "100-digit" just to imagine a large chain of decimal digits. You may come up with an approach which only works for "54-digit" numbers. It's okay. Just give me that!
 A: You can shrink it if you use more symbols. For instance, a 100-digit number is only about 83 digits long if written in hexadecimal (base 16, with digits 0123456789ABCDEF).
But if you are only allowed to use the digits 0-9, then there is no compression method that will shrink all 100-digit numbers. This is simply because the number of distinct strings of 99 or fewer digits is less than the number of 100-digit numbers.
If you know in advance that certain kinds of numbers are more likely than others, then you might be able to devise a compression method that shrinks the more likely numbers at the expense of making the less likely numbers longer. (This is how compression programs like WinRar work.) Then your numbers will be shorter on average. For instance, suppose you know somehow that your numbers have a 50% chance of being square numbers. Then you can encode a square number $n^2$ as $0n$, and a non-square number $m$ as simply $m$ (with no leading zero). Now the avegare length of an encoded number is about 75 digits.
By the way, the first paragraph is not strictly true: you can shrink number representations slightly by using leading zeroes. This is because the length of your string can also carry information. So you can use e.g. 123, 0123, and 00123 to encode different numbers. But you will gain less than a single digit on average with such a scheme.
