ON HAPPY NUMBERS

ESAM EL-SEDY AND SAMIR SIKSEK

Abstract. The happy function T : ℕ → ℕ is the mapping which sends a natural number to the sum of the squares of its decimal digits. A happy number x is a natural number for which the sequence {T^{n}(x)}_{n=1}^{∞} eventually reaches 1. Guy asks in [1] (problem E34) if there exists sequences of consecutive happy numbers of arbitrary length. In this paper we answer this question affirmatively.

1. Introduction

In [1] (problem E34, page 234) a happy number is defined as follows: “If you iterate the process of summing the squares of the decimal digits of a number, then it is easy to see that you either reach the cycle

4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4

or arrive at 1. In the latter case you started from a happy number.” Several questions are asked about happy numbers, including: “How many consecutive happy numbers can you have? Can there be arbitrarily many?”. It is the purpose of this paper to show that there are sequences of consecutive happy numbers of arbitrary length. It is hoped that our proof will be a model for answering similar questions involving iterates of maps depending on the digital representations of natural numbers.

2. Some Preliminary Results

We gather here some preliminary results which will be needed in our proof of the existence of sequences of consecutive happy numbers of arbitrary length. These are all elementary except for the final Lemma, which affirms the existence of an integer l with certain specified properties. The proof of this Lemma is left to the final section.

Definition 2.1. It will be convenient to define the happy function T : ℕ → ℕ by taking T (x) to be the sum of the squares of the decimal digits of x. A natural number x is then said to be happy if T^{r}(x) = 1 for some r ≥ 0, otherwise it is said to be unhappy.

Here, as usual, T^{0}(x) = x.

Lemma 2.1. For each natural number x the sequence x, T (x), T^{2}(x), … eventually reaches 1, 1, 1, … in which case x is happy or it eventually reaches the cycle 4, 16, 37, 58, 89, 145, 42, 20, 4, … in which case x is unhappy.

1991 Mathematics Subject Classification. 11B05; Secondary 11A63.

Key words and phrases. Happy Numbers, Digital Problems.

Proof. This Lemma is simply a rephrasing of the quotation, made above, from Guy’s book [1]. □

Lemma 2.2. For each natural number x the set T^{−1}(x) = {y ∈ ℕ : T (y) = x} is non-empty.

Proof. We simply observe that the number y = ∑_{i=0}^{x−1} 10^{i} has x digits all of which are equal to 1. It is immediate from the definition of T that T (y) = x. □

The happy transformation T is by no means linear, but the following Lemma shows that it behaves in a ‘semi-linear’ fashion in certain cases. This observation is crucial for the proof of our main result later.

Lemma 2.3. Suppose that x, y, s are natural numbers, such that 10^{s} > y. Then T (10^{s}x + y) = T (x) + T (y).

Proof. This follows from the fact that the digits of 10^{s}x + y are the digits of x and the digits of y with possibly some zeros in between. □

Let C = {4, 16, 37, 58, 89, 145, 42, 20} (the cycle) and let D = {1}∪C. One notes that the elements of D are permuted by the action of T on them.

We now rephrase Lemma 2.1 as follows.

Lemma 2.4. For every natural number x there exists r_{x} ≥ 0 such that T^{r}(x) ∈ D for all r ≥ r_{x}.

Lemma 2.5. If T^{r}(y) = x where r ≥ 0 and x is happy then y is also happy.

Proof. If x is happy then T^{r′}(x) = 1 for some r′ ≥ 0. Thus T^{r+r′}(y) = T^{r′}(x) = 1 and so y is happy. □

Lemma 2.6. There exists a natural number l such that l+u is happy for all u ∈ D.

Proof. A number l satisfying this property, plus a description of how this number was found, is given in Section 4 □

3. The Main Result

We are now ready to prove the main result of this paper.

Theorem 3.1. There exists sequences of consecutive happy numbers of arbitrary length. That is for each m ≥ 1 there exists an integer l_{0} such that every element of the finite sequence l_{0} + 1, l_{0} + 2, …, l_{0} + m is a happy number.

Proof. From now on l will denote a fixed positive integer, guaranteed to exist by Lemma 2.6, such that l + u is happy for each u ∈ D.

For each m we show that there exists a sequence of consecutive happy numbers of length m. Keep m fixed. From Lemma 2.4 we easily see that exists an r ≥ 1 such that T^{r}(i) ∈ D for all i = 1, 2, …, m.

The set {T^{j}(i) : i = 1, …, m; j = 0, …, r} is finite; thus we can choose an s such that

10^{s} > T^{j}(i) for all i = 1, …, m; j = 0, …, r  (1)

We define integers l_{0}, l_{1}, …, l_{r} in by means of a ‘reverse inductive’ definition; this means we give the value of l_{r}, and for each 0 ≤ j ≤ r − 1 we give a value for l_{j} in terms of the value of l_{j+1}.

First let l_{r} = l. For 0 ≤ j ≤ r − 1 we define l_{j} in terms of l_{j+1} as follows: by Lemma 2.2 we can find k_{j+1} such that T (k_{j+1}) = l_{j+1}. Let l_{j} = 10^{s}k_{j+1}. We note the following:

(1) For each 0 ≤ j ≤ r − 1, we have T (l_{j}) = l_{j+1}.

(2) If 0 ≤ j ≤ r − 1 and y < 10^{s} then by Lemma 2.3
T (l_{j} + y) = T (10^{s}k_{j+1} + y) = T (k_{j+1}) + T (y) = l_{j+1} + T (y)

From these two observations and from the set of inequalities (1) we see for all i = 1, …, m that

T^{r}(l_{0} + i) = T^{r−1}(T (l_{0} + i)) = T^{r−1}(l_{1} + T (i))
= T^{r−2}(T (l_{1}) + T (i)) = T^{r−2}(l_{2} + T^{2}i)
=  …  =  l_{r} + T^{r}(i)

Since l_{r} = l we have that T^{r}(l_{0} + i) = l + T^{r}(i) for all i = 1, …, m. Recall that r was chosen so that T^{r}(i) ∈ D for all i = 1, …, m, and that l was chosen l + u is happy for all u ∈ D. Hence T^{r}(l_{0} + i) = l + T^{r}(i) is happy for all i = 1, …, m. It follows from Lemma 2.5 that l_{0} + i is happy for i = 1, …, m. This is a sequence of consecutive happy numbers of length m. □

4. Some Computations

All that remains is to give a proof of Lemma 2.6; that is to give an integer l such that l + u is happy for all u ∈ D, where we recall that

D = {1, 4, 16, 20, 37, 42, 58, 89, 145}

We claim that the number

l = ∑_{r=1}^{233192} 9 × 10^{r+4} + 20958  (2)

has the desired property. It is easy to see that upon adding any element of D to l only at most the last four digits of l will be affected. Thus T (l + u) = 233192 × 9^{2} + 2^{2} + T (958 + u) = 18888556 + T (958 + u). A short computer program can now be used to verify that 18888556 + T (958 + u) is happy for all u ∈ D and thus so is l + u.

It is clear that we could not have found this l by a straightforward computer search; indeed the reader will shortly see finding an appropriate l required some experimentation and a fair amount of luck. Before embarking on a computer search, it is reasonable to somehow come up with an estimate for a ‘search region’ that ought to contain such a number. According to Guy ([1] page 234) it appears that roughly 1/7 of all numbers are happy and this is confirmed by our own extensive numerical experiments. If we are to assume that happy numbers are randomly distributed and have a density of 1/7 then given any natural number l, the probability that l + u is happy for all u ∈ D is 7^{−9} ≈ 2.48 × 10^{−8}. Thus if we were to go through all numbers up to 10^{9} then it is reasonable to expect that we will come up with a suitable l.

Considering the size of this search region it is natural to write the program in a low-level computer language: we chose C++. The C++ variable type unsigned long int allows integers of size up to 4.2 × 10^{9}. Division of integer types simply gives the quotient and it is easy to use this feature to recursively get the digits of an integer and so sum their squares. Thus our happy transformation T can be coded and we can decide if an integer is happy or not. An overnight search on a Pentium 233MHZ did not reveal any such l whose size is less than 4 × 10^{9}. It seems clear that happy numbers are not as random as we have supposed.

In desperation we decided to relax the conditions on the number l by requiring that l satisfies instead that l + u is happy for all u ∈ D′; where now D′ is the subset D′ = {1, 4, 16, 20, 37, 42}. A search now revealed many numbers satisfying this weaker condition. Remarkably, most ended with the digits 958. These include the first 18 such numbers to be found:

7894958, 7984958, . . . . . . , 19925958, 21995958

We do not know of an explanation for this phenomenon but it made us decide to restrict our search only to numbers ending with the digits 958. We thus assume that our l = 10^{3}x + 958. A search with x ≤ 4 × 10^{9} again did not reveal any l of this form which satisfies our condition: l + u is happy for all u ∈ D.

Eventually it occurred to us to try the following; if the number we seek l is of the form l = 10^{4}x + 958 then for all u ∈ D we have u + 958 < 10^{4} and so by Lemma 2.3 T (l) = T (x) + T (u + 958). Now let E = {T (u + 958) : u ∈ D} = {1, 11, 38, 66, 121, 146, 187, 194}. Our idea is to look for y such that y + v is happy for all v ∈ E. If we find such a y then we can also find an x such that T (x) = y (see Lemma 2.2). We can let l = 10^{4}x + 958 and it is now clear that l + u will be happy for all u ∈ D. We searched for y such that y + v is happy for all v ∈ E and within a few minutes we found that the number y = 18888556 satisfies this condition. But 18888556 = 233192 × 81 + 4. Let

x = ∑_{r=1}^{233192} 9 × 10^{r} + 2

then T (x) = y and 10^{4}x + 958 is our required l given in (2).

References

[1] R. Guy, Unsolved Problems in Number Theory, Springer-Verlag, 1994.

Department of Mathematics, King Saud University, Abha Branch, Abha, PO Box 157, Saudi Arabia