$\DeclareMathOperator{\river}{river}\DeclareMathOperator{\leadingsum}{ls}\DeclareMathOperator{\digitsum}{ds}\newcommand{\qed}{\square} $A 1999 British Informatics Olympiad question asks about recursively-defined integer sequences called (digital) rivers. In any sequence, the number following $n$ is $n$ plus the digit sum of $n$ (in base $10$). By $\river k$, we mean the sequence with first term $k > 0$. Two rivers meet when they have terms in common. (All formalised below in case you care.)

Let's consider $\river 173$ for example. After $173$ comes $173+1+7+3=184$, after $184$ comes $184+1+8+4=197$, after $197$ comes $197 + 1 + 9 + 7 = 214$, and so on.

We find that $\river 91 = (91, 101, 103, \dotsc)$ meets $\river 100=(100, 101, 103, \dotsc)$, and that they both meet $\river 173$.

The question asserts the following without proof (and does not ask candidates for a proof).

Claim: All rivers eventually meet $\river 1$, $\river 3$ or $\river 9$.

We'll agree to call these three the main rivers. (One may calculate that $\river 173$, $\river 91$ and $\river 100$ all meet $\river 1$). My attempts to write a proof of the claim have yielded only partial progress (details below). I've asked others in my department to no avail and so I'm casting the net wider.

I am grateful for any insight you can shed and any literature references you may think relevant. I am equally content to see this attacked with elementary tools as with sledgehammers. I also include an alternative characterisation of "$n$ plus the digit sum of $n$", in case it helps. Many thanks in advance!

For the avoidance of doubt, here are some formal definitions.

Any positive integer $n$ has a unique base-$10$ representation $ \sum_{j=0}^\infty 10^j a_j $, where each $a_j \in \{0,1,2, \dotsc, 9\}$. In this representation, the digit sum of $n$ is $\digitsum n \mathrel{:=} \sum_{j=0}^\infty a_j$. (The digit sum is not to be confused with what others call the "digital root".) We define $f(n) \mathrel{:=} n + \digitsum n$, and then $\river k \mathrel{:=} (f^k(n))_{k \geq 0}$.

We say $\river k $ meets $\river k' $ if there exist $J,J' \geq 0$ with $f^J(k)=f^{J'}(k')$.

The following simple argument shows that $\river 1$, $\river 3$ and $\river 9$ are distinct (and any river meets at most one of them). Recall that the doubling map $x \mapsto 2x \pmod 9$ on $\{1,2,\dotsc,9\}$ permutes elements as follows: $9 \mapsto 9$, $3 \mapsto 6 \mapsto 3$, $1 \mapsto 2 \mapsto 4 \mapsto 8 \mapsto 7 \mapsto 5 \mapsto 1$. Observe in particular that $1$, $3$ and $9$ lie on distinct cycles.

Lemma 1. $k \equiv \digitsum k \pmod 9 $.

Proof 1. $ k = \sum_{j=0}^\infty 10^j a_j \equiv \sum_{j=0}^\infty 1^j a_j =\sum_{j = 0}^\infty a_j = \digitsum k $. $\qed$

Lemma 2. $f(n) \equiv 2n \pmod 9$.

Proof 2. For any $j >0$, $f(n) = n + \digitsum n \equiv n + n = 2 n \pmod 9$ by Lemma 1. $\qed$

Lemma 3. The rivers $\river 1$, $\river 3$, $\river 9$ are distinct.

Proof 3. Reduce the entries of these rivers modulo $9$, and find that they are the periodic sequences $(1,2,4,8,7,5,1,\dotsc)$, $(3,6,3,\dotsc)$ or $(9,9,\dotsc)$, by Lemma 2. None shares any entries with another. $\qed$

Consequently, $\river k$ can meet at most one main river, depending on which cycle of the doubling permutation contains the residue of $k$ modulo $9$.

I'll end with an alternative characterisation of $f(n)$.

First, I need to define the number $\operatorname{tr} n$ of trailing 9s of $n$, which uses the base-$10$ representation of $n$ as above. Informally, it's the number of $9$s at the end of $n$, so that for example $\operatorname{tr} 78 = 0$, $\operatorname{tr} 79 = 1$, $\operatorname{tr} 99 = 2$, $\operatorname{tr} 7999 = 3$. Formally, $$ \operatorname{tr}\left(\sum_{j=0}^\infty 10^j a_j\right) \mathrel{:=} \max\{r \geq 0 \colon a_j = 9 \text{ for all } j \in \{0,1, \dots, r\}\}\text{.} $$ Equivalently, $$ \operatorname{tr} n \mathrel{:=} \max\{j \geq 0 \colon n+1 \text{ is a multiple of }10^j\}\text{.} $$

Lemma 4. $\digitsum(n+1)-\digitsum n = 1 -9\operatorname{tr} n$.

Proof 4. What happens to the digits when we add $1$ to $n$? The rightmost non-$9$ digit is increased by $1$, and all the trailing $9$s to the right of it are reduced from $9$ to $0$. Remaining digits are unaffected. The result follows. $\qed$

Lemma 5. $f(n+1)-f(n) = 2-9\operatorname{tr} (n)$.

Proof 5. Follows trivially from Lemma 4. $\qed$

Next, define the leading sum of an integer $n>0$ to be $\leadingsum n \mathrel{:=} \sum_{j=1}^\infty \left\lfloor \frac{n}{10^j}\right\rfloor$ (beware: indices $j$ start at $1$, not $0$). Some examples: $\leadingsum 12345 = 1234 + 123 + 12 + 1 = 1370$ and $\leadingsum 173 = 17 + 3 = 20$.

Lemma 6. $ \sum_{j=1}^{n-1} \operatorname{tr}(j) = \leadingsum(n)$.

Proof 6. There are $\left\lfloor \frac{n}{10}\right\rfloor$ multiples of $10$ that are equal to or less than $n$ and each contributes $1$ to this sum. There are $\left\lfloor \frac{n}{100}\right\rfloor$ multiples of $100$ that are equal to or less than $n$ and each contributes a further $1$. Etc. The result follows. $\qed$

Lemma 7. $f(n) = 2n - 9\leadingsum n$.

Proof 7. We can form a telescoping sum $$f(n) - f(1) = \sum_{j=1}^{n-1} f(j+1) - f(j) = \sum_{j=1}^{n-1} (2-9\operatorname{tr}j) = 2(n-1) - 9\sum_{j=1}^{n-1}\operatorname{tr} j = 2(n-1) -9 \leadingsum n\text{.}$$ To this, we simply add $f(1)=2$ and we're done. $\qed$

EDITS: typos