Fixed Points of Augmented Generalized Happy Functions II: Oases and Mirages

Breeanne Baker Swart Department of Mathematical Sciences

The Citadel 171 Moultrie St.

Charleston, SC 29409

USA

breeanne.swart@citadel.edu

Susan Crook

Division of Mathematics, Engineering and

Computer Science

Loras College 1450 Alta Vista St. Dubuque, IA 52001

USA

susan.crook@loras.edu

Helen G. Grundman Department of Mathematics

Bryn Mawr College 101 N. Merion Ave. Bryn Mawr, PA 19010

USA

grundman@brynmawr.edu

Laura Hall-Seelig Department of Mathematics Merrimack College 315 Turnpike Street North Andover, MA 01845 USA

                          hallseeligl@merrimack.edu

May Mei Department of Mathematics and Computer Science Denison University 100 West College Street Granville, Ohio 43023 USA

                              meim@denison.edu

Laurie Zack Department of Mathematical Sciences High Point University One University Parkway High Point, NC 27268 USA

                             lzack@highpoint.edu

Abstract

An augmented generalized happy function S_{[c,b]} maps a positive integer to the sum of the squares of its base b digits plus c. For b ≥ 2 and k ∈ ℤ^{+}, a k-desert base b is a set of k consecutive non-negative integers c for each of which S_{[c,b]} has no fixed points.

In this paper, we examine a complementary notion, a k-oasis base b, which we define to be a set of k consecutive non-negative integers c for each of which S_{[c,b]} has a fixed point. In particular, after proving some basic properties of oases base b, we compute bounds on the lengths of oases base b and compute the minimal examples of maximal length oases base b for small values of b.

1 Introduction

The concepts of happy number \underline{A007770} and generalized happy number [3, 4, 5] were generalized further [1] by allowing for augmentation, as follows.

Definition 1. For integers c ≥ 0 and b ≥ 2, the augmented generalized happy function, S_{[c,b]} : ℤ^{+} → ℤ^{+}, is defined for 0 ≤ a_{i} ≤ b − 1 and a_{n} ≠ 0 by

S_{[c,b]} (∑_{i=0}^{n} b^{i}a_{i}) = c + ∑_{i=0}^{n} a_{i}^{2}.

The value c is called the augmenting constant of S_{[c,b]}. A positive integer a is called a fixed point of S_{[c,b]} if S_{[c,b]}(a) = a. A positive integer a is a happy number if, for some k ∈ ℤ^{+}, S_{[0,10]}^{k}(a) = 1.

The function S_{[0,10]} is easily seen to have exactly one fixed point, while, depending on the values of c and b, the function S_{[c,b]} may have zero, one, or multiple fixed points [2]. The case of zero fixed points is studied in Part I of this paper [2], in which Baker Swart et al. prove that for each b ≥ 2, there exist arbitrarily long finite sequences of consecutive values of c for which S_{[c,b]} has no fixed point.

In this work, we study the complementary case by considering sets of consecutive augmenting constants c for which S_{[c,b]} has at least one fixed point and proving that, for each fixed b, the size of these sets is bounded. In Section 2, we define the concept of k-oasis base b, determine some initial properties, and prove a bound, for each b ≥ 2, on the lengths of oases base b. In Section 3, we define the concept of a k-mirage base b, prove that the maximal length of mirages base b bounds the maximal length of oases base b, and provide an algorithm for finding the maximal length of mirages base b. Finally, we use the above to determine the maximal length of oases (and of mirages) base b, for all b ≤ 20.

For later convenience, we note that if ∑_{i=0}^{n} b^{i}a_{i} is a fixed point of S_{[c,b]}, then solving for c yields that

c = ∑_{i=0}^{n}(b^{i} − a_{i})a_{i}.  (1)

Thus, for a given base b and an arbitrary positive integer a, there is at most one augmenting constant, c, such that a is a fixed point of S_{[c,b]}.

2 Fixed point oases

