1. Given n, write aaaaaaa n where the number of a's is equal to the length of n.
2. If the number of a's is 1 or 2, stop.
3. Let n' be the number of a's.
4. Write bbbbb n' n where the number of b's is equal to the length of n'.
5. If the number of b's is 1 or 2, stop.
6. ...continue until the number of initial letters is 1 or 2.
I think that algorithm is mostly well-defined and only produces one possible output for each input number. So let's see if I can give a good proof-ish argument that it sorts correctly.
Suppose n <= m, then length(n) <= length(m).
Case 1: If their lengths are equal, then in step 1, they are written as
aaaaaaaaa n
aaaaaaaaa m
where the number of a's are the same. Now the rest of the algorithm is the same for both numbers, since they have the same number of a's, so they get written as the exact same prefix followed by the number. Since they have the same length, the smaller one sorts first.Case 2: Now suppose length(n) < length(m), and further suppose length(n) <= 2. Then in step 1, they are written as, for instance,
a n
aa m
or something like aa n
aaaa m
Now any encoding of m in further steps will start with the letter b or greater, which sorts below "aa n".Case 3: Now suppose length(n) < length(m), but further suppose length(n) > 2. Then in step 1, they are written as
aaaaaaaaa n
aaaaaaaaaaa m
Now n will sort before m as long as the encoding of a smaller string of a's sorts before the encoding of a longer string. Let n' = length(n) and m' = length(m). We know that n' < m' and we want to prove that the encoding of n' sorts before the encoding of m'. This is true recursively by the same 3-case argument as above, though I haven't really formalized it well here.For example, if length(n') = length(m'), then they both get written in the next step as
bbbb n' n
bbbb m' m
which is just like Case 1 above. Otherwise, they get written something like b n' n
bbb m' m
which is just like Case 2 above. Otherwise, they get written bbbbb n' n
bbbbbb m' m
which is like Case 3 above, and requires us to recurse again.
First, imagine we store the number in the form
where the number of a's is equal to the length of the number. This encoding scheme works for the same reasons as discussed in the article. And it only takes 2*(length of original number)+1 characters.But now, we can do better by applying the same encoding scheme to the 'aaaaaaaaaaa'. That is, suppose the original number is 295 digits long. The number 295 is 3 digits long. So we store the number with 3 b's, as:
OK, but what if we want to store a number that's 4,000,000,000 digits long? This would look like And that's a bit wasteful. If there are more than two b's, then we can recursively apply the encoding to the b's. There are 10 b's, and 10 has two digits, so we get And so on. (We won't ever have hard drives that can make use of letters e and above, so it can probably stop there.)So the encoding schemes look like