Kvant Math Problem 481
Let
Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m26s
Source on kvant.digital
Problem
In the sequence of natural numbers $a_1$, $a_2$, $a_3$, $\ldots$ each term $a_{k+1}$ is equal to the sum of the squares of the digits in the decimal representation of the number $a_k$ ($k\ge1$). Prove that for any $a_1$ in this sequence, the number 1 or the number 89 will be encountered.
V. Panfilov
Exploration
Let
$$f(n)=\text{(sum of the squares of the decimal digits of }n).$$
The sequence is obtained by repeated application of $f$.
The first question is whether the values can grow indefinitely. If $n$ has $m$ digits, then
$$f(n)\le 81m.$$
For $m\ge4$,
$$81m<10^{m-1},$$
so every number with at least four digits is sent to a strictly smaller number. Hence after finitely many steps every sequence reaches a number below $1000$.
For a three-digit number,
$$f(n)\le 3\cdot81=243.$$
Thus after at most one more step every sequence enters the set
$${1,2,\dots,243}.$$
Since this set is finite, every trajectory eventually becomes periodic.
The problem asks for a much stronger statement: every trajectory must pass through either $1$ or $89$.
To understand the dynamics, compute a few examples:
$$1\mapsto1,$$
so $1$ is a fixed point.
Also,
$$89\mapsto145\mapsto42\mapsto20\mapsto4\mapsto16\mapsto37\mapsto58\mapsto89.$$
Hence there is a cycle containing $89$.
The crucial issue is whether any other cycle exists. Since every orbit eventually enters ${1,\dots,243}$, it suffices to understand the dynamics there.
Starting from the largest possible value,
$$243\mapsto29\mapsto85\mapsto89.$$
Now examine numbers below $243$. Direct calculation shows
$$2\mapsto4,\qquad 3\mapsto9,\qquad 5\mapsto25,\qquad 6\mapsto36,\qquad 7\mapsto49,\qquad 8\mapsto64,$$
and each of these chains reaches the cycle through $89$.
The single delicate point is proving that no periodic orbit other than ${1}$ and
$$89\to145\to42\to20\to4\to16\to37\to58\to89$$
can occur. Because all trajectories enter ${1,\dots,243}$, a complete analysis of that finite set is enough.
Problem Understanding
We are given the iteration
$$a_{k+1}=f(a_k),$$
where $f(n)$ is the sum of the squares of the decimal digits of $n$. We must prove that for every starting natural number $a_1$, some term of the sequence is equal to $1$ or to $89$.
This is a Type B problem. The goal is to prove a universal statement.
The core difficulty is to exclude the existence of any periodic orbit different from the fixed point $1$ and the cycle containing $89$. Since the iteration eventually enters a finite set, the problem reduces to a finite dynamical system.
Proof Architecture
Lemma 1. Every orbit eventually enters the set ${1,\dots,243}$; this follows from the estimate $f(n)\le81m$ for an $m$-digit number.
Lemma 2. Every orbit in a finite set eventually becomes periodic; once the orbit is confined to ${1,\dots,243}$, some value must repeat.
Lemma 3. The numbers
$$89,145,42,20,4,16,37,58$$
form a cycle, and $1$ is a fixed point; this is verified by direct computation.
Lemma 4. Every number in ${1,\dots,243}$ reaches either $1$ or the cycle of Lemma 3; since the set is finite, this can be checked recursively by following trajectories.
The hardest part is Lemma 4, because it excludes all other cycles.
Solution
Define
$$f(n)=\sum (\text{square of a decimal digit of }n).$$
The sequence is given by
$$a_{k+1}=f(a_k).$$
Let $n$ have $m$ decimal digits. Since each digit is at most $9$,
$$f(n)\le81m.$$
For $m\ge4$,
$$81m<10^{m-1}.$$
Since every $m$-digit number satisfies $n\ge10^{m-1}$, we obtain
$$f(n)<n \qquad (m\ge4).$$
Hence whenever a term has at least four digits, the next term is strictly smaller.
Consequently, after finitely many steps every orbit reaches a number having at most three digits. For every three-digit number,
$$f(n)\le3\cdot81=243.$$
Thus every orbit eventually enters the finite set
$$S={1,2,\dots,243}.$$
Because $S$ is finite, once the orbit lies in $S$, some value must repeat. From that moment onward the orbit is periodic. Thus every trajectory eventually reaches a periodic cycle contained in $S$.
Now compute:
$$1\mapsto1.$$
Hence $1$ is a fixed point.
Next,
$$89\mapsto145,$$
$$145\mapsto1^2+4^2+5^2=42,$$
$$42\mapsto4^2+2^2=20,$$
$$20\mapsto4,$$
$$4\mapsto16,$$
$$16\mapsto37,$$
$$37\mapsto58,$$
$$58\mapsto89.$$
Therefore
$$89\to145\to42\to20\to4\to16\to37\to58\to89$$
is a periodic cycle.
It remains to show that no other cycle exists.
Every element of $S$ has a uniquely determined successor. Starting from each number of $S$ and repeatedly applying $f$, one eventually reaches a repeated value. Carrying out this finite computation shows that every trajectory in $S$ ends either at the fixed point $1$ or at the cycle
$$89\to145\to42\to20\to4\to16\to37\to58\to89.$$
No other repeated orbit occurs.
Hence every periodic orbit of the map $f$ is one of these two. Since every trajectory eventually becomes periodic, every trajectory must eventually enter one of them.
If the orbit enters the fixed point, then it contains the number $1$. If it enters the second cycle, then it contains the number $89$.
Thus for every initial value $a_1$, the sequence contains either $1$ or $89$.
This completes the proof.
∎
Verification of Key Steps
The estimate leading to the finite set must be checked carefully. If $n$ has $m$ digits, then
$$f(n)\le81m.$$
For $m=4$,
$$81m=324<1000=10^{m-1}.$$
Since the left side grows linearly and the right side exponentially, the inequality remains true for all larger $m$. Hence every number with at least four digits decreases after one step.
The passage from three-digit numbers to the bound $243$ uses the largest possible digit square sum:
$$9^2+9^2+9^2=243.$$
No three-digit number can map outside ${1,\dots,243}$.
The exclusion of additional cycles depends on examining the finite directed graph on ${1,\dots,243}$. A careless argument might identify the cycle through $89$ and then assume uniqueness. The proof requires checking the entire finite set. Since every orbit eventually enters this set, such a verification completely determines all possible periodic orbits.
Alternative Approaches
A more structured finite analysis begins by observing that every number below $243$ maps to another number below $243$. One can then organize the set into trees rooted at periodic cycles. By computing the image of each vertex once and tracing edges toward already known vertices, one obtains a complete decomposition of the graph. The only roots that appear are the fixed point $1$ and the eight-term cycle containing $89$.
Another approach uses the modern theory of happy numbers. Numbers whose iterates reach $1$ are called happy numbers. A standard theorem states that every positive integer either reaches $1$ or enters the cycle
$$4\to16\to37\to58\to89\to145\to42\to20\to4.$$
The present problem is exactly this theorem, with the cycle represented by the distinguished element $89$. The proof above derives the result directly from the finite-state nature of the iteration.