A Generalization of Collatz Functions and Jacobsthal Numbers

Ji Young Choi Department of Mathematics Shippensburg University of Pennsylvania 1871 Old Main Drive Shippensburg, PA 17257 USA

                    jychoi@ship.edu

Abstract

Let b ≥ 2 be an integer and g = b − 1. We consider a generalization of the modified Collatz function: For any positive integer m, the g-Collatz function f_{g} divides m by g, if m is a multiple of g; otherwise, the g-Collatz function f_{g} is the least integer greater than or equal to \frac{bm}{g}. Using this g-Collatz function, we extend the Collatz problem, and we show that there are nontrivial cycles for some g. Then we show how the function f_{g} transforms the base-b representation of positive integers, and we study the sequence of the b-ary representation of integers generated by the function f_{g}, starting with a b-ary string representing b^{N} for an arbitrary large integer N. We show each b-ary string in the sequence has a repeating string, and the number of occurrences of each digit in each shortest repeating string generalizes Jacobsthal numbers.

1 Introduction

Definition 1. [2, 4] For any positive integer m, the Collatz function f_{1} and the modified Collatz function f_{2} on m are defined as follows:

f_{1}(m) := \begin{cases}\frac{m}{2}, & if m is even; \\ 3m + 1, & if m is odd, \end{cases} and f_{2}(m) := \begin{cases}\frac{m}{2}, & if m is even; \\ \frac{3m+1}{2} = ⌈\frac{3m}{2}⌉, & if m is odd. \end{cases} (1)

Collatz [2] asked if every positive integer m is mapped to 1 by applying the Collatz function or the modified Collatz function repeatedly: f_{i}^{n}(m) = 1 for some integer n, where i = 1 or 2.

Conway [3] proved that a generalization of the Collatz problem is undecidable, and there are several ways to generalize the Collatz function. For example, Conway considered the following:

f̄(m) = a_{i}m + b_{i}, m ≡ i (mod p),  (2)

where a_{i} and b_{i} are rational numbers so that f̄(m) is an integer. Notice that the Collatz function (1) is the same as (2), when p = 2, a_{0} = \frac{1}{2}, b_{0} = 0, a_{1} = 3, and b_{1} = 1.

Throughout this paper, we let g be an integer greater than 1 and b = g + 1 (unless we specify otherwise), and we consider p = g, a_{0} = \frac{1}{g}, b_{0} = 0, a_{i} = b, b_{i} = g − i for (2), as follows:

f̄_{g}(m) := \begin{cases}\frac{m}{g}, & if m ≡ 0 (mod g); \\ bm + g − i, & if m ≡ i (mod g) for i = 1, 2, …, g − 1. \end{cases}  (3)

Then, as we modified f_{1} to f_{2}, we modify f̄_{g} as shown in the following definition, by considering f̄_{g}(m), if g divides m; f̄_{g}^{2}(m), otherwise.

Definition 2. For any integer g ≥ 2 and any positive integer m, the g-Collatz function f_{g} on m is defined as follows:

f_{g}(m) := \begin{cases}\frac{m}{g}, & if m ≡ 0 (mod g); \\ \frac{bm+g−i}{g} = ⌈\frac{bm}{g}⌉, & if m ≡ i (mod g) for i = 1, 2, …, g − 1. \end{cases}  (4)

Now we extend the Collatz problem. We ask if every positive integer m is eventually mapped to 1 by repeatedly applying the g-Collatz function: if f_{g}^{n}(m) = 1 for some integer n, and we call it the g-Collatz problem. We can answer this g-Collatz problem immediately for some g by finding a nontrivial cycle. For example, when g = 3, we can find a nontrivial cycle in

5 → 7 → 10 → 14 → 19 → 26 → 35 → 47 → 63 → 21 → 7 → · · · .

Table 1 shows the minimum positive integer m such that f_{g}^{n}(m) ≠ 1 for every n and the minimum integer k > g such that f_{g}^{n}(k) = k for some n, where g = 3, 4, …, 20. When

g 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
m 5 11  7  31 34 588 767  49 35 19  63
k 7 23  23  35 42 642 1348  53 178 79  71

Table 1: Minimum m and k > g: m ↛ 1 and k → k by f_{g} repeatedly

g = 5, 7, 8, 13, 14, 18, and 19, every positive integer up to 2 × 10^{9} is mapped to 1 by f_{g}^{n} for some n, but we do not know whether every integer beyond 2 × 10^{9} also reaches 1. The g-Collatz problem for g = 5, 7, 8, 13, 14, 18, and 19 seems hard, just as in the original Collatz problem.

Do we know which values of g provide a nontrivial cycle for the corresponding g-Collatz problem? That is, can we find a pattern for g which makes the g-Collatz problem different from the original Collatz problem? If we can answer this question, we can solve the original Collatz problem, since the original Collatz problem is the 2-Collatz problem. Hence, we want to work on a different property of the Collatz function to see if the property can be extended for all g.

The number of occurrences of each digit in each shortest repeating string in the ternary Collatz sequence starting with 3^{N} for an arbitrary large N is expressed with Jacobsthal numbers [1]. We wonder if we can extend this. That is, we want to know if we can generalize Jacobsthal numbers, to express the number of occurrences of each digit in each shortest repeating string in the b-ary g-Collatz sequence starting with b^{N} for an arbitrary large N, for all g. It is easy to do for some g, but not easy for all g.

In this paper, we provide two different generalizations of Jacobsthal numbers: one is defined for g ≢ 2 (mod 4) and the other for g ≡ 2 (mod 8), except g = 2. For g ≡ 6 (mod 8), we may need to consider infinitely many cases, and we could provide infinitely many new types of generalizations of Jacobsthal numbers. This is desirable for future work.

Section 2 clarifies the notation in this paper. Section 3 shows how to apply the g-Collatz function to the base-b representation of positive integers. In Section 4, we study the shortest repeating string in the sequence of b-ary strings representing f_{g}^{n}(b^{N}) for an arbitrary large integer N. In Section 5, we study the number of occurrences of each digit in each shortest repeating string in the b-ary g-Collatz sequence, when g ≢ 6 (mod 8). Finally, in Section 6, we define two different types of generalizations of Jacobsthal numbers to express the number of each digit studied in Section 5.

2 Notation

Every base-b representation of an integer is a finite string in {0, 1, 2, …, g}^{∗}, which is the set of all finite strings consisting of digits 0, 1, 2, …, g. The set {0, 1, 2, …, g}^{∗} also includes the empty string, which contains no digits, denoted by ϵ [5].

The notation for the number of digits in a string is as follows:

Notation 3. [5] For any finite string x and a digit a, let |x| denote the number of digits in x, and |x|_{a} denote the number of occurrences of digit a’s in x.

Lemma 4. For any string x in {0, 1, 2, …, g}^{∗},

|x| = ∑_{i=0}^{g} |x|_{i}.

For example, |01011| = 5, |01011|_{0} = 2, |01011|_{1} = 3, and 5 = 2 + 3.

The following operation shows how to create a new string from given ones [5]:

Definition 5. For any strings x and y and any positive integer n, the concatenation of x and y, denoted by xy, is the string obtained by joining x and y end-to-end, and x^{n} denotes the concatenation of n x’s. That is, if x = a_{1}a_{2} ⋯ a_{|x|} and y = b_{1}b_{2} ⋯ b_{|y|} for some a_{i}, b_{i} ∈ {0, 1, 2, …, g},

xy = a_{1}a_{2} ⋯ a_{|x|}b_{1}b_{2} ⋯ b_{|y|}, and x^{n} = xx ⋯ x (n times).

For a convention, x^{0} is defined to be ϵ.

Lemma 6. For any strings x and y and a nonnegative integer n, |xy| = |x| + |y| and |x^{n}| = n|x|.

For example, 101 00 = 10100, (10)^{3} = 101010, and 1 = 1 (10)^{0}. Then, |101 00| = |101| + |00| = 3 + 2 = 5, |(10)^{3}| = 3|10| = 3 · 2 = 5, and |ϵ| = |(10)^{0}| = 0.

Since the base-b representation of an integer is a string in {0, 1, 2, …, g}^{∗}, we call the base-b representation of an integer as a b-ary string throughout this paper. When we have to distinguish an integer and its b-ary string, we use the following notation.

Notation 7. For any integer m with its base-b representation x, we write m = [x]_{b} or (m)_{b} = x.

For example, 5 = [12]_{3} and (5)_{3} = 12. Then, ([x]_{b})_{b} = x for any b-ary string x and [(m)_{b}]_{b} = m for any integer m.

Throughout this paper, we use the convention that m is an integer and x is its b-ary string. When we apply the g-Collatz function f_{g}, we often phrase this in terms of how f_{g} transforms x to another b-ary string, and we do not mention m.

Notation 8. For a b-ary string x, we let f_{g}(x) denote the b-ary representation of f_{g}([x]_{b}). That is, f_{g}(x) = (f_{g}([x]_{b}))_{b}.