We begin by defining the key concept in this paper, a k-oasis base b, which is analogous to the concept of a k-desert base b, defined in Part I of this paper [2].

Definition 2. For b ≥ 2 and k ∈ ℤ^{+}, a k-oasis base b is a set of k consecutive non-negative integers c for each of which S_{[c,b]} has at least one fixed point. An oasis base b is a k-oasis base b, for some k ≥ 1. The length of a k-oasis base b is k.

Theorem 3 provides some basic facts about the existence and lengths of oases base b for different values of b ≥ 2.

Theorem 3. Let b ≥ 2.

1. There exists an oasis base b.

2. If b ≥ 2 is odd, then every k-oasis base b has k = 1.

3. If b ≥ 6 is even, then there exists a 5-oasis base b.

Proof. First, for any base b ≥ 2, since S_{[0,b]}(1) = 1, {0} is a 1-oasis base b.

Next, let b ≥ 2 be odd. As shown by Baker Swart et al. [2, Lemma 2.3], if S_{[c,b]} has a fixed point, then c is even. Part 2 of the theorem follows immediately.

Finally, let b ≥ 6 be even and let B = b/2. Set

a_{1} = (B − 2) b + 1,  c_{1} = B^{2} − 4,
a_{2} = (B − 1) b + 2,  c_{2} = B^{2} − 3,
a_{3} = Bb + 2,  c_{3} = B^{2} − 2,
a_{4} = (B − 1) b + 1,  c_{4} = B^{2} − 1,
a_{5} = Bb + 1,  c_{5} = B^{2}.

A direct calculation shows that for each 1 ≤ i ≤ 5, S_{[c_{i},b]}(a_{i}) = a_{i}. Hence {c_{1}, c_{2}, c_{3}, c_{4}, c_{5}} is a 5-oasis base b.

Given a k-oasis base b, it is easy to produce additional k-oases base b.

Theorem 4. Let b ≥ 2 and k ≥ 1. If there exists a k-oasis base b, there exist infinitely many k-oases base b.

Proof. Fix b ≥ 2 and let {c + j|1 ≤ j ≤ k} be a k-oasis base b. For each j, 1 ≤ j ≤ k, let a(j) denote a fixed point of S_{[c+j,b]}. Fix n ∈ ℤ^{+} such that for each j, a(j) < b^{n}. Then for each positive integer t and for each j, tb^{n} + a(j) is a fixed point of

S_{[c+j+tb^{n}−S_{[0,b]}(t),b]}.

Hence for each t ∈ ℤ^{+}, {c + j + tb^{n} − S_{[0,b]}(t)|1 ≤ j ≤ k} is a k-oasis base b.

The following theorems provide properties of fixed points associated with values of c that are in the same oasis base b. Theorem 5 provides that unless two such fixed points are quite small, they must have the same number of digits, and Theorem 6 says that few of the digits of the fixed points may differ. These theorems are used in proving Theorem 7, which gives a general upper bound for the length of an oasis base b, and again in Section 3, in proving the correctness of a method we provide for improving this bound.

Theorem 5. Let c ≥ 0 and b ≥ 2. Let a ∈ ℤ^{+} have n + 1 > 3 digits and satisfy S_{[c,b]}(a) = a. Then every fixed point with an augmenting constant in the same oasis base b as c has exactly n + 1 digits.

We note that Theorem 5 is optimal in that fixed points of two and three digits, respectively, can have augmenting constants in the same oasis. For example, in base 16, the two-digit number a = 85_{(16)} has augmenting constant c = 44 and the three-digit number â = 10(15)_{(16)} = 1 · 16^{2} + 15 has augmenting constant ĉ = 45. Clearly c and ĉ are in the same oasis base 16.

Proof of Theorem 5. Consider the collection of all values of c in a fixed oasis base b, and the set of all fixed points of the happy functions base b with those cs as augmenting constants. Assume that two of these fixed points have different numbers of digits and at least one of them has more than 3 digits. Then there must exist augmenting constants c̄ and ĉ in the oasis with |c̄ − ĉ| ≤ 1, and fixed points ā of S_{[c̄,b]} with n̄ + 1 > 3 digits and â of S_{[ĉ,b]} with n̂ + 1 ≠ n̄ + 1 digits. We may assume without loss of generality that n̂ < n̄.

