# “Encode” a single digit in a multi-digit number in the smallest way possible

This may have more to do with computing than Mathematics in its application, however this has been giving me a headache for some time and I see no other recourse than to ask...

Given a natural integer T > 9 (and probably between 1,000 and 1,000,000,000), and a choice N in {0,1,2,3,4}, provide two algorithms (encoding and decoding):

• One which take T and N as inputs and outputs R, a number which has no more digits than T. [encoding]

• The other which takes an (encoded) number R and outputs the original (unencoded) T and N. [decoding]

The complexity of the algorithms should at best allow to be implemented by modern computing. Apart from that, everything and anything is allowed :).

As a side note, do advise me if this is impossible.

-
What is N supposed to do in both algorithms? – J. M. Dec 20 '10 at 10:36
The problem is one of computing and I will not go into these details here. Basically, one must encode T and N together such that the result R is no longer than T and that T and N can be retrieved later from R uniquely. – Félix Saparelli Dec 20 '10 at 10:41
See also the closely related question math.stackexchange.com/q/3419/242 – Bill Dubuque Dec 20 '10 at 14:32

## 1 Answer

This is impossible for the same reason a compression algorithm that reduces the size of every file is impossible. Suppose $T$ has $k$ decimal digits. There are $9\times10^{k-1}$ possible values of $T$, and $5$ possible values of $N$, making $45\times10^{k-1}$ possible $(T,N)$ pairs. But since you're only allowed up to $k$ digits in $R$, there are only $10\times10^{k-1}$ possible values of $R$ to encode them in. So no matter what you do, you won't be able to decode $R$ back into $T$ and $N$.

-
Yes, that's what I thought. I started playing with factorials and saw a compression possibility... however it seemingly will not work on small numbers and I do not have the time to either prove it or leave my computer running to compute an example on large (>10^16) numbers. Thanks! – Félix Saparelli Dec 20 '10 at 10:54
@passcod: The same argument works for any number of digits. See my edited answer. – Rahul Dec 20 '10 at 11:11