To apply the g-Collatz function on a b-ary string, it is important to know whether a given b-ary string represents a multiple of g or not. For any integer m, we let m mod g denote the least nonnegative residue of m modulo g, and s_{b}(m) denote the digit sum of the base-b representation of m. That is, m mod g is the remainder when m is divided by g, and if (m)_{b} = a_{1}a_{2} ⋯ a_{k−1}a_{k},

s_{b}(m) = ∑_{i=1}^{k} a_{i}.

It is well-known that s_{b}(m) is congruent to m modulo g. Hence,

m mod g ≡ s_{b}(m) (mod g).  (5)

For a convention, we define the notation for the sum of digits in x, and the remainder when [x]_{b} is divided by g, for any b-ary string x.

Definition 9. For any b-ary string x, we let s(x) and r(x) denote as follows:

s(x) = \begin{cases}s_{b}([x]_{b}), & if x ≠ ϵ; \\ 0, & if x = ϵ, \end{cases} and r(x) = \begin{cases}[x]_{b} mod g, & if x ≠ ϵ; \\ 0, & if x = ϵ. \end{cases}

Lemma 10. For any b-ary string x, r(x) ≡ s(x) (mod g).

To simplify arguments, we sometimes use the following notation.

Notation 11. For any integers a and b, let a ≡_{g} b denote a ≡ b (mod g).

3 Generalized Collatz functions

For any nonzero digit a ∈ {0, 1, 2, …, g}, the product g · a can be represented by a b-ary string of length 2, whose digit sum is g.

Lemma 12. For any a ∈ {1, 2, …, g}, the product g · a = [a − 1, b − a]_{b} and the sum s_{b}(g · a) = g.

Proof. Since g = b − 1, g · a = (a − 1) · b + (b − a), so s_{b}(g · a) = a − 1 + b − a = g.

Lemma 13. For any digits a_{1} and a_{0} in {0, 1, 2, …, g} with a_{1} < g, if [a_{1}a_{0}]_{b} = g · q + r for 0 ≤ r < g,

q = \begin{cases}a_{1}, & if a_{1} + a_{0} < g; \\ a_{1} + 1, & if a_{1} + a_{0} ≥ g, \end{cases} and r = \begin{cases}a_{0} + q, & if a_{0} + q < b; \\ a_{0} + q − b, & if a_{0} + q ≥ b. \end{cases}

Proof. If [a_{1}a_{0}]_{b} < g, the digit a_{1} = 0 so it is obvious that q = 0 and r = a_{0}. Hence, assume [a_{1}a_{0}]_{b} ≥ g. Then, by Lemma 12, g · q = (q − 1) · b + b − q, so

r = [a_{1}a_{0}]_{b} − g · q = (a_{1} − q + 1) · b + a_{0} − b + q.

Since a_{1} < g, the number [a_{1}a_{0}]_{b} < [g0]_{b} = g ·b so q ≤ b−1. Then, a_{0} −b+q ≤ a_{0} −1 ≤ g −1. Hence, if a_{0} − b + q ≥ 0, the remainder r = a_{0} − b + q and a_{1} − q + 1 = 0, so q = a_{1} + 1. Then, a_{0} − b + (a_{1} + 1) ≥ 0, so a_{1} + a_{0} ≥ b − 1 = g. If a_{0} + q − b < 0, the remainder r = a_{0} − b + q + b = a_{0} + q and a_{1} − q = 0, so q = a_{1}. Hence, q and r are as desired.

Lemma 14. For any digit a_{i}’s in {0, 1, 2, …, g}, if [a_{1}a_{2} ⋯ a_{k}]_{b} ≡ 0 (mod g),

\frac{[a_{1}a_{2} ⋯ a_{k}]_{b}}{g} = [a′_{1}a′_{2} ⋯ a′_{k}]_{b},

where a′_{1} = 1 if a_{1} = g; 0 otherwise, and for i > 1,

a′_{i} = \begin{cases}r(a_{1}a_{2} ⋯ a_{i−1}), & if a_{i} < g − r(a_{1}a_{2} ⋯ a_{i−1}); \\ r(a_{1}a_{2} ⋯ a_{i−1}) + 1, & if a_{i} ≥ g − r(a_{1}a_{2} ⋯ a_{i−1}). \end{cases}

Proof. It is obvious for a′_{1}. For any i > 1, let r_{i} = r(a_{1}a_{2} ⋯ a_{i−1}). Then, r_{i} is a digit < g, and a′_{i} is the quotient when [r_{i}a_{i}]_{b} is divided by g. Hence, a′_{i} = r_{i} if r_{i} + a_{i} < g; r_{i} + 1 otherwise, by Lemma 13. That is, a′_{i} = r_{i} if a_{i} < g − r_{i}; r_{i} + 1 otherwise.

The following lemma shows how f̄_{g} defined in (3) transforms a b-ary string representing a non-multiple of g to a b-ary string representing a multiple of g.

Lemma 15. For any b-ary string x, if [x]_{b} ≢ 0 (mod g), f_{g}(x) = f_{g}(xa), where a = g −r(x).

Proof. Since [x]_{b} ≢ 0 (mod g), the number f̄_{g}([x]_{b}) = b[x]_{b} + g − r(x) = [x0]_{b} + a = [xa]_{b} by (3). Then, [xa]_{b} ≡_{g} s(xa) = s(x) + a ≡_{g} r(x) + a ≡ 0 (mod g). Hence, by Definition 2, f_{g}([x]_{b}) = \frac{[xa]_{b}}{g} = f_{g}([xa]_{b}).

For example, when b = 10 and x = 9107222, g = 9 and r(x) = 5. Hence, a = 9 − 5 = 4 so f̄_{9}(x) = 9107222 4 so f_{9}(x) = f_{9}(91072224).

For a b-ary string x representing a multiple of g, the g-Collatz function f_{g} divides [x]_{b} by g. Hence, by combining Lemma 14 and 15, we find how the g-Collatz function f_{g} transforms a b-ary string to a b-ary string.

Theorem 16. For any digits a_{i}’s in {0, 1, 2, …, g},

f_{g}(a_{1}a_{2} ⋯ a_{k}) = \begin{cases}a′_{1}a′_{2} ⋯ a′_{k}, & if [a_{1}a_{2} ⋯ a_{k}]_{b} ≡ 0 (mod g); \\ a′_{1}a′_{2} ⋯ a′_{k}a′_{k+1}, & if [a_{1}a_{2} ⋯ a_{k}]_{b} ≢ 0 (mod g), \end{cases}

where a′_{1} = 1 if a_{1} = g; 0 otherwise, a′_{k+1} = r(a_{1}a_{2} ⋯ a_{k}) + 1, and for i = 2, 3, …, k,

a′_{i} = \begin{cases}r(a_{1}a_{2} ⋯ a_{i−1}), & if a_{i} < g − r(a_{1}a_{2} ⋯ a_{i−1}); \\ r(a_{1}a_{2} ⋯ a_{i−1}) + 1, & if a_{i} ≥ g − r(a_{1}a_{2} ⋯ a_{i−1}). \end{cases}

Proof. Let x = a_{1}a_{2} ⋯ a_{k}. When [x]_{b} ≡ 0 (mod g), it is obvious by Lemma 14. Hence, assume [x]_{b} ≢ 0 (mod g). By Lemma 15, f_{g}(x) = f_{g}(xa), where a = g − r(x). Since [xa]_{b} ≡ 0 (mod g), the number f_{g}([x]_{b}) = \frac{[xa]_{b}}{g}. Therefore, a′_{i}’s are obtained by Lemma 14. Especially, a′_{k+1} = r(x) + 1, since a = g − r(x).

In this paper, when a head digit is transformed to digit 0, we keep the new head digit 0, so that |f_{g}(x)| = either |x| or |x|+1 for any string x. For example, when b = 10, f_{9}(36099) = 04011 and f_{9}(36095) = 040106 so that |04011| = |36099| and |040106| = |36095| + 1.

Corollary 17. For any digits a_{i}’s in {0, 1, 2, …, g}, if f_{g}(a_{1}a_{2} ⋯ a_{k}) = a′_{1}a′_{2} ⋯ a′_{k}a′ for some digits a′_{i} and a′, allowing a′ = ϵ, the digit a′_{i} ≠ g − a_{i}.

Proof. If a_{i} < g − r(a_{1}a_{2} ⋯ a_{i−1}), the digit a′_{i} = r(a_{1}a_{2} ⋯ a_{i−1}) < g − a_{i}. If a_{i} ≥ g − r(a_{1}a_{2} ⋯ a_{i−1}), the number r(a_{1}a_{2} ⋯ a_{i−1}) ≥ g − a_{i}, so a′_{i} = r(a_{1}a_{2} ⋯ a_{i−1}) + 1 > r(a_{1}a_{2} ⋯ a_{i−1}) ≥ g − a_{i}.

a′ r(x) = 0 1 2 3 ⋯ g − 3 g − 2 g − 1
a = 0  0 1 2 3 ⋯ g − 3 g − 2 g − 1
1  0 1 2 3 ⋯ g − 3 g − 2 g
2  0 1 2 3 ⋯ g − 3 g − 1 g
3  0 1 2 3 ⋯ g − 2 g − 1 g
⋮  ⋮
g − 3  0 1 2 4 ⋯ g − 2 g − 1 g
g − 2  0 1 3 4 ⋯ g − 2 g − 1 g
g − 1  0 2 3 4 ⋯ g − 2 g − 1 g
g  1 2 3 4 ⋯ g − 2 g − 1 g