In Part I of this paper [2, Theorem 4.2], Baker Swart et al. showed that for n ≥ 2, if S_{[c,b]} has a fixed point of n + 1 digits, then m_{b,n} ≤ c ≤ M_{b,n}, where the bounds, which are given explicitly in terms of their parameters, are sharp. They also showed [2, Lemma 4.3] that, for n ≥ 2, M_{b,n} + 1 < m_{b,n+1}.

In the same work [2, Theorem 4.2], the authors prove that, for n ≥ 2, if S_{[c,b]} has a fixed point of n + 1 digits, then m_{b,n} ≤ c ≤ M_{b,n}, where the bounds, which are given explicitly in terms of their parameters, are sharp. Additionally, they show [2, Lemma 4.3] that, for n ≥ 2, M_{b,n} + 1 < m_{b,n+1}. It follows (using a simple induction argument) that if n̂ ≥ 2, then ĉ + 1 ≤ M_{b,n̂} + 1 < m_{b,n̄} ≤ c̄. But this implies that 1 < c̄ − ĉ = |c̄ − ĉ|, a contradiction.

Thus, we have that n̂ < 2. Letting â = ∑n̂ ; i=0 a_{i}b^{i}, Equation (1) yields

ĉ = (b − a_{1})a_{1} + (1 − a_{0})a_{0}.

The largest possible value of (b−a_{1})a_{1} occurs when a_{1} = ⌊b/2⌋ and the largest possible value of (1 − a_{0})a_{0} is 0. Thus,

ĉ = (b − a_{1})a_{1} + (1 − a_{0})a_{0} ≤ (b − ⌊b/2⌋)⌊b/2⌋ + 0 ≤ b^{2}/4.

Since ā has more than three digits, n̄ ≥ 3, and so [2, Theorem 4.2] implies that

c̄ ≥ m_{b,n̂} = bn̂ − b^{2} + 3b − 3 ≥ b^{3} − b^{2} + 3b − 3.

Combining these and the fact that b ≥ 2 yields

1 ≥ |c̄ − ĉ| ≥ (b^{3} − b^{2} + 3b − 3) − b^{2}/4 > 1,

a contradiction, completing the proof.

Theorem 6. Fix b ≥ 2 and let c and ĉ be in the same oasis base b. Let S_{[c,b]}(a) = a and S_{[ĉ,b]}(â) = â. Then, letting a_{i} and â_{i} denote the coefficients of b^{i} in the base b expansions of a and â, respectively, for each i ≥ 3, a_{i} = â_{i}.

Proof. Suppose for a contradiction that there exists an i ≥ 3 such that a_{i} ≠ â_{i}. Then, at least one of a and â has more than three digits, and so, by Theorem 5, a and â have the same number of digits, say n + 1 > 3. We may assume, without loss of generality, that |ĉ− c| ≤ 1.

Fix j ≥ 3 maximal such that a_{j} ≠ â_{j}. Then using Equation (1), we have

|ĉ − c| = |(∑_{i=0}^{n}(b^{i} − â_{i})â_{i}) − (∑_{i=0}^{n}(b^{i} − a_{i})a_{i})|

= |∑_{i=0}^{j} ((b^{i} − â_{i})â_{i} − (b^{i} − a_{i})a_{i})|

≥ |(b^{j} − â_{j})â_{j} − (b^{j} − a_{j})a_{j}| − ∑_{i=0}^{j−1} |(b^{i} − â_{i})â_{i} − (b^{i} − a_{i})a_{i}| .

