# How can we prove that a number is not happy number?

def : a positive number is called happy if repetative square sum of its digits ends in 1, otherwise not.

Upon checking some numbers, I found that a number that is not happy will result in some previously encontered values ? ( is it true?)

For Example

2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4
3 -> 9 -> 81 -> 65 -> 61 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> 2 -> 4 -> 16 -> 37


How can we be sure that the chain above will not terminate ? that is how can we know that if its not a happy number the number we have encountered earlier will be encountered in the chain again ?

Every bounded sequence of integers will hit at least one number infinitely many times.

Given that in your sequence, every element is a function of the previous element, this means that if your sequence is bounded, it will have cycles. So all you really need to do is prove that your sequence is bounded,

Hint:

Proving that your sequence is bounded regardless of where it starts is relatively simple, since for large enough numbers, the sum of the squares of its digits will be smaller than the number itself. For example, if a number has $$7$$ digits, then the sum if its digits squares will be at most $$7\cdot 9^2 = 576$$.

The above bound can of course be even lower. Let's denote the sum of the squares of an integer $$n$$ with $$S(n)$$.

Then, the same argument as above can be used to prove that if $$n\geq 1000$$, then $$S(n) < n$$. This is because $$k\cdot 9^2 < 10^{k-1}$$ for $$k\geq 4$$, which means that if our number $$n$$ has $$k$$ digits, and $$k$$ is $$4$$ or more, then $$S(n)$$, which is at most $$k\cdot 9^2$$, will have $$k-1$$ digits.

An exhaustive search can then be used to prove that for $$3$$ digit numbers, it is still true that $$S(n).

This means that the sequence you created will be monotonically decreasing so long as the numbers are larger than $$100$$, and it will only then hit a cycle. It might be a nice programming exercise to find all the cycles.

Just for the fun of it, I actually made a little more digging into this question and from what I can tell, there is only one non-trivial cycle possible, which is

$$[4, 16, 37, 58, 89, 145, 42, 20]$$.

All numbers either enter this cycle or hit $$1$$, and all other numbers form a sort of tree structure above this simple cycle.

• To see that $S(n) > n$ requires $n$ to have at most $2$ digits without an exhaustive search, assume $100 \le n < 1000$, then $S(n) \le 3\cdot 9^2 = 243$, meaning the first digit of $n$ must be $\le 2$. But then $S(n) \le 4 + 2\cdot 9^2 = 166$, so the first digit is $1$ and the second digit is $\le 6$. So $S(n) \le 1 + 36 + 81 = 118$ and the second digit is $\le 1$. But then $S(n) \le 1 + 1 + 81 = 83$, which cannot be. Commented May 10 at 16:55