Table 2: The image a′ of a in f_{g}(xay) = x′a′y′

Table 2 shows how f_{g} transforms digit a to digit a′ satisfying f_{g}(xay) = x′a′y′ for any b-ary strings x, x′, y, and y′ with |x| = |x′|. Notice that each image digit a′ of digit a depends on r(x), and there are g distinct images of each digit a.

Note 18. For any b-ary strings x_{1}, x_{2}, y_{1}, and y_{2} and any digit a, let x′_{1}, x′_{2}, y′_{1}, and y′_{2} be b-ary strings and a′_{1} and a′_{2} be digits satisfying f_{g}(x_{1}ay_{1}) = x′_{1}a′_{1}y′_{1} and f_{g}(x_{2}ay_{2}) = x′_{2}a′_{2}y′_{2} with |x_{1}| = |x′_{1}| and |x_{2}| = |x′_{2}|. Then, a′_{1} = a′_{2} iff r(x_{1}) = r(x_{2}).

Now consider the g-Collatz function f_{g} on a concatenation of b-ary strings.

Lemma 19. For any b-ary strings y and z with [y]_{b} ≡ 0 (mod g),

f_{g}(yz) = f_{g}(y)f_{g}(z).

Proof. Since s(y) ≡_{g} [y]_{b} ≡ 0 (mod g), the number [yz]_{b} ≡_{g} s(yz) = s(y) + s(z) ≡_{g} s(z) ≡ [z]_{b} (mod g). Hence, if [z]_{b} ≡ 0 (mod g), [f_{g}(yz)]_{b} = \frac{[yz]_{b}}{g} and

[f_{g}(y)f_{g}(z)]_{b} = [(\frac{[y]_{b}}{g} )_{b} (\frac{[z]_{b}}{g} )_{b}]_{b} = [(\frac{[y]_{b}}{g} )_{b} 0^{|z|}]_{b} + \frac{[z]_{b}}{g} = \frac{[y0^{|z|}]_{b} + [z]_{b}}{g} = \frac{[yz]_{b}}{g} .

If [z]_{b} ≢ 0 (mod g), the string f_{g}(z) = f_{g}(za), where a = g − r(z) by Lemma 15. Since [yz]_{b} ≡ [z]_{b} (mod g), the remainder r(yz) = r(z). Hence, a = g − r(yz), so f_{g}(yz) = f_{g}(yza). Since [za]_{b} ≡ 0 (mod g), the string f_{g}(yz) = f_{g}(yza) = f_{g}(y)f_{g}(za) = f_{g}(y)f_{g}(z).

Theorem 20. For any b-ary strings y_{i}’s and z, if [y_{i}]_{b} ≡ 0 (mod g) for all i,

f_{g}(y_{1}y_{2} ⋯ y_{k}z) = f_{g}(y_{1})f_{g}(y_{2}) ⋯ f_{g}(y_{k})f_{g}(z).  (6)

Proof. Since [y_{i}]_{b} ≡ 0 (mod g) for all i, by Lemma 19, f_{g}(y_{1}y_{2} ⋯ y_{k}z) = f_{g}(y_{1})f_{g}(y_{2} ⋯ y_{k}z). Continuing this, (6) is obtained.

In order to study a lengthy b-ary g-Collatz sequence with repeating digits in the following section, we present the following corollaries and theorem.

Corollary 21. For any b-ary string x and z and for any positive integer k, if gcd([x]_{b}, g) = d,

f_{g}(x^{k}z) = (f_{g}(x^{\frac{g}{d}}))^{⌊^{\frac{dk}{g}}⌋} f_{g}(x^{k mod \frac{g}{d}} z).

Proof. Since k = \frac{g}{d} ⌊\frac{dk}{g}⌋+k mod \frac{g}{d}, the string x^{k} = (x^{\frac{g}{d}})^{⌊^{\frac{dk}{g}}⌋}x^{k mod \frac{g}{d}}. Since [x^{\frac{g}{d}}]_{b} ≡_{g} s(x^{\frac{g}{d}}) =

\frac{g}{d} · s(x) ≡_{g} \frac{g}{d}[x]_{b} ≡_{g} g · \frac{[x]_{b}}{d} ≡ 0 (mod g), we can apply Theorem 20.

Theorem 22. For any b-ary string x and digits a_{i}’s, if x = a_{1}a_{2} ⋯ a_{|x|} and gcd([x]_{b}, g) = 1, the b-ary string f_{g}(x^{g}) = a′_{1}a′_{2} ⋯ a′_{g|x|} for some digits a′_{i}’s, where

{a′_{k}, a′_{|x|+k}, …, a′_{(g−1)|x|+k}} = {a ∈ {0, 1, 2, …, g}|a ≠ g − a_{k}}.

for any k = 1, 2, …, |x|.

Proof. Since [x^{g}]_{b} ≡_{g} s(x^{g}) = g · s(x) ≡ 0 (mod g), the number |f_{g}(x^{g})| = |x^{g}| = g|x|. Hence, f_{g}(x^{g}) = a′_{1}a′_{2} ⋯ a′_{g|x|} for some digits a′_{i}’s. Let a_{i|x|+k} be the (i|x| + k)-th digit in the string x^{g}. Then, for any i and j with 0 ≤ i ≠ j ≤ g − 1, the digit a_{i|x|+k} = a_{j|x|+k} but r(a_{1}a_{2} ⋯ a_{i|x|+k}) ≠ r(a_{1}a_{2} ⋯ a_{j|x|+k}). (If so, r(x^{i}) = r(x^{j}). Then, i · [x]_{b} ≡_{g} i · s(x) = s(x^{i}) ≡_{g} s(x^{j}) = j · [x]_{b} ≡ j · r(x) (mod g), so (i − j) · [x]_{b} ≡ 0 (mod g), which is impossible, since gcd([x]_{b}, g) = 1 and 0 ≤ i ≠ j ≤ g − 1.) Hence, a′_{i|x|+k} ≠ a′_{j|x|+k} by Note 18, so |{a′_{k}, a′_{|x|+k}, …, a′_{(g−1)|x|+k}}| = g. Since a′_{i|x|+k} ≠ g − a_{k} by Corollary 17, the set {a′_{k}, a′_{|x|+k}, …, a′_{(g−1)|x|+k}} collects every possible image of a_{k} by f_{g}. That is, the set {a′_{k}, a′_{|x|+k}, …, a′_{(g−1)|x|+k}} contains every digit in {0, 1, 2, …, g} except g − a_{k}.

Corollary 23. For any b-ary string x and digit a ∈ {0, , 1, 2, …, g}, if gcd([x]_{b}, g) = 1,

|f_{g}(x^{g})|_{a} = |x| − |x|_{g−a}.  (7)

Proof. Theorem 22 shows that every digit a′ in the string x is transformed to g distinct digits in f_{g}(x^{g}), and each new digit a in f_{g}(x^{g}) cannot be equal to g − a′. That is, every digit a in f_{g}(x^{g}) is obtained by transforming digit a′ in x, where a′ ≠ g − a, and there is no other way to obtain digit a in f_{g}(x^{g}). Hence,

|f_{g}(x^{g})|_{a} = ∑_{a′≠g−a} |x|_{a′} = ∑_{a′=0}^{g} |x|_{a′} − |x|_{g−a} = |x| − |x|_{g−a}.

Corollary 24. For any b-ary string x, if gcd([x]_{b}, g) = 1,

[f_{g}(x^{g})]_{b} ≡ \begin{cases}[x]_{b} + \frac{g}{2} (mod g), & if g is even and |x| is odd; \\ [x]_{b} (mod g), & otherwise. \end{cases}

Proof. By Corollary 23,

[f_{g}(x^{g})]_{b} ≡_{g} s(f_{g}(x^{g})) = ∑_{a=0}^{g} a|f_{g}(x^{g})|_{a} = ∑_{a=0}^{g} a(|x| − |x|_{g−a})

≡_{g} |x| ∑_{a=0}^{g} a + ∑_{a=0}^{g}(g − a)|x|_{g−a}

= \frac{g(g + 1)}{2}|x| + s(x)

≡_{g} \frac{g(g + 1)}{2}|x| + [x]_{b}.

If g + 1 or |x| is even, the number \frac{g(g+1)}{2}|x| ≡ 0 (mod g), so [f_{g}(x^{g})]_{b} ≡ [x]_{b} (mod g). If g + 1 and |x| are odd, g is even and |x| = 2k + 1 for some integer k. Hence,

\frac{g(g + 1)}{2}|x| = \frac{g}{2}(g + 1)(2k + 1) ≡_{g} \frac{g}{2} · 2k + \frac{g}{2} = gk + \frac{g}{2} ≡_{g} \frac{g}{2}.

4 b-ary g-Collatz sequences

Consider a sequence of b-ary strings generated by the g-Collatz function f_{g}, starting with a b-ary string 10^{N} for any arbitrary large positive integer N. For example, when g = 3, b = 4. Then, the first few strings in the 4-ary 3-Collatz sequence starting with the string 1 0^{60} are as follows:

\begin{aligned}1 0^{60} & = 1000000000000000000000000000000000000000000000000000000000000; \\ f_{3}^{1}(1 0^{60}) & = 01111111111111111111111111111111111111111111111111111111111112; \\ f_{3}^{2}(1 0^{60}) & = 001301301301301301301301301301301301301301301301301301301301303; \\ f_{3}^{3}(1 0^{60}) & = 0002113231002113231002113231002113231002113231002113231002113233; \\ f_{3}^{4}(1 0^{60}) & = 0000302210112013321223131033000302210112013321223131033000302211. \end{aligned}

Since digit 0 repeats in the initial string 10^{N}, there exists a substring repeats in f_{g}^{n}(10^{N}), ignoring the head digit and a tail string. For example, when g = 3, the substrings 013 and 002113231 repeat in the 4-ary strings f_{3}^{2}(1 0^{60}) and f_{3}^{3}(1 0^{60}), respectively.

Definition 25. Let N be an arbitrary large integer. For any positive integer n and any g-Collatz function f_{g}, the nth repeating string u_{gn} is defined as the shortest string in the b-ary string f_{g}^{n}(10^{N}) such that

f_{g}^{n}(10^{N}) = 0(u_{gn})^{⌊ \frac{N}{|ugn|} ⌋}t

for some b-ary string t.

For example, u_{3n} for n = 1, 2, 3, 4 is as follows:

u_{31} = 1;
u_{32} = 013;
u_{33} = 002113231;
u_{34} = 000302210112013321223131033.

Since r(10^{N}) = 1 for any g ≥ 2, the string f_{g}(10^{N}) = 01^{N}2. Hence, u_{g1} = 1 for any g ≥ 2. Then, by Theorem 16, u_{g2} = f_{g}(1^{g}) = 012 … (g − 3)(g − 2)g. For example, u_{g2} for g = 2, 3, …, 9 is as follows.

\begin{matrix}g & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ u_{g2} & 02 & 013 & 0124 & 01235 & 012346 & 0123457 & 01234568 & 012345679 \end{matrix}

Then, |u_{g2}| = g, and [u_{g2}]_{b} ≡ 1 (mod g) if g is odd; 1+ \frac{g}{2} (mod g) if g is even, by Corollary 24. Hence, gcd([u_{g2}]_{b}, g) = 1 for odd g. For even g, we consider two cases: g = 4k or 4k + 2 for some integer k. If g = 4k, the number [u_{g2}]_{b} ≡_{g} 1 + \frac{g}{2} = 1 + 2k. Since gcd(1 + 2k, k) = 1 and gcd(1 + 2k, 4) = 1, gcd(1 + 2k, 4k) = 1. If g = 4k + 2, the number [u_{g2}]_{b} ≡_{g} 1 + \frac{g}{2} = 2(k + 1). Since gcd(k + 1, 2k + 1) = 1, gcd(2(k + 1), 2(2k + 1)) = 2. Hence,

gcd([u_{g2}]_{b}, g) = \begin{cases}1, & if g ≢ 2 (mod 4); \\ 2, & if g ≡ 2 (mod 4). \end{cases}

Therefore, by Corollary 21, the string u_{g3} = f_{g}(u_{g2}^{g}) if g ≢ 2 (mod 4); (ug2^{\frac{g}{2}}) otherwise. For example, u_{g3} for g = 3, 4, 5, 6 is as follows.

\begin{matrix}g & 3 & 4 & 5 & 6 \\ u_{g3} & 002113231 & 0014340322421131 & 0014211253224043351545031 & 001405446153223631 \end{matrix}

Observation 26. For any integer g ≥ 2,

u_{g1} = 1;  |u_{g1}| = 1;
u_{g2} = 012 ⋯ (g − 3)(g − 2)g;  |u_{g2}| = g;
u_{g3} = \begin{cases}f_{g}(u_{g2}^{g}), & if g ≢ 2 (mod 4); \\ f_{g}(ug2^{\frac{g}{2}}), & if g ≡ 2 (mod 4), \end{cases}  |u_{g3}| = \begin{cases}g|u_{g2}| = g^{2}, & if g ≢ 2 (mod 4); \\ \frac{g}{2}|u_{g2}| = \frac{g^{2}}{2} , & if g ≡ 2 (mod 4). \end{cases}

To calculate the string u_{g4}, we need to know gcd([u_{g3}]_{b}, g). Since |u_{g2}| = g, the number |u_{g2}| is even, if g is even. That is, there is no such case that g is even and |u_{g2}| is odd. If g ≢ 2 (mod 4), gcd([u_{g2}]_{b}, g) = 1. Hence, [f_{g}(u_{g2}^{g})]_{b} ≡ [u_{g2}]_{b} (mod g) by Corollary 24. Therefore,

gcd([u_{g3}]_{b}, g) = 1, if g ≢ 2 (mod 4).  (8)

Consider g ≡ 2 (mod 4). Since u_{g3} = f_{g}(ug2^{\frac{g}{2}}), let a′_{i}’s be digits satisfying u_{g3} = a′_{1}a′_{2} ⋯ a′_{\frac{g^{2}}{2}} , and Theorem 16 provides the following: For any m = 0, 1, 2, …, \frac{g}{2} − 1 and

any digit a = 0, 1, 2, …, g − 2,

\begin{aligned}a′_{mg+a+1} & = & \begin{cases}r(u_{g2}^{m}012 ⋯ (a − 2)(a − 1)), & if a < g − r(u_{g2}^{m}012 ⋯ (a − 1)); \\ r(u_{g2}^{m}012 ⋯ (a − 2)(a − 1)) + 1, & if a ≥ g − r(u_{g2}^{m}012 ⋯ (a − 1)); \end{cases} \\ a′_{(m+1)g} & = & r(u_{g2}^{m}012 ⋯ (g − 3)(g − 2)) + 1, \end{aligned} (9)

because g ≥ g − r(u_{g2}^{m}012 ⋯ (g − 3)(g − 2)). Since r(u_{g2}) ≡_{g} s(u_{g2}) = \frac{g(g+1)}{2} − g + 1 ≡_{g} \frac{g}{2} + 1,

\begin{matrix}r(u_{g2}^{m}012 ⋯ (a − 2)(a − 1)) ≡_{g} m (\frac{g}{2} + 1) + \frac{a(a − 1)}{2}; \\ r(u_{g2}^{m}012 ⋯ (g − 3)(g − 2)) ≡_{g} m (\frac{g}{2} + 1) + \frac{(g − 2)(g − 1)}{2} ≡_{g} (m + 1) (\frac{g}{2} + 1) . \end{matrix}

Since \frac{g}{2} + 1 is even and −g + 2(\frac{g}{2} + 1) = 2, gcd(g, \frac{g}{2} + 1) = 2. Hence,

\{m (\frac{g}{2} + 1) |m = 0, 1, 2, …, \frac{g}{2} − 1\} ≡_{g} \{0, 2, 4, …, g − 4, g − 2\}.

Since \frac{a(a−1)}{2} is even if a = 4q or 4q + 1; odd otherwise,

\{r (u_{g2}^{m}01 ⋯ (a − 1)) |m = 0, 1, …, \frac{g}{2} − 1\} = \begin{cases}\{0, 2, 4, …, g − 2\}, & if a = 4q or 4q + 1; \\ \{1, 3, 5, …, g − 1\}, & otherwise, \end{cases}

\{r (u_{g2}^{m}01 ⋯ (g − 2)) |m = 0, 1, …, \frac{g}{2} − 1\} = \{0, 2, …, g − 4, g − 2\}.

Therefore, by (9), for any digit a = 0, 1, …, g − 2,

\{a′_{mg+a+1}|m = 0, 1, 2, …, \frac{g}{2} − 1\}

= \begin{cases}\{2k_{1}, 2k_{2} + 1|0 ≤ 2k_{1} < g − a < 2k_{2} + 1 < g\}, & if a = 4q or 4q + 1; \\ \{2k_{1} + 1, 2k_{2}|0 < 2k_{1} + 1 < g − a < 2k_{2} ≤ g\}, & otherwise; \end{cases}

\{a′_{(m+1)g}|m = 0, 1, 2, …, \frac{g}{2} − 1\} = \{1, 3, 5, …, g − 3, g − 1\}.

Since g − 1 is not a digit in u_{g2}, every even digit a′ in u_{g3} is obtained by transforming the digit a’s in {0, 1, 2, …, g − 2}, where a = 4q or 4q + 1 with a < g − a′; a = 4q + 2 or 4q + 3 with a > g − a′. Every odd digit a′ in u_{g3} is obtained by transforming the digit a’s in {0, 1, 2, …, g − 2, g}, where a = 4q + 2 or 4q + 3 with a < g − a′; a = 4q or 4q + 1 with a > g − a′; a = g. That is,

if a′ is even, |u_{g3}|_{a′} = |{ a| a = 4q, 4q + 1 with 0 ≤ a < g − a′;
a = 4q + 2, 4q + 3 with g − a′ < a ≤ g − 2 }|;
if a′ is odd, |u_{g3}|_{a′} = |{ a| a = 4q + 2, 4q + 3 with 0 ≤ a < g − a′;
a = 4q, 4q + 1 with g − a′ < a < g − 1;
a = g  }|.

