Digit Sum Sequences

A daily puzzle from @mathematrix has as its solution a "digit sum sequence": each new term is created by adding the sum of digits of the previous number. So, for example, starting from 1 we get the sequence

1, 2, 4, 8, 16, 23 (=16 + 7), 28 (=23 + 5), 38 (=28 + 10), 49, 62, 70, 77, 91, 101, 103, 107, 115, 122, ...

This is A004207 in the Online Encyclopedia of Integer Sequences.

Some numbers, like 64, have no predecessor in a digit sum sequence. But if we compute the digit sum sequence starting from 64 we get 74, 85, 98, 115, ... which intercepts the sequence above at 115.

We might start to wonder: must every digit-sum sequence intercept the one that starts with 1? Or is there a digit-sum sequence that does not intercept A004207?

If we look at the numbers above, none of them are divisible by 3. We can easily prove that this must be the case. It is well known that if a number is divisible by 3, then its digit-sum is also divisible by 3. This is because 10 mod 3 = 1, so that dividing a number ... + c*10^2 + b*10 + a by 3 gives the same result as dividing ... + c + b + a by 3. But that gives us a more general result: x mod 3 and (the sum of digits of x) mod 3 are equal. But modulo 3, 1+1 = 2, and 2 + 2 = 1, so a number and its digit-sum cannot sum to a multiple of 3 if they don't start out summing to 3.

So, we have another digit-sequence starting from 3 which never intercepts the one above:

3, 6, 12, 15, 21, 24, 30, 33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, 147, 159, 174, ...

This too is in OEIS as A016052. A close look at this sequence shows that no digit-sum is divisible by 9, so we can use reasoning similar to that above. Modulo 9, the number and the sum of its digits are equal, but there are more cases to consider for non-zero residues:

1+1 = 2
2+2 = 4
3+3 = 6
4+4 = 8
5+5 = 1 (mod 9)
6+6 = 3 (mod 9)
7+7 = 5 (mod 9)
8+8 = 7 (mod 9)

So, A016052 doesn't contain any numbers divisible by 9. That gives us a third sequence, which is A016096.

9, 18, 27, 36, 45, 54, 63, 72, 81, 90, 99, 117, 126, 135, 144, 153, 162, 171, 180, 189, 207, 216, 225, ....

These three sequences are sufficient. Every number's digit-sequence must intersect one of the three sequences starting with 1, 3 or 9.

In "The Mathematics of the New Self Numbers" (link goes to an annotated scan from the OEIS) the Indian mathematician D. R. Kaprekar studied these sequences and proved several additional results. One of the things he studied was "self numbers" like 64, which have no predecessor in a digit sequence. The collection of self numbers (or "Colombian numbers") is listed in the OEIS, as A003052:

1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97, 108, 110, 121, 132, 143, 154, 165, 176, 187, 198, 209, 211, 222, 233, 244, 255, 266, 277, 288, 299, 310, 312, 323, 334, 345, 356, 367, 378, 389, 400, 411, 413, 424, 435, 446, 457, 468, 479, 490, 501, 512, 514, ...

Additional references to digit-sum sequences and self numbers can be found there.