7
$\begingroup$

I found an astonishing result in a problem today here !
A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.

For example,

$44 \to 32 \to 13 \to 10 \to 1 \to 1$

$85 \to 89 \to 145 \to 42 \to 20 \to 4 \to 16 \to 37 \to 58 \to 89$

Therefore any chain that arrives at $1$ or $89$ will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at $1$ or $89$.
Why is this true?

$\endgroup$
3
  • $\begingroup$ This is similar to the number of letters of a word in english eventually converging to "four" -> "four" -> "four" and in french to "trois"->"cinq"->"quatre"->"six"->"trois". There are only finitely many possibilities so each sum is going to eventually going to stabilize to a repeating loop. $\endgroup$
    – fleablood
    Commented Sep 19, 2016 at 20:32
  • $\begingroup$ Note that if the chain remains bounded, it must repeat - if bounded by $N$ then after $N$ operations there will be at least one repeat, and since each number in the chain depends only on the one previous number, the whole chain will repeat. If the numbers in the chain were bounded and depended only on the previous four numbers, there would be only a finite number of sequences of four numbers and therefore a repeat. This is occasionally a useful observation. If there is no repeat, the numbers in the chain grow without limit (are unbounded). $\endgroup$ Commented Sep 19, 2016 at 21:34
  • $\begingroup$ It's not that surprising. (a-i)(b+j)=a^2 + b^2 -2ia + 2bj + if=a^2 + b^2$ if $2bj -2ai + ij = 0$ which isn't that rare so it shouldn't be surprising if there were 8 or 9 such values. So two digit number having a chain of 8 and each element of the chain of 8 having a 8 or 9 two digit numbers going into it yeilding about 2/3 of all two digit numbers to the chain and 1/3 to 10 isn't surprising. One would have to calculate to see that is does do it, but it's not a surprising result when you do. $\endgroup$
    – fleablood
    Commented Sep 19, 2016 at 21:45

3 Answers 3

12
$\begingroup$

Let $s(n)$ be the function that adds the square of the digits in $n$.

Note that for $r\geq 3$, and $d_k\in\{0,1,\dots 9\}$ for $k=1,2,\dots, r$ with $d_r\geq 1$, we have that $$n=d_0+\sum_{k=1}^{r-1} d_k 10^k+d_r10^r >d_0^2+\sum_{k=1}^{r-1} d_k^2+d_r^2=s(n)$$ because $10>d_k$ and $d_0 +d_r10^r\geq 1000\geq 9^2+9^2\geq d_0^2+d_r^2$.

Therefore if $n$ has at least three digits then $n>s(n)$. This implies that eventually we will obtain a number of at most three digits. So it suffices to check what happens for the integers in $[1,999]$: it can be verified that given $n\in [1,999]$, then $s^{(k)}(n)\in\{1,89\}$ with $k\leq 11$.

Hence, we may conclude that for any $n\geq 1$ the sequence, after a finite number of steps, will enter in one of the two cycles: $$(1)\quad \mbox{or}\quad (89,145,42,20,4,16,37,58).$$

$\endgroup$
4
  • $\begingroup$ But it converges to exactly one of the two points. That's really astonishing. $\endgroup$
    – maverick
    Commented Sep 19, 2016 at 20:35
  • 4
    $\begingroup$ 89 is not quite so special. Any of the 8 numbers in that cycle would do as well. $\endgroup$
    – B. Goddard
    Commented Sep 19, 2016 at 20:39
  • 1
    $\begingroup$ Oh thats right. Thanks for pointing it out. $\endgroup$
    – maverick
    Commented Sep 19, 2016 at 20:41
  • 3
    $\begingroup$ If it's strictly decreasing for three-digit numbers, it suffices to check what happens to numbers in $[1,99]$. $\endgroup$ Commented Sep 19, 2016 at 20:59
7
$\begingroup$

I suppose you're excluding $0$.

If $x$ has $n$ digits, the sum of squares of the digits of $x$ is at most $81 n$, and that has at most $1 + \log_{10}(81 n)$ digits. Now $1 + \log_{10}(81 n) < n$ if $n \ge 4$, so eventually you get to a number of at most $3$ digits. Check all $999$ positive numbers of at most 3 digits, and you'll find that they all end up at $1$ or $89$.