Let g = 4k + 2 for some integer k. Then,

\begin{aligned}|u_{g3}|_{0} & = |\{4q, 4q + 1|q = 0, 1, 2, …, k\} − \{4k + 1\}| = 2k + 1; \\ |u_{g3}|_{1} & = |\{4q + 2, 4q + 3|q = 0, 1, 2, …, k − 1\} ∪ \{4k + 2\}| = 2k + 1; \\ |u_{g3}|_{2} & = |\{4q, 4q + 1|q = 0, 1, 2, …, k − 1\}| = 2k, \end{aligned}

and for any p = 1, 2, …, k,

|u_{g3}|_{4p−1} =|{4q + 2|q = 0, …, k − p} ∪ {4q + 3|q = 0, …, k − p − 1}

∪ {4q|q = k − p + 1, …, k} ∪ {4q + 1|q = k − p + 1, …, k − 1} ∪ {4k + 2}|;

|u_{g3}|_{4p} =|{4q|q = 0, …, k − p} ∪ {4q + 1|q = 0, …, k − p}
∪ {4q + 2|q = k − p + 1, …, k − 1} ∪ {4q + 3|q = k − p, …, k − 1};
|u_{g3}|_{4p+1} =|{4q + 2|q = 0, …, k − p − 1} ∪ {4q + 3|q = 0, …, k − p − 1}

∪ {4q|q = k − p + 1, …, k} ∪ {4q + 1|q = k − p + 1, …, k − 1} ∪ {4k + 2}|;

|u_{g3}|_{4p+2} =|{4q|q = 0, …, k − p − 1} ∪ {4q + 1|q = 0, …, k − p − 1}
∪ {4q + 2|q = k − p, …, k − 1} ∪ {4q + 3|q = k − p, …, k − 1}.

Hence, |u_{g3}|_{4p−1} = |u_{g3}|_{4p} = 2k + 1 and |u_{g3}|_{4p+1} = |u_{g3}|_{4p+2} = 2k. Observation 27. Let g = 4k+2 for some integer k ≥ 0. For any digit a ∈ {0, 1, 2, …, g−1, g},

|u_{g3}|_{a} = \begin{cases}\frac{g}{2}, & if a = 0, 1, 4p − 1, 4p; \\ \frac{g}{2} − 1, & if a = 2, 4p + 1, 4p + 2, \end{cases} for p = 1, 2, …, k.

Lemma 28. For any g ≥ 2,

gcd([u_{g3}]_{b}, g) = \begin{cases}1, & if g ≢ 6 (mod 8) \\ 2, & if g ≡ 6 (mod 8). \end{cases}

Proof. The case when g ≢ 2 (mod 4) is shown in (8). Hence, assume g ≡ 2 (mod 4). Let g = 4k + 2 for some k. Then, by Observation 27,

∑_{a=0}^{g} a|u_{g3}|_{b} = (0 + 1 + ∑_{p=1}^{k}(4p − 1 + 4p)) · \frac{g}{2} + (2 + ∑_{p=1}^{k}(4p + 1 + 4p + 2)) · (\frac{g}{2} − 1)

= \frac{g}{2} + g · (1 + ∑_{p=1}^{k}(8p + 1)) − 2 − ∑_{p=1}^{k}(8p + 3)

≡_{g} (2k + 1) − 2 − 4k(k + 1) − 3k = −4k^{2} − 5k − 1 ≡_{g} −3k − 1 ≡_{g} k + 1.

Since [u_{g3}]_{b} ≡_{g} s(u_{g3}), the number [u_{g3}]_{b} ≡_{g} k + 1. Then, gcd ([u_{g3}]_{b}, 2(2k + 1))) = 1 if k is even; 2 if k is odd, since gcd(k + 1, 2k + 1) = 1. That is,

gcd([u_{g3}]_{b}, g) = \begin{cases}1, & if g ≡ 2 (mod 8); \\ 2, & if g ≡ 6 (mod 8). \end{cases}

If gcd([u_{g3}]_{b}, g) = 1, f_{g} transforms the string u_{g3}^{g} to u_{g4}. Hence,

u_{g4} = f_{g}(u_{g3}^{g}), if g ≢ 6 (mod 8).  (10)

We will focus on the case when g ≢ 6 (mod 8) from now on, because it is relatively easy to generate u_{gn} for all n ≥ 4.

Theorem 29. For any positive integer n ≥ 3, if g ≢ 6 (mod 8),

(1) gcd([u_{gn}]_{b}, g) = 1;

(2) u_{g,n+1} = f_{g}(u_{gn}^{g});

(3) |u_{gn}| = g^{n−1} if g ≢ 2 (mod 4); g^{n−1}/2 if g ≡ 2 (mod 8).

Proof. The proof is done by mathematical induction on n. The base case is shown in Lemma 28, (10), and Observation 26. Assume (1), (2), and (3) are true for all n − 1 ≥ 3:

gcd([u_{g,n−1}]_{b}, g) = 1;  u_{gn} = f_{g}(u_{g,n−1}^{g});  |u_{g,n−1}| = \begin{cases}g^{n−2}, & if g ≢ 2 (mod 4); \\ g^{n−2}/2, & if g ≡ 2 (mod 8). \end{cases}

Since g is even, |u_{g,n−1}| is even. Hence, there is no such case that g is even and |u_{g,n−1}| is odd. Since gcd([u_{g,n−1}]_{b}, g) = 1, the number [f_{g}(u_{g,n−1}^{g})]_{b} ≡ [u_{g,n−1}]_{b} (mod g) by Corollary 24. Since u_{gn} = f_{g}(u_{g,n−1}^{g}), (1) holds.

Since u_{gn} is the shortest repeating string in the string f_{g}^{n}(10^{N}), the shortest repeating string in f_{g}^{n+1}(10^{N}) should be f_{g}(u_{gn}^{h}) for some integer h. Since gcd([u_{gn}]_{b}, g) = 1 by (1), the string f_{g}(u_{gn}^{g}) repeats in f_{g}^{n+1}(10^{N}) by Corollary 21: for some string t,

f_{g}^{n+1}(10^{N}) = 0 (f_{g}(u_{gn}^{g}))^{⌊ \frac{N}{g|ugn|} ⌋} t.

For any 0 < h < g, the number [u_{gn}^{h}]_{b} ≡_{g} s(u_{gn}^{h}) = h · s(u_{gn}) ≡_{g} h · [u_{gn}]_{b} ≢ 0 (mod g), since gcd([u_{gn}]_{b}, g) = 1. Hence, the string f_{g}(u_{gn}^{h}) cannot repeat in f_{g}^{n+1}(10^{N}) by Theorem 16, if h < g. Therefore, f_{g}(u_{gn}^{g}) is the shortest repeating string in f_{g}^{n+1}(10^{N}). Hence, (2) holds.

By Induction hypothesis, |u_{gn}| = |f_{g}(u_{g,n−1}^{g})| = |u_{g,n−1}^{g}| = g|u_{g,n−1}|, so (3) holds.

Note 30. For any g ≢ 2 (mod 4), Theorem 29 holds for all n ≥ 1.

5 The number of digits in b-ary g-Collatz sequences

Let’s count the number of occurrences of each digit in the string u_{gn} for g ≢ 6 (mod 8). First, we simplify the notation.

Definition 31. For any positive integer n and any digit a ∈ {0, 1, 2, …, g},

a_{gn} := \begin{cases}|u_{g,n+1}|_{a}, & if g ≢ 2 (mod 4); \\ |u_{g,n+2}|_{a}, & if g ≡ 2 (mod 8). \end{cases}

For example, a_{gn} for g = 2, 3, 4, 10 is as follows.

\begin{matrix}n & 0_{2n} & 1_{2n} & 2_{2n} \\ 1 & 1 & 1 & 0 \\ 2 & 2 & 1 & 1 \\ 3 & 3 & 3 & 2 \\ 4 & 6 & 5 & 5 \\ 5 & 11 & 11 & 10 \end{matrix}  \begin{matrix}n & 0_{3n} & 1_{3n} & 2_{3n} & 3_{3n} \\ 1 & 1 & 1 & 0 & 1 \\ 2 & 2 & 3 & 2 & 2 \\ 3 & 7 & 7 & 6 & 7 \\ 4 & 20 & 21 & 20 & 20 \\ 5 & 61 & 61 & 60 & 61 \end{matrix}  \begin{matrix}n & 0_{4n} & 1_{4n} & 2_{4n} & 3_{4n} & 4_{4n} \\ 1 & 1 & 1 & 1 & 0 & 1 \\ 2 & 3 & 4 & 3 & 3 & 3 \\ 3 & 13 & 13 & 13 & 12 & 13 \\ 4 & 51 & 52 & 51 & 51 & 51 \\ 5 & 205 & 205 & 205 & 204 & 205 \end{matrix}

