Let’s examine the following procedure: Start with a finite string of digits and replace each substring consisting of a repeated single digit with the number of digits in that substring followed by the digit of that that is being repeated. Example: 333 would become 33, and 2 would become 12 and 222233333 would become 4253. Starting with 1, and recursively applying this procedure generates the sequence: 1, 11, 21, 1211,… and so on. What is the largest digit that will ever appear in this sequence?

Correct answers to last month’s puzzle:
Arash Ushani
Greg Edelston

(See last month’s puzzle and solution at https://franklyspeakingnews.com/node/159)

——————————————————-
Proof by Arash Ushani:
Just by going a few iterations into the sequence, we can get 1, 2, and 3:

1, 11, 21, 1211, 111221, 312211, …

However, it is impossible to get any digit greater than 3.

Consider each number in the sequence by pairs of digits:

1, [11], [21], [12] [11], [11] [12] [21], [31] [22] [11], …

By definition of the sequence, each pair of digits comprises of two parts: a count (call it n) and a specific digit (call it d). This pair describes how many times the digit d appeared consecutively in the previous sequence number.

Note that in each successive pair [nd] in the number, d must be different, by definition of the sequence. If any two successive d’s were the same, then the two successive pairs should have just be one pair.

For example, we can’t have [53] immediately followed by [23]. Instead of these two pairs, we would have had [73].

This implies that any four consecutive digits, whether they are two pairs (as in [nd][nd]) or split across three pairs (the bold digits in [nd][nd][nd] ), cannot all be the same, because the successive d’s must be different.

Because we can never have 4 or more consecutive digits that are the same, we will never get any digit of 4 or more in the sequence, by definition of the sequence.

Thus, the maximum digit we will get is 3.

——————————————————-
Proof by Ruby Spring:
There will never be more than three digits in a substring, therefore no single digit integer greater than 3 will appear in the sequence.

To prove this I will show that the pattern n1#n2# (where # is the single digit integer from the previous substring being quantified and n1 and n2 are integers quantifying the #s from the previous substring) can’t appear in the sequence. This is because the only possible previous string for this pattern is an unbroken substring of #s, which can only be described using two digits, say, n3#, not as n1#n2#. So the substring n1#n2# where n1 = n2= # (written ####) will also never appear in the sequence.
Similarly, n 1#n2#n3#…nx# can’t exist, and so 3 is the largest single digit integer in the sequence.