For i ≥ 2 and 0 ≤ x ≤ b − 1, the first derivative of the function f(x) = (b^{i} − x)x is positive and decreasing. Thus, the function is increasing at a decreasing rate over the domain. Therefore, the smallest difference between the function values for two integer values of x occurs when x = b − 1 and x = b − 2. Similarly, the largest difference occurs when x = b − 1 and x = 0. It follows that

|ĉ − c| ≥ ((b^{j} − (b − 1))(b − 1) − (b^{j} − (b − 2))(b − 2))

− ∑_{i=2}^{j−1} ((b^{i} − (b − 1))(b − 1) − (b^{i} − 0)(0))

− ∑_{i=0}^{1} |(b^{i} − â_{i})â_{i} − (b^{i} − a_{i})a_{i}|

≥ b^{j} − (b − 1)^{2} + (b − 2)^{2} − ∑_{i=2}^{j−1} b^{i}(b − 1) + (j − 2)(b − 1)^{2}

− |(b − \frac{b}{2}) (\frac{b}{2}) − (b − 0)(0)|

− |(1 − (b − 1))(b − 1) − (1 − 0)(0)|

= b^{2} + (b − 2)^{2} + (j − 3)(b − 1)^{2} − \frac{b^{2}}{4} − (b − 1)(b − 2).

Since j ≥ 3 and b ≥ 2, this implies that

1 ≥ |ĉ − c| ≥ \frac{3}{4}b^{2} − b + 2 > 2,

a contradiction. Thus no such i ≥ 3 exists, as desired.

Theorem 7. Let b ≥ 2. If there exists a k-oasis base b, then

k ≤ \frac{b^{3}}{2} + \frac{b^{2}}{2} − b.

Proof. If b is odd, then, by Theorem 3, every oasis base b has length 1, which is less than b^{3}/2 + b^{2}/2 − b. So we assume that b is even.

Let {c + j|1 ≤ j ≤ k} be a k-oasis base b. For each j, 1 ≤ j ≤ k, let a(j) be a fixed point of S_{[c+j,b]}. By Theorem 6, the fixed points, a(j), differ in, at most, the rightmost three digits. Since each fixed point corresponds to exactly one augmenting constant, this implies an initial bound: k ≤ b^{3}. But we can improve on this.

Baker Swart et al. [2, Theorem 2.1] prove that if a(j) is a multiple of b, then a(j) + 1 is also a fixed point of S_{[c+j,b]}. Thus, substituting a(j)+1 for a(j), if necessary, we may assume that none of the a(j) is a multiple of b. This leaves us with b − 1 possible rightmost digits.

Similarly, if a(j) has second rightmost digit equal to d ≠ 0, then the number obtained by replacing that digit with the digit b − d is another fixed point of S_{[c+j,b]} [2, Lemma 2.2]. Thus we may assume that none of the a_{i} have second rightmost digit greater than b/2. This leaves us with (b + 2)/2 possible second rightmost digits.

So, the number of possible values of the rightmost three digits of the a(j)s is

(b) (\frac{b + 2}{2}) (b − 1).

Since, for each of the k augmenting constants, c + j, there is a distinct fixed point, a(j), we conclude that the number of augmenting constants in the oasis is

k ≤ (b) (\frac{b + 2}{2}) (b − 1) = \frac{b^{3}}{2} + \frac{b^{2}}{2} − b,

as desired.

3 Maximal lengths of oases base b

In the previous section, we determined a general formula for an upper bound for the length of an oasis base b, for b ≥ 2. In this section, we present an algorithm for determining a new bound on this length, which, in many cases, can be shown to provide the precise maximal length of oases base b.

From Theorem 3, we know that if b is odd, every oasis base b has length 1. For bounding the oasis lengths for even bases, we introduce the concept of a mirage base b. For convenience, we extend the domain of the function S_{[0,b]} for b ≥ 2 to include 0 by defining S_{[0,b]}(0) = 0.

Definition 8. For b ≥ 2 and k ∈ ℤ^{+}, a k-mirage base b is a set of k consecutive integers {d_{1}, ..., d_{k}}, such that for each 1 ≤ i ≤ k, d_{i} = r_{i} − S_{[0,b]}(r_{i}) with r_{i} a non-negative integer of at most three digits. A mirage base b is a k-mirage base b for some k ≥ 1.