\begin{matrix}n & 0_{10,n} & 1_{10,n} & 2_{10,n} & 3_{10,n} & 4_{10,n} & 5_{10,n} & 6_{10,n} & 7_{10,n} & 8_{10,n} & 9_{10,n} & 10_{10,n} \\ 1 & 5 & 5 & 4 & 5 & 5 & 4 & 4 & 5 & 5 & 4 & 4 \\ 2 & 46 & 46 & 45 & 45 & 46 & 46 & 45 & 45 & 46 & 45 & 45 \\ 3 & 455 & 455 & 454 & 455 & 455 & 454 & 454 & 455 & 455 & 454 & 454 \\ 4 & 4546 & 4546 & 4545 & 4545 & 4546 & 4546 & 4545 & 4545 & 4546 & 4545 & 4545 \\ 5 & 45455 & 45455 & 45454 & 45455 & 45455 & 45454 & 45454 & 45455 & 45455 & 45454 & 45454 \end{matrix}

Lemma 32. For any positive integer n,

(1) ∑_{a=0}^{g} a_{gn} = g^{n} if g ≢ 2 (mod 4); \frac{g^{n+1}}{2} if g ≡ 2 (mod 8);

(2) a_{g,n+1} = ∑_{a′≠g−a} a′_{gn} for any g ≢ 6 (mod 8).

Proof. Theorem 29 (3) and Note 30 provide (1), and Corollary 23 provides (2).

Lemma 33. Suppose g ≢ 2 (mod 4). Then,

if n is odd, a_{gn} = \begin{cases}0_{gn}, & if a ≠ g − 1; \\ 0_{gn} − 1, & if a = g − 1, \end{cases} and if n is even, a_{gn} = \begin{cases}0_{gn}, & if a ≠ 1; \\ 0_{gn} + 1, & if a = 1. \end{cases}

Proof. The proof is done by mathematical induction. The base case is obvious by Observation 26: a_{g1} = 1 if a ≠ g − 1; 0 if a = g − 1, since u_{g2} = 012 ⋯ (g − 2)g. Induction hypothesis: suppose it is true for all n − 1. If n is even, n − 1 is odd. By induction hypothesis, a_{g,n−1} = 0_{g,n−1} for all a ≠ g − 1 and (g − 1)_{gn} = 0_{g,n−1} − 1. Since a_{gn} = ∑_{a′≠g−a} a′_{g,n−1} by Lemma 32 (2), a_{gn} = (g − 1)0_{g,n−1} + (g − 1)_{g,n−1} = g · 0_{g,n−1} − 1 for all a ≠ 1 and 1_{gn} = g · 0_{g,n−1}. Hence, a_{gn} = 0_{gn} for all a ≠ 1 and 1_{gn} = 0_{gn} + 1. Similarly, we can prove the case when n is odd.

Lemma 34. For any g = 8k + 2 for some integer k ≥ 1,

if n is odd, a_{gn} = \begin{cases}0_{gn}, & if a = 0, 1, 4p − 1, 4p; \\ 0_{gn} − 1, & if a = 2, 4p + 1, 4p + 2, \end{cases} for p = 1, 2, …, 2k;

if n is even, a_{gn} = \begin{cases}g_{gn} + 1, & if a = 4q, 4q + 1, g − 2; \\ g_{gn}, & if a = 4q + 2, 4q + 3, g − 1, g, \end{cases} for q = 0, 1, …, 2k − 1.

Proof. The proof is done by mathematical induction. The base case is shown in Observation 27. Induction Hypothesis: suppose it is true for all n − 1. If n is even, n − 1 is odd. By induction hypothesis, a_{g,n−1} = 0_{g,n−1} if a = 0, 1, 4p − 1, 4p and a_{g,n−1} = 0_{g,n−1} − 1 if a = 2, 4p + 1, 4p + 2 for p = 1, 2, …, 2k. By Lemma 32 (2), a_{gn} = (\frac{g}{2} + 1) · 0_{g,n−1} + (\frac{g}{2} − 1) · (0_{g,n−1} − 1) = g · 0_{g,n−1} − \frac{g}{2} + 1 if g − a = 2, 4p + 1, 4p + 2; \frac{g}{2} · 0_{g,n−1} + \frac{g}{2} · (0_{g,n−1} − 1) = g · 0_{g,n−1} − \frac{g}{2} otherwise. Since g = 8k + 2, the number g − a = 2, 4p + 1, 4p + 2 implies a = g −2, 4(2k −p)+1, 4(2k −p). Since p = 1, 2, …, 2k, the number 2k −p = 0, 1, …, 2k −1. Hence, a_{gn} = 0_{gn} if a = 4q, 4q+1, g−2; 0_{gn}−1 otherwise, for q = 0, 1, 2, …, 2k−1. Similarly, we can prove the case when n is odd.

When g = 2, we have a different arrangement for a_{gn}[1].

Note 35.

If n is odd, a_{2n} = \begin{cases}0_{2n}, & if a = 0, 1; \\ 0_{2n} − 1, & if a = 2, \end{cases} and if n is even, a_{2n} = \begin{cases}g_{2n}, & if a = 1, 2; \\ g_{2n} + 1, & if a = 0. \end{cases}

Corollary 36. For any positive integer n, if g ≢ 2 (mod 4),

(1) if n is odd, 0_{n} = g · 0_{g,n−1} + 1; (g − 1)_{gn} = g · 0_{g,n−1};

(2) if n is even, 0_{n} = g · 0_{g,n−1} − 1; 1_{gn} = g · 0_{g,n−1}.

Proof. If n is odd, n − 1 is even. By Lemma 33, a_{g,n−1} = 0_{g,n−1} for all a ≠ 1 and 1_{g,n−1} = 0_{g,n−1} + 1. Then, by Lemma 32 (2),

\begin{aligned}0_{gn} & = 0_{g,n−1} & +1_{g,n−1} & + 2_{g,n−1} + ⋯ + (g − 2)_{g,n−1} + (g − 1)_{g,n−1}; \\ (g − 1)_{gn} & = 0_{g,n−1} & & + 2_{g,n−1} + ⋯ + (g − 2)_{g,n−1} + (g − 1)_{g,n−1} + g_{g,n−1}. \end{aligned}

Hence, (1) is obtained. Similarly, we can prove (2).

Corollary 37. For any positive integer n, if g ≡ 2 (mod 8),

(1) if n is odd, 0_{n} = \frac{g}{2}0_{n−1} + \frac{g}{2}g_{n−1}; g_{n} = (\frac{g}{2} − 1)0_{n−1} + (\frac{g}{2} + 1)g_{n−1};

(2) if n is even, g_{n} = \frac{g}{2}0_{n−1} + \frac{g}{2}g_{n−1}; 0_{n} = (\frac{g}{2} − 1)g_{n−1} + (\frac{g}{2} + 1)0_{n−1}.

Proof. If n is odd, n−1 is even. By Lemma 34 and Note 35, a_{g,n−1} = 0_{g,n−1} if a = 4q, 4q+1, 2 and a_{g,n−1} = g_{g,n−1} if a = 4q + 2, 4q + 3, g − 1, g for any q = 0, 1, …, , 2k − 1. By Lemma 32 (2),

0_{gn} = 0_{g,n−1} + 1_{g,n−1} + ⋯ + (g − 1)_{g,n−1} and g_{gn} = 1_{g,n−1} + 2_{g,n−1} + ⋯ + g_{g,n−1}.

Hence, (1) is obtained. Similarly, we can prove (2).

Corollary 38. For any positive integer n,

if g ≢ 2 (mod 4), \begin{matrix}|\{a ∈ \{0, 1, 2, …, g\}|a_{gn} = 0_{gn} = g_{gn}\}| = g; \\ |\{a ∈ \{0, 1, 2, …, g\}|a_{gn} = 0_{gn} + (−1)^{n}\}| = 1, \end{matrix}
and if g ≡ 2 (mod 8), \begin{matrix}|\{a ∈ \{0, 1, 2, …, g\}|a_{gn} = 0_{gn}\}| = \frac{g}{2} + \frac{1−(−1)^{n}}{2} ; \\ |\{a ∈ \{0, 1, 2, …, g\}|a_{gn} = g_{gn}\}| = \frac{g}{2} + \frac{1+(−1)^{n}}{2} . \end{matrix}

Proof. It is obtained by sorting and counting a_{gn}’s using Lemma 33, 34 and Note 35.

Even if there are b distinct digits in a b-ary string, there are only two distinct values to identify a_{gn}, for any g and n. If g ≢ 2 (mod 4), there are g many a_{gn}’s with a_{gn} = 0_{gn} = g_{gn} and only one a_{gn} with a_{gn} ≠ 0_{gn}. If g ≡ 2 (mod 8), there are \frac{g}{2} +1 many a_{gn}’s with a_{gn} = 0_{gn} (g_{gn} for even n) and \frac{g}{2} many a_{gn}’s with a_{gn} ≠ 0_{gn} (g_{gn} for even n) for odd n. Hence, we consider the majority of a_{gn}’s and the minority of a_{gn}’s as follows:

Definition 39. For any g ≢ 6 (mod 8) and any positive integer n,

M_{gn} = \begin{cases}0_{gn}, & if n is odd; \\ g_{gn}, & if n is even, \end{cases} and m_{gn} = M_{gn} + (−1)^{n}.

