My initial thought seems to be actually correct, and the longest chain must be:
Untitpoi posted his answer while I was editing, but I believe our approaches are similar. One such chain is:
Why this is optimal:
Without loss of generality, consider the first number in a chain. If it's largest digit is odd, at the next step we will have an even number. As such, its largest digit must be even. Consider the case where this number is the largest for all but the last number of the chain. We can consider number mod 10, and keep subtracting from there. This yields the following possibilities:
Largest digit 2:
Largest digit 4:
Largest digit 6:
Largest digit 8:
Other starts need not be considered, since they simply start later in the chain.
If we assume this digit is NOT continuously the highest in the chain, but we do constantly have an even highest digit (as required), we consider two cases:
- The highest digit is the last digit. Then, the numbers are even, so this is not possible.
- The highest digit is not the last digit. For this to happen, we would need to subtract more than 10, which is clearly impossible.
As such, we have the case where 8 is always the highest, leading (possibly) to the above chain.
Using the above explanation, it's easy to see to that in base-n, we have a maximum chain length of
Using some number that:
Always has n-2 as the highest digit. This results in a chain with numbers ending in 1, 3, 5, [...], n-5, n-3, n-1, END.
Not sure if I'm getting this right, but... EDIT: This logic is clearly flawed, as indicated in the comments. I'm leaving it here for future reference.
888[...]881 seems to give an infinite number of consecutive odd numbers.
To be clear, there is an infinite number of eights. The next number will be
888[...]865... Eight is always the largest number, and since it's infinitely long, there will be no end. Not for us common folk, anyway, mathematicians will start arguing about types of infinity, I guess...
In addition to my edit: This does give at least a lower bound - Though I have no clue as to how much this can be improved (I'm assuming it can).
The lower bound:
5, with the chain being 881-873-865-857-849-840