A mirage base b may or may not be an oasis base b. We first provide a large class of mirages that actually are oases.

Lemma 9. If a k-mirage base b contains only positive integers, then it is a k-oasis base b.

Proof. Given a k-mirage containing only positive integers, using the notation in the definition of k-mirage base b, for each 1 ≤ i ≤ k, we have S_{[d_{i},b]}(r_{i}) = d_{i} + S_{[0,b]}(r_{i}) = r_{i}. Thus r_{i} is a fixed point of S_{[d_{i},b]}, and so {d_{1}, ..., d_{k}} is a k-oasis base b.

Of course, not all mirages base b are oases base b. For example, −4 = 16 − S_{[0,6]}(16), −3 = 22 − S_{[0,6]}(22), −2 = 2 − S_{[0,6]}(2), −1 = 9 − S_{[0,6]}(9), and 0 = 1 − S_{[0,6]}(1), implying that {−4, −3, −2, −1, 0} is a 5-mirage base 6, though not an oasis base 6.

We next show that given a k-oasis base b, there must exist a k-mirage base b.

Theorem 10. Given b ≥ 2 and k ∈ ℤ^{+}, if there exists a k-oasis base b, then there exists a k-mirage base b.

Proof. Let O = {c + j|1 ≤ j ≤ k} be a k-oasis base b, and for each 1 ≤ j ≤ k, let a(j) ∈ ℤ^{+} be a fixed point of S_{[c+j,b]}.

First, consider the case in which each a(j) has 3 or fewer digits. Then for 1 ≤ j ≤ k, a(j) = S_{[c+j,b]}(a(j)) = (c + j) + S_{[0,b]}(a(j)), and so c + j = a(j) − S_{[0,b]}(a(j)). Thus O is a k-mirage base b, and we are done.

Next, consider the case in which, for at least one value of j, a(j) has more than 3 digits. Then, by Theorem 5, all of the a(j) have the same number of digits, say n + 1 > 3. For each 1 ≤ j ≤ k, let 0 ≤ a(j)_{i} ≤ b − 1, such that

a(j) = ∑_{i=0}^{n} a(j)_{i}b^{i},

and define

r_{j} = ∑_{i=0}^{2} a(j)_{i}b^{i}.

By Theorem 6, for each 1 ≤ j ≤ k and i ≥ 3, a(j)_{i} = a(1)_{i}. Thus, for each 1 ≤ j ≤ k,

a(j) = r_{j} + ∑_{i=3}^{n} a(j)_{i}b^{i} = r_{j} + ∑_{j=3}^{n} a(1)_{i}b^{i} = r_{j} + a(1) − r_{1}.  (2)

Further, since a(j) is a fixed point of S_{[c+j,b]}, we have that

\begin{aligned}a(j) & = S_{[c+j,b]}(a(j)) = (c + j) + S_{[0,b]}(r_{j}) + ∑_{i=3}^{n} a(j)_{i}^{2} \\ & = (c + j) + S_{[0,b]}(r_{j}) + ∑_{i=3}^{n} a(1)_{i}^{2}. \end{aligned}  (3)

Thus, using equations (2) and (3), for each 1 ≤ j ≤ k,

r_{j} − S_{[0,b]}(r_{j}) = (r_{1} − a(1) + ∑_{i=3}^{n} a(1)_{i}^{2} + c) + j.  (4)

Since the only value on the right-hand-side of Equation (4) dependent on j is j itself,

{r_{j} − S_{[0,b]}(r_{j})|1 ≤ j ≤ k}

is a set of consecutive integers and thus is a k-mirage base b.

It follows from Theorem 10 that the length of the longest mirage base b bounds the length of the longest oasis base b. Since each element in a mirage is generated by a fixed point between 0 and b^{3} exclusive, the maximum length of a mirage base b can be determined by a direct computer search. Formalizing this algorithm: in order to determine, for some fixed b ≥ 2, the maximal length of a mirage base b, and to check whether this is necessarily equal to the maximal length of an oasis base b, the following steps suffice.