For example, the following shows the first few M_{gn} and m_{gn} for g = 2, 3, 4, 5, 7, 10.

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 \\ M_{2n} & 1 & 1 & 3 & 5 & 11 & 21 \\ M_{3n} & 1 & 2 & 7 & 20 & 61 & 182 \\ M_{4n} & 1 & 3 & 13 & 51 & 205 & 819 \\ M_{5n} & 1 & 4 & 21 & 104 & 521 & 2604 \\ M_{7n} & 1 & 6 & 43 & 300 & 2101 & 14706 \\ M_{10,n} & 5 & 45 & 455 & 4545 & 45455 & 454545 \end{matrix} \begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 \\ m_{2n} & 0 & 2 & 2 & 6 & 10 & 22 \\ m_{3n} & 0 & 3 & 6 & 21 & 60 & 183 \\ m_{4n} & 0 & 4 & 12 & 52 & 204 & 820 \\ m_{5n} & 0 & 5 & 20 & 105 & 520 & 2605 \\ m_{7n} & 0 & 7 & 42 & 301 & 2100 & 14707 \\ m_{10,n} & 4 & 46 & 454 & 4546 & 45454 & 454546 \end{matrix}

Then, we have a recurrence relation as follows:

Theorem 40. For any g ≢ 6 (mod 8) and any integer n ≥ 3,

M_{gn} = (g − 1)M_{g,n−1} + gM_{g,n−2}.

Proof. By Lemma 36 and 37, for any positive integer n, whether n is even or odd,

if g ≢ 2 (mod 4), M_{gn} = gM_{g,n−1} + (−1)^{n−1} and m_{gn} = gM_{g,n−1};
if g ≡ 2 (mod 8), M_{gn} = \frac{g}{2}M_{g,n−1} + \frac{g}{2}m_{g,n−1} and m_{gn} = (\frac{g}{2} + 1) M_{g,n−1} + (\frac{g}{2} − 1) m_{g,n−1}.

Hence, if g ≢ 2 (mod 4),

M_{gn} = (g −1)M_{g,n−1} +M_{g,n−1} +(−1)^{n−1} = (g −1)M_{g,n−1} +m_{g,n−1} = (g −1)M_{g,n−1} +gM_{g,n−2}, and if g ≡ 2 (mod 8),

M_{gn} = \frac{g}{2}M_{g,n−1} + \frac{g}{2}m_{g,n−1}

= \frac{g}{2} (\frac{g}{2}M_{g,n−2} + \frac{g}{2}m_{g,n−2}) + \frac{g}{2}( (\frac{g}{2} + 1) M_{g,n−2} + (\frac{g}{2} − 1) m_{g,n−2})

= \frac{g^{2} + g}{2} · M_{g,n−2} + \frac{g^{2} − g}{2} · m_{g,n−2}

= \frac{g^{2} − g}{2} (M_{g,n−2} + m_{g,n−2}) + gM_{g,n−2}

= (g − 1)\frac{g}{2} (M_{g,n−2} + m_{g,n−2}) + gM_{g,n−2} = (g − 1)M_{g,n−1} + gM_{g,n−2}.

Furthermore, the explicit formulae are calculated as follows: Theorem 41. For any nonnegative integer n,

if g ≢ 2 (mod 4), M_{gn} = \frac{g^{n} − (−1)^{n}}{b}, and if g ≡ 2 (mod 8), M_{gn} = \frac{g}{2} · \frac{g^{n} − (−1)^{n}}{b} .

Proof. By Lemma 32 (1), Corollary 38, and Definition 39,

if g ≢ 2 (mod 4), gM_{gn} + m_{gn} = gM_{gn} + M_{gn} + (−1)^{n} = g^{n};
if g ≡ 2 (mod 8), (\frac{g}{2} + 1) M_{gn} + \frac{g}{2}m_{gn} = (\frac{g}{2} + 1) M_{gn} + \frac{g}{2}(M_{gn} + (−1)^{n}) = \frac{g^{n+1}}{2} .

Since b = g + 1, the explicit formulae are calculated as desired.

Notice that M_{g1} = 1 for all g ≢ 2 (mod 4) and M_{g1} = \frac{g}{2} for all g ≡ 2 (mod 8).

6 Generalized Jacobsthal numbers

For any nonnegative integer n, the n-th Jacobsthal number, J_{n} (\underline{A001045}), and the nth almost Jacobsthal numbers, A_{n} (\underline{A005578}) and B_{n} (\underline{A000975}), [6] are defined as follows:

J_{n} = \frac{2^{n} − (−1)^{n}}{3} ; A_{n} = ⌈\frac{2^{n}}{3} ⌉; B_{n} = ⌈\frac{2^{n} − 2}{3}⌉ ,  (11)

and they satisfy the following [1]: for any positive number n,

J_{n} = 1_{2n}, A_{n} = 0_{2n}, B_{n} = 2_{2n}, J_{n} + A_{n} + B_{n} = 2^{n}.  (12)

In order to generalize (12), we first generalize the sequences in (11).

Definition 42. For any integer g ≥ 2 and any nonnegative integer n, the nth g-Jacobsthal number, J_{gn}, and the nth almost g-Jacobsthal numbers, A_{gn} and B_{gn}, are defined as

J_{gn} = \frac{g^{n} − (−1)^{n}}{g + 1} ; A_{gn} := ⌈\frac{g^{n}}{g + 1}⌉; B_{n} := ⌈\frac{g^{n} − g}{g + 1} ⌉ .

The g-Jacobsthal numbers (J_{gn})_{g≥n} can be generated by the following recurrence as well. Lemma 43. The g-Jacobsthal numbers (J_{gn})_{n≥0} satisfy the following:

(1) J_{g0} = 0, J_{g1} = 1, J_{gn} = (g − 1)J_{g,n−1} + gJ_{g,n−2} for n ≥ 2;

(2) J_{g0} = 0, J_{g,n−1} + J_{g,n} = g^{n−1} for n ≥ 1.

Obviously, J_{2n} = J_{n}, A_{2n} = A_{n}, and B_{2n} = B_{n}. The sequence (A_{3n})_{n≥0} is identified as \underline{A122983}, and (J_{gn})_{n≥0} for g = 2, 3, 4, 5, 6 is identified as follows:

\begin{matrix}g & 2 & 3 & 4 & 5 & 6 \\ (J_{gn})_{n≥0} & \underline{A001045} & \underline{A015518} & \underline{A015521} & \underline{A015331} & \underline{A015540} \end{matrix}

Furthermore, consider Y_{gn} := J_{gn} + (−1)^{n} = \frac{g^{n}+g(−1)^{n}}{g+1} . Then, (Y_{gn})_{n≥0} for g = 2, 3, 4, 5, 6 is identified as follows:

\begin{matrix}g & 2 & 3 & 4 & 5 & 6 \\ (Y_{gn})_{n≥0} & \underline{A078008} & \underline{A0054878} & \underline{A109499} & \underline{A109500} & \underline{A109501} \end{matrix}

The following shows the first few J_{gn}’s.

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ J_{2n} & 0 & 1 & 1 & 3 & 5 & 11 & 21 & 43 \\ J_{3n} & 0 & 1 & 2 & 7 & 20 & 61 & 182 & 547 \\ J_{4n} & 0 & 1 & 3 & 13 & 51 & 205 & 819 & 3277 \\ J_{5n} & 0 & 1 & 4 & 21 & 104 & 521 & 2604 & 13021 \\ J_{6n} & 0 & 1 & 5 & 31 & 185 & 1111 & 6665 & 39991 \\ J_{7n} & 0 & 1 & 6 & 43 & 300 & 2101 & 14706 & 102943 \end{matrix}

Now, we can express M_{gn} and m_{gn} defined in Section 5 in terms of J_{gn}. Theorem 44. For any positive integer n,

(1) if g ≢ 2 (mod 4), M_{gn} = J_{gn} and m_{gn} = J_{gn} + (−1)^{n};

(2) if g ≡ 2 (mod 8), M_{gn} = \frac{g}{2}J_{gn} and m_{gn} = \frac{g}{2}J_{gn} + (−1)^{n}. Proof. It is obtained by Definition 39, Theorem 41, and Definition 42.

Hence, we can express all a_{gn}’s defined in Section 5 in terms of J_{gn}.

Corollary 45. For any positive integer n, if g ≢ 2 (mod 4),

a_{g,2n−1} = \begin{cases}J_{g,2n−1}, & if a ≠ g − 1; \\ J_{g,2n−1} − 1, & if a = g − 1 \end{cases}  and  a_{g,2n} = \begin{cases}J_{g,2n}, & if a ≠ 1; \\ J_{g,2n} + 1, & if a = 1, \end{cases}

and if g = 8k + 2 with k ≥ 1,

a_{g,2n−1} = \begin{cases}\frac{g}{2}J_{g,2n−1}, & if a = 0, 1, 4p − 1, 4p; \\ \frac{g}{2}J_{g,2n−1} − 1, & if a = 2, 4p + 1, 4p + 2, \end{cases}  for p = 1, 2, …, 2k;

