Fixed points of iterates of a certain map $\Bbb N \to \Bbb N$

Question

I have stumbled onto chains of numbers that are interesting in that, when they are split up into their digits, summed, squared, and repeating some number of times, yield the original number.

This definition is a bit wordy, so here are examples:

• $\{169,256\}$ is a chain, since $169\to(1+6+9)^2=256$ and $256\to(2+5+6)^2=169$. This chain has a length (cardinality) of two.
• $\{256,169\}$ is also a valid chain. (Pretend the use of the curly brackets denotes a chain and not a set, as the two would be equal otherwise.)

There is a chain of length $1$, that is, $\{81\}$. I believe $\{81\}$ to be the only unary chain.

Let $C_n$ be the set of all chains with a length of $n$. I believe $C_1$ to be a finite set, and that $\|C_1\|=1$.

My question is twofold:

1. I believe that for $n>1$, $C_n$ is infinite in carnality, since there are an infinite amount of positive integers. Is this belief correct?
2. Let $C_n(d)$ be the set of chains whose largest members is at most $d$ digits and whose length is $n$. I believe that for all $d<\infty$ and for all all $n$, $C_n(d)$ is finite, if not empty. Is this belief also correct?

Answer 1

Let $\phi: \Bbb N \to \Bbb N$ denote the map that applies the operation that breaks a natural number into the sequence of its digit, forms their sum, and squares the result. We are looking precisely for fixed points of iterates $$\phi^k = \underbrace{\phi \circ \cdots \circ \phi}_k,$$ $k > 0$, of $\phi$.

Now, a number $n \in \Bbb N$ has $\lfloor \log_{10} n + 1 \rfloor$ digits, each of which is at most $9$, and so $$\phi(n) \leq (9 \lfloor \log_{10} n + 1 \rfloor)^2 \leq 81 (\log_{10} n + 1)^2.$$

As a function of $n$, the expression on the r.h.s. of the equality is concave in $n$, and so we have $\phi(n) < n$ when $n$ is larger than the largest solution to $\phi(x) = x$ (here, we regard $\phi$ as a function of $\Bbb R_+$), namely, $$\frac{324}{(\log 10)^2} W\left(-1, -\frac{\log 10}{18 \sqrt{10}}\right)^2 < 1391 ,$$ where $W(-1, x)$ is a particular (nonprincipal) branch of the Lambert $W$-function. So, for $n \geq 1391$, $\phi^k (n) < n$ for all $k > 0$, and hence no chain contains a number $n \geq 1391$. (In fact, this bound turns out to be crude: The largest $n$ for which $\phi(n) > n$ is $n = 399$.)

Thus, there are finitely many chains, so the claim in (1) is false. The claim in (2) is true, for the simple reason that there are only finitely many numbers with at most $d$ digits.

Anyway, since every element of a chain must be a square, this quickly leads to a complete list of chains, which, up to reordering and to discarding concatenations of a chain with copies itself. are just the two identified in the question, namely $(81)$ and $(169, 256)$, and the trivial chain $(1)$. In fact, since the map $\phi$ maps each of the sets $\{0, 3, 6\}$, $\{1, 8\}$, and $\{2, 4, 5, 7\}$ of residues modulo $9$ to themselves, we see that a sequence $\{n, \phi(n), \phi^2(n), \ldots\}$ stabilizes in the chain $(1)$ iff $n \equiv 1, 8 \bmod 9$, in the chain $(81)$ if $n \equiv 0 \bmod 3$, and in the chain $(169, 256)$ otherwise, and probably this is easy to prove

Answer 2

Note that an $k$ digit number $N$ is $10^{k-1}\le N \lt 10^k$ and the square of the sum of the digits is $\le 81k^2$ (all digits equal to $9$) so if $81k^2\lt 10^{k-1}$ applying your process will reduce the number of digits.

So for a five digit number your process gives a maximum of $2025$ for $99999$. You won't ever get bak to a five digit result. So you only need to search a finite space and there will be a finite set of answers.

You can get a better estimate which will reduce the search space further.