## An Unusual Sequence

From the 2003 Tournament of the Towns:

Each term in a sequence of positive integers is obtained from the previous term by adding it to its largest digit. What is the greatest possible number of successive odd terms in such a sequence?

Another curious problem from Russia. Upon first reading, it seems very difficult to gauge just how tough the problem is. If you were told it was easy, or extremely challenging, you might believe either claim.

Experimenting with small numbers might suggest that the answer is 2.

21, 23, (26)

43, 47, (54)

61, 67, (74)

Things get more interesting with three-digit numbers:

625, 631, 637, (644)

By now you might have figured out what’s really going on: for two successive terms to be odd, their difference must be even. So we somehow need to force the largest digit to be even for as long as possible.

Actually, this is harder than it seems. What tends to happen is you write down an odd number containing a large even digit, like 483. Then the sequence proceeds: 483, 491, (500), and we’re stuffed. Or 623, 629, (638), and again we’re undone very quickly.

Here is where the problem lies: if you add to the previous term its largest digit, then unless there is a carry, the rightmost digit of the next term will become the largest digit. We need this digit to be odd, but then the following term will be even, ruining our sequence.

So we need to continually carry for as long as possible, during which time the rightmost digit will continue to fall, and then the carrying will stop. It turns out the best we can do is this:

807, 815, 823, 831, 839, (848).