a_{g,2n} = \begin{cases}\frac{g}{2}J_{g,2n}, & if a = 4q + 2, 4q + 3, g − 1, g; \\ \frac{g}{2}J_{g,2n} + 1, & if a = 4q, 4q + 1, g − 2, \end{cases} for q = 0, 1, …, 2k − 1.

Proof. It is obtained by Theorem 44, Definition 39, Lemma 33, and Lemma 34.

Now, let us compare A_{gn} and B_{gn} with J_{gn}. The following shows the first few A_{gn}, J_{gn}, and B_{gn}, when g = 3 and 4.

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ A_{3n} & 1 & 1 & 3 & 7 & 21 & 61 & 183 \\ J_{3n} & 0 & 1 & 2 & 7 & 20 & 61 & 182 \\ B_{3n} & 0 & 0 & 2 & 6 & 20 & 60 & 182 \end{matrix}  \begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ A_{4n} & 1 & 1 & 4 & 13 & 52 & 205 & 820 \\ J_{4n} & 0 & 1 & 3 & 13 & 51 & 205 & 819 \\ B_{4n} & 0 & 0 & 3 & 12 & 51 & 204 & 819 \end{matrix}

We can identify both A_{gn} and B_{gn} as J_{gn} or J_{gn} ± 1.

Lemma 46. For any nonnegative integer n,

A_{gn} = \begin{cases}J_{gn}, & if n is odd; \\ J_{gn} + 1, & if n is even. \end{cases} B_{gn} = \begin{cases}J_{gn} − 1, & if n is odd; \\ J_{gn}, & if n is even. \end{cases}

Proof. Since g^{n} = ((g + 1) − 1)^{n} = ∑_{i=0}^{n−1} \binom{n}{i}(g +1)^{n−i}(−1)^{i} +(−1)^{n}, the number g^{n} −(−1)^{n} is divisible by g + 1. Hence,

⌈\frac{g^{n}}{g + 1}⌉ = \frac{g^{n} − (−1)^{n}}{g + 1} + ⌈\frac{(−1)^{n}}{g + 1} ⌉ = J_{gn} + \begin{cases}0, & if n is odd; \\ 1, & if n is even. \end{cases}

and

⌈\frac{g^{n} − g}{g + 1} ⌉ = \frac{g^{n} − (−1)^{n}}{g + 1} + ⌈\frac{(−1)^{n} − g}{g + 1} ⌉ = J_{gn} + \begin{cases}−1, & if n is odd; \\ 0, & if n is even. \end{cases}

Therefore, we can generalize (12), when g ≢ 2 (mod 4).

Theorem 47. For any positive integer n, if g ≢ 2 (mod 4),

a_{gn} = \begin{cases}J_{gn}, & if a ≠ 1, g − 1; \\ A_{gn}, & if a = 1; \\ B_{gn}, & if a = g − 1, \end{cases} and (g − 1)J_{gn} + A_{gn} + B_{gn} = g^{n}.

Proof. Corollary 45 and Lemma 46 identify a_{gn}, and Lemma 32 (1) provides the relation.

To work on the case when g ≡ 2 (mod 8), we express A_{gn} and B_{gn} more explicitly. Corollary 48. For any nonnegative integer n,

A_{gn} = \frac{g^{n} + (\frac{g+1}{2} − 1)(−1)^{n} + \frac{g+1}{2}}{g + 1} and B_{gn} = \frac{g^{n} + (\frac{g+1}{2} − 1)(−1)^{n} − \frac{g+1}{2}}{g + 1} .  (13)

Proof. Since \frac{(−1)^{n}+1}{2} = 0 for odd n; 1 for even n, and \frac{(−1)^{n}−1}{2} = −1 for odd n; 0 for even n,

A_{gn} = \frac{g^{n} − (−1)^{n}}{g + 1} + \frac{(−1)^{n} + 1}{2} and B_{gn} = \frac{g^{n} − (−1)^{n}}{g + 1} + \frac{(−1)^{n} − 1}{2},

which is modified to (13).

Notice that A_{n} and B_{n} are as follows:

A_{n} = \frac{g^{n} + (\frac{3}{2} − 1)(−1)^{n} + \frac{3}{2}}{3} and B_{n} = \frac{g^{n} + (\frac{3}{2} − 1)(−1)^{n} − \frac{3}{2}}{3} .  (14)

We can obtain (13) from (14) by replacing \frac{3}{2} with \frac{g+1}{2}. However, we can consider replacing \frac{3}{2} with \frac{g+1}{g}. If we consider J_{2n} = \frac{2}{2} · J_{n}, A_{2n} = \frac{2}{2} · A_{n}, and B_{2n} = \frac{2}{2} · B_{n}, we can also consider replacing \frac{2}{2} with \frac{g}{2}. Taking all of these new considerations, we now have the following:

\frac{g}{2} · \frac{g^{n} − (−1)^{n}}{g + 1} ; \frac{g}{2} · \frac{g^{n} + (\frac{g+1}{g} − 1)(−1)^{n} + \frac{g+1}{g}}{g + 1} ; \frac{g}{2} · \frac{g^{n} + (\frac{g+1}{g} − 1)(−1)^{n} − \frac{g+1}{g}}{g + 1} . (15)

By simplifying (15), we have another generalization of (11). Definition 49. For any integer g ≥ 2 any nonnegative integer n, we define J′_{gn}, A′_{gn}, and B′_{gn} as follows:

J′_{gn} = \frac{g^{n+1} − g(−1)^{n}}{2(g + 1)} ; A′_{gn} = ⌈\frac{g^{n+1}}{2(g + 1)}⌉; B′_{gn} = ⌈\frac{g^{n+1} − g − 2}{2(g + 1)}⌉ .

Lemma 50. For any nonnegative integer n,

J′_{gn} = \frac{g}{2}J_{gn}; A′_{gn} = J′_{gn} + \begin{cases}0, & if n is odd; \\ 1, & otherwise \end{cases} ; B′_{gn} = J′_{gn} + \begin{cases}−1, & if n is odd; \\ 0, & otherwise \end{cases}

Proof. By Definition 42 and 49, it is obvious that J′_{gn} = \frac{g}{2}J_{gn}. Since

A′_{gn} = \frac{g^{n+1} − g(−1)^{n}}{2(g + 1)} + ⌈\frac{g(−1)^{n}}{2(g + 1)}⌉ and B′_{gn} = \frac{g^{n+1} − g(−1)^{n}}{2(g + 1)} + ⌈\frac{g(−1)^{n} − g − 2}{2(g + 1)}⌉ ,

A′_{gn} and B′_{gn} are shown as desired.

Theorem 51. For any positive integer n, if g = 8k + 2 for some integer k ≥ 1,

a_{gn} = \begin{cases}J′_{gn}, & if a = 4p − 1 for p = 1, 2, …, 2k; \\ A′_{gn}, & if a = 0, 1, 4p for p = 1, 2, …, 2k; \\ B′_{gn}, & if a = 4p − 2, g − 1, g for p = 1, 2, …, 2k; \\ J′_{gn} + (−1)^{n}, & if a = 4p + 1 for p = 1, 2, …, 2k − 1, \end{cases}

and

(4k − 1)J′_{gn} + (2k + 2)A′_{gn} + (2k + 2)B′_{gn} = \frac{g^{n+1}}{2} − (2k − 1)(−1)^{n}.

Proof. Lemma 50 and Corollary 45 identify a_{gn}, and Lemma 32 (1) provides

2k · J′_{gn} + (2k + 2)A′_{gn} + (2k + 2)B′_{gn} + (2k − 1) (J′_{gn} + (−1)^{n}) = \frac{g^{n+1}}{2} .

7 Acknowledgments

I would like to thank the reviewer for his/her suggestions, which helped to improve this paper.

References

[1] J. Choi, Ternary modified Collatz sequences and Jacobsthal numbers, J. Integer Seq. 19 (2016) 16.75.

[2] L. Collatz, On the motivation and origin of the (3n + 1) problem, J. Qufu Normal University, Natural Science Edition 3 (1986) 9–11.

[3] J. Conway, Unpredictable iterations, Conf. Proc. Number Theory, Univ. of Colorado, Boulder(1972) 49-52.

[4] R. Terras, A stopping time problem on the positive integers, Acta Arith. 30 (1976) 241–252.

[5] J. Shallit, A Second Course in Formal Languages and Automata Theory, Cambridge University Press, 2009.

[6] N. J. A. Sloane, Online Encyclopedia of Integer Sequences, http://oeis.org.

2010 Mathematics Subject Classification: Primary 11A67; Secondary 11B75. Keywords: Collatz problem, Jacobsthal number, base-b representation, 3n + 1 problem.

(Concerned with sequences \underline{A000975}, \underline{A001045}, \underline{A005578}, \underline{A015331}, \underline{A015518}, \underline{A015521}, \underline{A015540}, \underline{A054878}, \underline{A078008}, \underline{A109499}, \underline{A109500}, \underline{A109501}, and \underline{A122983}.)

Received November 1 2017; revised version received March 29 2018; May 11 2018. Published in Journal of Integer Sequences, May 25 2018.

Return to Journal of Integer Sequences home page.