EDIT: Although not so easy to see immediately, it turns out that the sum of squares of the digits of any $3$-digit number is less than the number, so we can restrict our attention to numbers of $2$ or fewer digits.

$\endgroup$
2
$\begingroup$

Let us observe that, for any function $g: \mathbb{N} \to \mathbb{N}$, if we apply $g$ repeatedly to $n$ we will eventually arrive at a positive integer $k$ such that $g(k) \ge k$. Why? Because if not, then $n > g(n) > g(g(n)) > g(g(g(n))) > \cdots$, but this can only go on finitely long since $g$ lies in the positive integers.

Therefore the same is true of $f$, and it suffices to consider only values of $\boldsymbol{n}$ for which $\boldsymbol{f(n) \ge n}$. Let us search for all such values.

  • First, $n$ must have $3$ or less digits. Others have already proven this, but let $k$ be the number of digits of $n$. Then the sum of the squares of the digits (i.e. $f(n)$) is at most $81k$. On the other hand, $n$ is at least $10^{k-1}$. So $n$ is very large but $f(n)$ is much smaller. Formally, we can say that if $\boldsymbol{k \ge 4}$ then $10^{k-1} > 81k$ so $$ n \ge 10^{k-1} > 81k \ge f(n). $$ Therefore, $f(n) < n$ for all $n$ with four or more digits, i.e. for all $n \ge 1000$. So we can assume $1 \le n \le 999$.

  • Now let's assume $n$ has three digits: $n = 100a + 10b + c$, where $a \ge 1$. We need $a^2 + b^2 + c^2 \ge 100a$, so $$ 100a \le 3 \cdot 9^2 = 243, $$ so $a = 1$ or $a = 2$. But now $100a \le a^2 + b^2 + c^2 \le 4 + 2 \cdot 9^2 = 166$, so $a = 1$. So we need $1 + b^2 + c^2 \ge 100 + 10b + c$, or in other words $b^2 + c^2 - 10b - c \ge 99$. Now $b^2 - 10b < 0$, so the best we can do is $9^2 - 9 < 99$, so this is impossible.

  • So we are left with considering $n = 10a + b$. Now we are simply solving the inequality $a^2 + b^2 \ge 10a + b$, for $0 \le a, b \le 9$. The inequality can be rewritten $$ b(b-1) \ge a(10 - a). $$ This leads to the following solutions for $n$: \begin{align*} a = 0 &\implies n = 1, 2, 3, 4, 5, 6, 7, 8, 9 \\ a = 1 &\implies n = 14, 15, 16, 17, 18, 19 \\ a = 2 &\implies n = 25, 26, 27, 28, 29 \\ a = 3 &\implies n = 36, 37, 38, 39 \\ a = 4 &\implies n = 46, 47, 48, 49 \\ a = 5 &\implies n = 56, 57, 58, 59 \\ a = 6 &\implies n = 66, 67, 68, 69 \\ a = 7 &\implies n = 76, 77, 78, 79 \\ a = 8 &\implies n = 85, 86, 87, 88, 89 \\ a = 9 &\implies n = 94, 95, 96, 97, 98, 99. \end{align*} So we need to show that applying $f$ repeatedly to any of the above will get $1$ or $89$. This can be done quite simply, by repeatedly applying $f$ to each individual element; for example, $$ 2 \to 4 \to 16 \to 37 \to 58 \to 89 $$ which knocks out $6$ of the above possibilities. And $$ 3 \to 9 \to (81) \to 17 \to (50) \to 25 \to 29 \to 85 \to 89, $$ knocking out several more (I put numbers $n$ such that $f(n) < n$ in parentheses, since we don't care about them.) We can proceed in this manner, just checking what happens for a specific value, until all of the numbers above are accounted for, and then we have proven that we will eventually arrive at $1$ or $89$.

As others have pointed out, while $f(1) = 1$, $89$ is not so special -- we don't have $f(89) = 89$, but instead it is part of a cycle of $8$ numbers.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .