## Numbers looking for happiness

A number can be happy or unhappy. To check if a number is happy, you have to replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1. If it starts looping on a set o numbers, the number is not happy.

For example, 7 is happy:

7² = 49

4² + 9² = 97

9² + 7² = 130

1² + 3² + 0² = 10

1² + 0² = 1

-> 1 is happy!

But 4 isn’t:

4² = 16

1² + 6² = 37

3² + 7² = 58

5² + 8² = 89

8² + 9² = 145

1² + 4² + 5² = 42

4² + 2² = 20

2² + 0² = 4

If we continue this process, we will stay in the loop 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16 … indefinitely.

There are plenty of solutions to check if a number is happy. Most of them store visited numbers and check if the number were already visited to avoid infinite loops. However, in this post, I will explore Henrique Bastos’ awesome recursive solution that considers that the process always end at a single-digit number:

def happy(number): next_ = sum(int(char) ** 2 for char in str(number)) return number in (1, 7) if number < 10 else happy(next_)

I would like to check if this supposition (the process always end at a single-digit number) is valid.

Lets first define a function f(x) -> y that calculates the sum of the squares of the digits of a number.

f(x_1x_2x_3 \ldots x_n) = x_1^2 + x_2^2 + x_3^2 + \ldots + x_n^2

In python, this function can be defined as:

f = lambda x: sum(int(xi) ** 2 for xi in str(x))

If f(x) < x, it would be easy to say that the process converge to single-digit numbers. Its is not always the case, since f(16) = 37. However we can use this property to check if N-digits numbers convege K-digits numbers, K < N.

It is easy to check that the sum of squares of a 4-digits number always results in a number with 3 or less digits. Consider the biggest number with 4 digits, 9999:

f(9999) = 9^2 + 9^2 + 9^2 + 9^2 = 324

As no other sum of squares can be bigger than 324 with 4-digits numbers, it is easy to see that 4-digits numbers converge to K-digits numbers (K < 4). The same thing occurs for 5-digits numbers (f(99999) = 405) and for any N-digits number (N \ge 4).

This property is also valid for 3-digits numbers. But it is not as easy to check since f(999) = 243, which is also a 3-digits number. To check the condition, we can check:

\forall x \in [100, 1000), f(x) < x

or:

\{x | x\in[100,1000), f(x)\ge x\}=\emptyset

In Python, this can be written as:

In [2]: not any(x for x in range(100, 1000) if f(x) >= x) Out[2]: True

Good. Now we know that number with more than 3 digits converge to smaller numbers, that eventually converge to digits with two or less digits. Unfortunately, this property is not valid for 2-digits numbers (f(99) = 162).

So we will check if 2-digits numbers converge to 1-digit numbers by brute-force, by applying f to them while they still have more than 1 digit, and while the amount of numbers with more than one digits decreases. We will also count how many numbers have more than 1 digit.

In [3]: old_size = 100 ...: current = range(10, 100) ...: sizes = [len(current)] ...: while current and len(current) < old_size: ...: old_size = len(current) ...: current = [f(x) for x in current if f(x) >= 10] ...: sizes.append(len(current)) ...: sizes Out[3]: [90, 83, 77, 69, 62, 58, 52, 46, 36, 24, 12, 7, 2, 1, 0] In [4]: len(_) Out[4]: 15

As you can see, in 14 steps, any 2-digits number can be reduced to a single-digit number.

Since 1 and 7 are the only single-digit happy numbers, all happy numbers reduce to them and all unhappy numbers reduce to {2, 3, 4, 5, 6, 8, 9}. So Henrique’s code is valid.

Edit (July 24, 2015): Fixed typo in a formula. Replaced all the formulas from mathtex equation editor to WP-KaTeX

## Leave a Reply