Seven Steps to Happiness

A diagram showing an unhappy number caught in a loop.

May 6, 2020 — Alexander Wood

The Happy Numbers Problem

I was playing around on Leetcode going through some random prompts when I ran across the old “happy numbers” problem.

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits. Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

For example, starting with the number $164$ would lead you to $1^2 + 6 ^2 + 4 ^2 = 53$ , then to $5^2 + 3^2 = 34$ , et cetera, until you reach a loop ending at $89$ .

89 is a happy number

While some may say $13$ is an unlucky number, it is quite happy. $109$ is also happy, as we see below:

109 is not a happy number

My First Solution

The Leetcode challenge was to write a function that returns True if a number is happy, False otherwise. Easy, right? I typed up and submitted my first solution:

This solution keeps track of all numbers seen so far in the hash table mapped. The first while loop on line 11 replaces the current number with the sum of its digits until either the sum is equal to one or the cycle begins repeating.

Line 17 in the nested while loop takes the last digit of the current number, squares it, and adds it to the sum. Line 18 removes this last digit, and the loop repeats the process until all of the digits are added.

The Least Happy Numbers

What concerned me right away about this solution is the complexity. In other words, how many iterations does it take to either begin repeating a cycle, or converge to $1$ ? What is the worst-case scenario? Average?

I counted the number of steps required for each of the first million integers to either land on $1$ or get caught in a cyle. It never took more than 20 steps. Happy numbers required less steps — at most 7!

Okay, so, it isn’t a problem for relatively small numbers. But a million is not that big. What about large numbers? It turns out that this isn’t a trivial question!

In 1994, mathematician Richard K. Guy posed a series of questions about happy numbers in Problem E34 of his book Unsolved Problems in Number Theory. [G94]. Guy defines the height of a happy number to be the number of iterations needed to reach $1$ and asks, can we give bounds on the least happy number of height $h$ ?

Height	Happy number	Bit length
0	1	1
1	10	4
2	13	4
3	23	5
4	19	5
5	7	3
6	356	9
7	78999	17
8	3789 × 10⁹⁷³ − 1	3245
9	78889 × 10^{(3789 × 10⁹⁷³ − 306)/81} − 1	>10⁹⁷³
10	259 × 10^{[78889 × 10^{(3789 × 10⁹⁷³ − 306)/81} − 13]/81} − 1

Inspired by this question, a series of works [GT03, CZ08] explore happy numbers and provide methods for finding the happy numbers of any given height, in theory. The least happy numbers of heights 8, 9, and 10 were calculated by Grundman and Teeple in 2003 [GT03]. A few years later, Cai and Zhou calculated the least happy numbers of heights 11 and 12 [CZ08]. These values, along with their bit lengths, are provided in the table above. As you can see, they are beyond huge!

Cai and Zhou also introduced a theorem providing bounds on the number of digits in the least happy number of height $k$ .

For any $k \ge 6$ , the total number of digits in $\sigma_k,$ the least happy number of height $k,$ is no more than $[\sigma_{k-1}/81] + 4$ and no less than $[\sigma_{k-1}/81]$ .

Not only do we know that numbers with heights as low as 8 and 9 are massive — we also know that numbers with larger heights are even more massive.

Seven Steps to Happiness

The least happy number of height 8 is 3,245 bits. The least happy number with height 9 is prohibitively large, as seen with even the laziest possible lower bound on an estimate of bit length that I put in the table.

So, assuming that we will not encounter any numbers with bit lengths above 3,245 bits, we can replace the while loop in the code with a 7-iteration for loop, limiting the steps required in the worst-case.

This may not be a particularly useful optimization, but I do think it is a mathematically interesting one. I included my implementation below.

Long story short - Happiness (or unhappiness) can be reasonably determined in seven steps!

Some Extra Happy Facts

Arthur Porges showed in 1945 that all unhappy numbers eventually land in the same cycle of eight numbers: $4$ , $16$ , $37$ , $58$ , $89$ , $145$ , $42$ , $20$ [P45]. This was the earliest reference to happy numbers I was able to locate. (Let me know if you find anything earlier).

The cycle of eight numbers that all unhappy numbers reach.

Variations on the Happy Numbers problem appeared again in the 60s in some books of mathematical puzzles [D67, M66].

The Happy Numbers problem resurfaced when mathematician Reg Allenby’s daughter encountered it at school. Allenby shared the problem with Guy, who included it as entry E34 in his book of open problems in number theory where he posed a series of interesting questions about happy numbers [G94]. For instance, is possible to have arbitrarily long sequences of consecutive happy numbers (e.g. $7839$ , $7840$ , $7841$ , $7842$ )? El-Sedy and Siksek showed in 2000 that the answer is yes [ES00].

Another question asked by Guy is to determine how large the gap can be in the sequence of happy numbers. Other research examines generalizations of happy numbers with different bases and powers [GT01]. An additional unproven conjecture postulates that there are infinitely many happy primes.

References

[CZ08] T. Cai and X. Zhou. On the Heights of Happy Numbers. Rocky Mountain J. Math. 38 (2008), no. 6, 1921—1926.
[D67] H. E. Dudeney. Problem 143 in 536 Puzzles & Curious Problems. New York: Scribner, (1967), pp. 43 and 258-259.
[ES00] E. El-Sedy and S. Siksek. On happy numbers. Rocky Mountain J. Mathematics 30 (2000), 565—570.
[G94] R. K. Guy. "Happy Numbers." §E34 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 234—235, 1994.
[GT01] H. G. Grundman and E. A. Teeple. Generalized happy numbers. Fibonacci Quarterly 39 (2001), 462—466.
[GT03] H.G. Grundman and E.A. Teeple. Heights of happy numbers and cubic happy numbers. Fibonacci Quart., 41 (2003), pp. 301—306.
[GT07] H.G. Grundman and E.A. Teeple. Sequences of Consecutive Happy Numbers. Rocky Mountain J. Math. 37 (2007), no. 6, 1905—1916.
[M66] Joseph S. Madachy. Mathematics on Vacation. Scribner, 1966 - Mathematical recreations
[P45] Arthur Porges. A Set of Eight Numbers. The American Mathematical Monthly, Vol. 52, No. 7 (Aug. - Sep., 1945), pp. 379 — 382.