square of digits - why does it always contain 1 or 89

Question

I attempted project euler problem 92, while I passed it, my solution works, but had just...awful performance. So I would like to try again tomorrow. In the meantime understanding why the iteration that is used in that problem always produces a sequence which contains a 1, or 89 and why never both, would be a good start.

The problem asks to form a number chain by summing the square of the digits of the root of the chain, and terminating the process only when the chain is no longer a set, by containing a duplicate value.

Answer 1

First Look at the Sequence:

The problem text does not explain what a number is, we assume it to be a natural number $x \in \mathbb{N}$. We start the sequence at index $0$, thus at the $n$-th step, for $n \in \mathbb{N}_0$, one takes the decimal representation of the current sequence number $x_n$: $$ x_n = (d_{m_n}^{(n)}\cdots d_0^{(n)})_{10} = \sum_{k=0}^{m(n)} d_k^{(n)} 10^k \quad (d_k^{(n)} \in \{0,\ldots 9\}) $$ It consists of $(m(n) + 1)$ digits $d_k^{(n)}$, $m_n \in \mathbb{N}_0$.

Estimating the Lenght of the Digit String:

Using that the all 9-digits string of length $m_n$ represents a value smaller than $10^{m_n+1}$: $$ x_n < 10^{m_n + 1} \Rightarrow \log_{10}(x_n) < (m_n + 1) $$ we get the length of the representation in terms of its value: $$ m_n = \left\{ \begin{array}{cl} 0 & \mbox{for } x_n = 0 \\ \lfloor \log_{10}(x_n) \rfloor & \mbox{for } x_n > 0 \\ \end{array} \right. $$

The Iteration Step:

The next element in sequence is \begin{align} x_{n+1} &= F(x_n) \\ &= \sum_{k=0}^{m_n} \left(d_k^{(n)}\right)^2 & \le 81(m_n + 1) \end{align}

This is a plot of $F(x)$ (blue colour):

it uses $$ d_k(x) = \left\lfloor \frac{x - \left\lfloor x/10^{k+1}\right\rfloor 10^{k+1}}{10^k}\right\rfloor $$ to calculate $F(x)$.

If $x_n \ne 0$ we have $$ x_{n+1} = F(x_n) \le 81 (\lfloor \log_{10}(x_n) \rfloor + 1) $$ this boundary is plotted in orange colour in the image above, and $$ m_{n+1} \le \log_{10}(81) + \log_{10}(m_n+1) $$ The series is falling if $x_{n+1} < x_n$. From the above we can take that this happens for $x_n > 3\cdot 81 = 243$. (The identity is plotted in green colour, also horizontal and vertical lines for the value $243$).

Conclusions:

So we have two regions:

1. $x_0 \in I = [1, 243]$ then $x_n \in I$.
2. $x_0 > 243$, number $x_n$ will decrease until it enters $I$ and stays there. Might need $(x_n - 243)$ steps at most.

What happens in $I$ might be further analyzed, but the easiest way is to calculate those 243 cases and tabulate them.

Exploring the Numbers:

To my surprise I got these cases of final values:

1 -> 1
2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4
3 -> 9 -> 81 -> 65 -> 61 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16 -> 37
5 -> 25 -> 29 -> 85 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16 -> 37 -> 58 -> 89
15 -> 26 -> 40 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16
20 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20
38 -> 73 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16 -> 37 -> 58
42 -> 20 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42
77 -> 98 -> 145 -> 42 -> 20 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145

and not just $1$ and $89$.

I have assumed that "arrive at" means that the final number, which is the first repeated number, is meant by this.

The result however suggests that "arrive at" means that the sequence will take this value for some index. I would expect this to be the case before the repetition happens, but who knows.

In the above found cases, each series has 89 as a member, from this spans a cycle $$ 89 \to 145 \to 42 \to 20 \to 4 \to 16 \to 37 \to 58 \to 89 \quad (*) $$ The listed finalists are members of this cycle.

The interesting bit now is if there ore other cases happening in the interesting range of 10 M numbers, or if there are just cycles having either value 1 or 89 for some index.

Cycles:

The cycle structure IMHO boils down to $F$ having fixed points $x^*$ of various order $r$: $$ F^{r}(x^*) = x^* $$ where $F^r = \underbrace{F \circ F \circ \cdots \circ F}_{r {\small \mbox{ applications of }} F}$.

Note: What I call a "$r$-th order fixed point" is just a fixed point of the iteration $F^r$, I lack a better term.

Here is the only fixed point (red dot) of $F$ in $I$:

Fixed points of $F$ are only possible on $[1,99]$, but except for $x=1$ all candidates (black dots) do not hit the identity line.

Note that the orange boundary lines are honored by $F$, the software does a bit of overplotting, interpolating the discrete function values, see $F99 = (99, F(99))$ and $F09 = (9, F(9))$ for example.

And here are the remaining $8$-th order fixed points (magenta dots) of $F$:

Shown is the entry into the $8$ iterations loop from start value $x=145$. Entering from another start value beyond a magenta dot will lead to another $8$-th order fixed point of the cycle within $8$ hops. The cycle itself is the one above marked with $(*)$.

So, why does it always contain $1$ and $89$?

Above, arguments were given why $I$ is the place to search for fixed points of $F$, which are, where the loops close. $I$ itself was searched via computer for fixed points of various orders and the $9$ ones above were found. Thus we can even claim that

Every sequence (for $F$) will eventually run into $1$ or $4, 16, 20, 37, 42, 58, 89, 145$!

Because these are all $r$-th order fixed points of $F$.

Answer 2

If I read the question correctly, I think it is in the spirit of Project Euler to answer. You are asking how to be sure that every number either goes to $1$ under the operation "sum the squares of the digits" or enters the loop that includes $89$ (and $145, 42, 20, 4, 16, 37, 58,$ any of them could have been chosen as well). First, once you enter a loop you can never leave, so you cannot go from $89$ to $1$ or the reverse. Second, if we define $f(n)$ as the sum of the squares of the digits of $n$ you show that for large enough $n, f(n) \lt n$. You need to observe that the number of digits of $n$ is about $\log_{10} n$, so $f(n)$ is (roughly) less than $81 \log_{10} n$, which will be less than $n$ if $n$ is large enough. You then try all the $n$ that you haven't proven will have $f(n) \lt n$ and show they all enter one of these two cycles. I didn't make all the details precise because I think it is in the spirit of exploration to fill them in.