You'd definitely have to be more careful than I was in my post! But I think it should be possible to make it work via something like always using either one or

You'd definitely have to be more careful than I was in my post! But I think it should be possible to make it work via something like always using either one or two initial letters. The algorithm I'm thinking of is: 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.