1. For each 0 < r < b^{3}, compute d = r − S_{[0,b]}(r) ∈ ℤ.

2. Sort the values of d.

3. Determine the length of the longest string of consecutive values of d.

4. Check whether there is a longest string in which all of the values of d are positive.

The result of step 3 is the maximal length of a mirage base b and, therefore, a bound on the length of the maximal length oasis base b. Each longest string found in step 3 is an example of a maximal length mirage base b. If step 4 is answered in the affirmative, then this string of positive values of d is also an example of a maximal length oasis base b.

We carry out this algorithm for all even bases 2 ≤ b ≤ 20, in each case finding a maximal oasis base b. We summarize the results in the following theorem.

Theorem 11. The maximal lengths of oases base b for bases 2, 4, and 6, are 2, 6, and 5, respectively; the maximal length of oases base b for bases 8, 10, 12, 14, 16, and 18 is 8; and the maximal length of oases base 20 is 9.

In Table 1 we provide, for each even base, 2 ≤ b ≤ 20, the minimal example of an oasis of maximal length, along with the smallest fixed point of the augmented happy function determined by each augmenting constant in the oasis.

Base Length  Minimal maximal length oasis

Smallest fixed points

2 2 {3, 4}

4, 6

4 6 {28, 29, 30, 31, 32, 33}

32, 38, 42, 36, 40, 51

6 5 {5, 6, 7, 8, 9}

6, 14, 20, 12, 18

8 8 {304, 305, 306, 307, 308, 309, 310, 311}

347, 338, 391, 336, 346, 354, 344, 352

10 8 {487, 488, 489, 490, 491, 492, 493, 494}

544, 554, 522, 533, 520, 609, 543, 532

12 8 {172, 173, 174, 175, 176, 177, 178, 179}

207, 194, 299, 192, 206, 218, 204, 216

14 8 {421, 422, 423, 424, 425, 426, 427, 428}

434, 451, 601, 480, 494, 450, 465, 448

16 8 {559, 560, 561, 562, 563, 564, 565, 566}

628, 644, 594, 611, 592, 799, 627, 610

18 8 {1663, 1664, 1665, 1666, 1667, 1668, 1669, 1670}

1768, 1786, 1730, 1749, 1728, 1960, 1767, 1748

20 9 {5124, 5125, 5126, 5127, 5128, 5129, 5130, 5131, 5132}

5383, 5362, 5699, 5360, 5382, 5402, 5380, 5400, 5617

Table 1: Minimal valued maximal length oases and smallest fixed points for small even bases. (Results are all given in base 10.)

References

[1] B. Baker Swart, K. Beck, S. Crook, C. Eubanks-Turner, H. Grundman, M. Mei, and L. Zack, Augmented generalized happy functions, Rocky Mountain J. Math., 47 (2017), 403–417.

[2] B. Baker Swart, K. Beck, S. Crook, C. Eubanks-Turner, H. Grundman, M. Mei, and L. Zack, Fixed points of augmented generalized happy functions, Rocky Mountain J. Math., 48 (2018), 47–58.

[3] H. G. Grundman and E. A. Teeple, Generalized happy numbers, Fibonacci Quart., 39 (2001), 462–466.

[4] Richard K. Guy, Unsolved Problems in Number Theory, 3rd ed., Springer-Verlag, 2004.

[5] Ross Honsberger, Ingenuity in Mathematics, New Mathematical Library, Vol. 23, Random House, Inc., 1970.

2010 Mathematics Subject Classification: Primary 11A63. Keywords: happy number, fixed point, iteration.

(Concerned with sequence \underline{A007770}.)

Received February 8 2019; revised version received July 31 2019. Published in Journal of Integer Sequences, August 23 2019.

Return to Journal of Integer Sequences home page.