Ternary Modified Collatz Sequences 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

We show how to apply the Collatz function and the modified Collatz function to the ternary representation of a positive integer, and we present the ternary modified Collatz sequence starting with a multiple of 3^{N} for an arbitrary large integer N. Each ternary string in the sequence is shown to have a repeating string, and the number of occurrences of each digit in each repeating string is identified as a Jacobsthal number, or one more or one less than a Jacobsthal number.

1 Introduction

Definition 1. [1] For any positive integer m, the Collatz function f on m is defined as follows:

f(m) := \{ \begin{matrix}\frac{m}{2}, & if m is even; \\ 3m + 1, & if m is odd. \end{matrix}  (1)

For any positive integer m, consider a sequence satisfying: a_{0} = m and a_{n} = f(a_{n−1}) for n > 1. Collatz [1] asked if there exists n such that a_{n} = 1, for any positive integer m = a_{0}.

The Collatz problem is still open, but it is known [2] that for every positive integer m < 5.7646 · 10^{18} there exists n > 0 such that f^{n}(m) = 1. If there is an integer m such that f^{n}(m) ≠ 1 for any integer n, we can assume m is a large odd integer. If m is even, we can divide m by a power of 2 to find a large odd integer. To find the Collatz sequence starting with a large odd integer m, we calculate f(m) = 3m + 1 and f^{2}(m) = \frac{3m+1}{2}. To make these calculations simpler, we would like to modify the Collatz function, since f^{2}(m) is always \frac{3m+1}{2} for any odd integer m.

Definition 2. [3] For any positive integer m, the modified Collatz function g on m is defined as follows:

g(m) := \{ \begin{matrix}f(m) = \frac{m}{2}, & if m is even; \\ f^{2}(m) = \frac{3m+1}{2}, & if m is odd. \end{matrix}  (2)

To make the calculation 3m + 1 for a large integer m easier, we use the ternary representation of integers. In this paper, we show how to apply the Collatz function and the modified Collatz function to the ternary representation of integers. Then we study the ternary representation of the modified Collatz sequence starting with 3^{N} for an arbitrary large integer N. As the ternary representation of 3^{N} is the string 100 ⋯ 0 with a digit 1 and N 0 digits, the ternary representation of g^{n}(3^{N}) has a repeating string of digits, for significantly many nonnegative integers n. The number of occurrences of each digit in each repeating string will be counted and identified. Then we consider a multiple of 3^{N} for an arbitrary large integer N.

Section 2 clarifies notation for this paper. Sections 3 and 4 show how to apply the Collatz function and the modified Collatz function to the ternary representation of integers. In Section 5, a repeating string of digits in the ternary modified Collatz sequence starting with the string 100 ⋯ 0 is studied, and the number of occurrences of each digit in each repeating string is counted. Section 6 shows that the number of 1 digits counted in Section 5 is identified as a Jacobsthal number, and suggests an extension of Jacobsthal numbers. Section 7 generalizes Section 5.

2 Notation

Every ternary representation of an integer is a finite string in {0, 1, 2}^{∗}, which is the set of all finite strings consisting of digits 0, 1, 2. The set {0, 1, 2}^{∗} 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:

Definition 3. [5] For any finite string x and a digit a, |x| is defined to be the number of digits in x, and |x|_{a} is defined to be the number of occurrences of digit a’s in x.

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

|x| = |x|_{0} + |x|_{1} + |x|_{2}.

For example, |00021121| = 8, |00021121|_{0} = 3, |00021121|_{1} = 3, |00021121|_{2} = 2 and 8 = 3 + 3 + 2.

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

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},

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 ϵ.

Then concatenation is associative, and the length of the concatenation of two strings is the sum of each string length.

Lemma 6. For any ternary strings x, y, and z, xyz = (xy)z = x(yz).

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

For example, 102 00 = 10200, (10)^{3} = 101010, and 1 = 1 (10)^{0}. |102 00| = |102| + |00| = 3 + 2 = 5 and |(10)^{3}| = 3|10| = 3 · 2 = 5.

For a finite string x, a substring y is called a head of x if there exists a string z such that x = yz, and a substring z is called a tail of x if there exists a string y such that x = yz [4]. For example, 102 and 10 are heads of 10200, and 00 and 0 are tails of 10200. Notice that a head or a tail of a string is not necessarily unique.

Since the ternary representation of an integer is a string in {0, 1, 2}^{∗}, we call the ternary representation of an integer as a ternary string throughout this paper. When we have to distinguish an integer and its ternary string, we use the following notation. Notation 8. For any integer m with base 3-representation x, we write m = [x]_{3} or (m)_{3} = x.

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

Throughout the paper we use the convention that m is an integer and x is its ternary representation. When we apply the functions f and g we often phrase this in terms of how f and g transform x to another ternary representation, and do not mention m. Notation 9. For a ternary string x, the ternary representation of f([x]_{3}) and g([x]_{3}) are denoted by f(x) and g(x), respectively. That is, f(x) = (f([x]_{3}))_{3} and g(x) = (g([x]_{3}))_{3}.

Then the ternary string g(x) is identified as follows:

Lemma 10. For a ternary string x,

g(x) = \{ \begin{matrix}f(x), & if x is even; \\ f(f(x)), & if x is odd. \end{matrix}

To apply the Collatz function to a ternary string, it is important to know whether a given ternary string represents an even or odd integer. To simplify the discussion, we say a ternary string is even or odd.

Definition 11. For any ternary string x, x is said to be odd if [x]_{3} is odd, and x is said to be even if [x]_{3} is even.

3 The Collatz function on ternary strings

Every ternary string represents a sum of powers of 3. For example, [102211]_{3} = 1 · 3^{5} + 2 · 3^{3} + 2 · 3^{2} + 1 · 3^{1} + 1 · 3^{0}. To determine the evenness or oddness of a sum, it does not matter how many even numbers are added. Instead, we have to count how many odd numbers are added. Since an even digit times a power of 3 is even, and an odd digit times a power of 3 is odd, we count odd digits (i.e., the 1’s) in a ternary string. For example, the string 102211 is odd, since |102211|_{1} = 3 is odd.

Observation 12. For a ternary string x, |x|_{1} is odd, if and only if x is odd.

For an odd ternary string x, the ternary string f(x) = (3[x]_{3} + 1)_{3}. Since (3)_{3} = 10, the ternary string of the product 3[x]_{3} is the concatenation x0. Adding 1 to 3[x]_{3} yields replacing the tail digit 0 in the string x0 with the digit 1.

Lemma 13. For any odd ternary string x, f(x) = x1.

Proof. 3[x]_{3} + 1 = [10]_{3}[x]_{3} + 1 = [x0]_{3} + 1 = [x1]_{3}.

For example, f(11102) = 11102 0 + 1 = 111021.

Now we consider even ternary strings. First, consider a ternary string x without any 1’s, i.e., x only consists of 0’s or 2’s. Since x is even, the Collatz function f divides [x]_{3} by 2. Since every digit in the string x is divisible by 2, f replaces each occurrence of the digit 2 with the digit 1, and keeps each digit 0 as it is. For example, the ternary f(220020) = 110010.

Lemma 14. For a ternary string x = a_{1}a_{2} ⋯ a_{|x|}, if each a_{i} is either 0 or 2,

f(x) = a′_{1}a′_{2} ⋯ a′_{|x|}, where a′_{i} = \{ \begin{matrix}0, & if a_{i} = 0; \\ 1, & if a_{i} = 2. \end{matrix}

Proof. Since |x|_{1} = 0, x is even, so f(x) = (\frac{[x]_{3}}{2} )_{3}. Since |a_{1}a_{2} ⋯ a_{i−1}|_{1} = 0, a_{1}a_{2} ⋯ a_{i−1} is even for any i = 1, …, |x|. Hence, when [a_{1}a_{2} ⋯ a_{i−1}]_{3} is divided by 2, the remainder is 0. Hence, the ith digit a′_{i} in f(x) is \frac{a_{i}}{2} , which is 0 if a_{i} = 0; 1 if a_{i} = 2.

Secondly, consider another even ternary string 1x1, where the string x does not contain any digit 1.

Lemma 15. For a ternary string x = a_{1}a_{2} ⋯ a_{|x|}, if each a_{i} is either 0 or 2,

f(1x1) = 0a′_{1}a′_{2} ⋯ a′_{|x|}2, where a′_{i} = \{ \begin{matrix}1, & if a_{i} = 0; \\ 2, & if a_{i} = 2. \end{matrix}

Proof. Since |1x1|_{1} = 2 is even, 1x1 is even, so f(1x1) = (\frac{[1x1]_{3}}{2} )_{3}. The head digit in (\frac{[1x1]_{3}}{2} )_{3} is 0, because the head digit 1 in 1x1 is less than the divisor 2. Since |1a_{1}a_{2} ⋯ a_{i−1}|_{1} = 1 is odd, 1a_{1}a_{2} ⋯ a_{i−1} is odd for any i = 1, …, |x|, so the remainder when [1a_{1}a_{2} ⋯ a_{i−1}]_{3} is divided by 2 is 1. Hence, the (i + 1)th digit a′_{i} in f(1x1) is the quotient when [1a_{i}]_{3} is divided by 2, i.e. a′_{i} = ⌊\frac{[1a_{i}]_{3}}{2} ⌋, which is 1 if a_{i} = 0; 2 if a_{i} = 2. Similarly, since 1x is odd, the remainder when [1x]_{3} is divided by 2 is 1. Hence, the last digit in f(1x1) is \frac{[11]_{3}}{2} = 2.

Note 16. In this paper, for any string x with the head digit 1, when f transforms the head digit 1 to digit 0, we keep the new head digit 0, so that |x| = |f(x)|.

For example, f(12200201) = 02211212, so |f(12200201)| = |02211212|.

Now consider a ternary string yz, where y and z are even ternary strings.

Lemma 17. For any even ternary strings y and z,

f(yz) = f(y)f(z).  (3)

Proof. Since y and z are even, |y|_{1} and |z|_{1} are even, and f(y) = (\frac{[y]_{3}}{2} )_{3} and f(z) = (\frac{[z]_{3}}{2} )_{3}.

Since |yz|_{1} = |y|_{1} + |z|_{1} is even, yz is even, so f(yz) = (\frac{[yz]_{3}}{2} )_{3}. Since [yz]_{3} = [y0^{|z|}]_{3} + [z]_{3},

\frac{[yz]_{3}}{2} = \frac{[y0^{|z|}]_{3}}{2} + \frac{[z]_{3}}{2} = [(\frac{[y]_{3}}{2} )_{3} 0^{|z|}]_{3} + \frac{[z]_{3}}{2} .

Since |z| = |f(z)| and \frac{[z]_{3}}{2} = [f(z)]_{3},

f(yz) = ([f(y)0^{|f(z)|}]_{3} + [f(z)]_{3})_{3} = ([f(y)f(z)]_{3})_{3} = f(y)f(z).

Now consider an arbitrary even ternary string x. By Observation 12, x has even number of 1’s, so we can separate x into small strings, each of which can be a string of the type in either Lemma 14 or Lemma 15. That is, x = y_{1}y_{2} ⋯ y_{k}, for some integer k, such that y_{i} = either x_{i} or 1x_{i}1, where |x_{i}|_{1} = 0 for all i. For example, x = 10210022112012001 = 1021 0022 11 20 12001. Applying Lemma 14 and 15, we find each ternary string f(y_{i}) for all i. Then we use the following theorem to put them together for f(x).

Theorem 18. For any even ternary string y_{i} for i = 1, 2, …, k,

f(y_{1}y_{2} ⋯ y_{k}) = f(y_{1})f(y_{2}) ⋯ f(y_{k}).  (4)

Proof. By Lemma 6, y_{1}y_{2} ⋯ y_{k} = y_{1} (y_{2} ⋯ y_{k}). Then, by Lemma 17, f(y_{1}y_{2} ⋯ y_{k}) = f(y_{1})f(y_{2} ⋯ y_{k}). Continuing this, (4) is obtained.

Example 19. The Collatz function f transforms the ternary string 10210022112012001 to the following ternary string:

f(10210022112012001) = f(1021 0022 11 20 12001)
= f(1021)f(0022)f(11)f(20)f(12001)
= 0122 0011 02 10 02112 = 01220011021002112.

4 The modified Collatz function on ternary strings

We have found how to transform a ternary string x into the ternary string f(x) in Section 3. We use the same method to find the ternary string g(x) for any ternary string x, since

g(x) = \begin{cases}f(x) = (\frac{[x]_{3}}{2} )_{3} , & if x is even; \\ f(x1) = (\frac{[x1]_{3}}{2} )_{3} , & if x is odd, \end{cases}  (5)

by Lemma 10 and Lemma 13.

Lemma 20. For any ternary strings y and z, if y is even,

g(yz) = g(y)g(z).  (6)

Proof. Since y is even, |y|_{1} is even. Hence, |yz|_{1} = |y|_{1}+|z|_{1} is even, iff |z|_{1} is even. Therefore, if z is even, yz is even, so g(yz) = f(yz). By Lemma 17, (6) is obtained.

If z is odd, yz is odd and z1 is even. By (5) and Lemma 17,

g(yz) = f(yz1) = f(y)f(z1) = g(y)g(z).

Theorem 21. Let y_{i} and z be ternary strings for i = 1, 2, … k. If every y_{i} is even,

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

Proof. Since every y_{i} is even, y_{1}y_{2} ⋯ y_{k} is even, so g(y_{i}) = f(y_{i}) for each i and g(y_{1}y_{2} ⋯ y_{k}) = f(y_{1}y_{2} ⋯ y_{k}). By Lemma 20, g(y_{1}y_{2} ⋯ y_{k}z) = g(y_{1}y_{2} ⋯ y_{k})g(z) = f(y_{1}y_{2} ⋯ y_{k})g(z). Applying Theorem 18, (7) is obtained.

Lemma 22. For a ternary string x = a_{1}a_{2} ⋯ a_{|x|}, if each a_{i} is either 0 or 2,

(a) g(x) = a′_{1}a′_{2} ⋯ a′_{|x|}, where a′_{i} = 0, if a_{i} = 0; a′_{i} = 1, if a_{i} = 2;

(b) g(1x1) = 0a′_{1}a′_{2} ⋯ a′_{|x|}2, where a′_{i} = 1, if a_{i} = 0; a′_{i} = 2, if a_{i} = 2; (c) g(1x) = 0a′_{1}a′_{2} ⋯ a′_{|x|}2, where a′_{i} = 1, if a_{i} = 0; a′_{i} = 2, if a_{i} = 2.

Proof. Since x and 1x1 are even, g(x) = f(x) and g(1x1) = f(1x1). Hence, (a) and (b) are obtained by Lemmas 14 and 15. Since 1x is odd, g(1x) = f(1x1) by (5). Since 1x1 is even, f(1x1) = g(1x1), so we apply (b) to get (c).

Strategy 23. For any ternary string x, the modified Collatz function g transforms x into the ternary string g(x) as follows:

1. break x: x = y_{1}y_{2} ⋯ y_{k}y_{k+1}, for some integer k, such that y_{i} = either x_{i} or 1x_{i}1 for all i ≤ k, and y_{k+1} = x_{k+1}, 1x_{k+1}1, or 1x_{k+1}, where |x_{i}|_{1} = 0 for all i = 1, 2, …, k, k + 1;

2. find g(y_{i}): apply Lemma 22 to find each ternary string g(y_{i});

3. concatenate all g(y_{i})’s: apply Theorem 21 to find the ternary string g(x).

Example 24. The modified Collatz function transforms the ternary string 120100211102 to the following ternary string:

g(120100211102) = g(1201 002 11 102)

= g(1201)g(002)g(11)g(102)

= 0212 001 02 0122 = 0212001020122

In this paper, for any ternary string x with the head digit 1, when g transforms the head digit 1 to digit 0, we keep the new head digit 0 in g(x), so the length of the ternary string g(x) can be calculated as follows: Note 25. For any ternary strings x, |g(x)| = |x|, if x is even; and |x| + 1, if odd.

In order to apply the modified Collatz function g to a lengthy ternary string in Section 5 and 7, we need to study more on g.

Theorem 26. For any ternary string x, let a_{i} ∈ {0, 1, 2} such that x = a_{1}a_{2} ⋯ a_{|x|}. Then

g(x) = \{ \begin{matrix}a′_{1}a′_{2} ⋯ a′_{|x|}, & if x is even; \\ a′_{1}a′_{2} ⋯ a′_{|x|}2, & if x is odd, \end{matrix}

where

a′_{i} = \{ \begin{matrix}0, & if a_{i} = 0; \\ 0, & if a_{i} = 1; \\ 1, & if a_{i} = 2, \end{matrix}  a′_{i} = \{ \begin{matrix}1, & if a_{i} = 0; \\ 2, & if a_{i} = 1; \\ 2, & if a_{i} = 2, \end{matrix}
if |a_{1}a_{2} ⋯ a_{i−1}|_{1} is even;  if |a_{1}a_{2} ⋯ a_{i−1}|_{1} is odd.

Proof. By(5), g divides either [x]_{3} or [x1]_{3} by 2. Since x = a_{1} ⋯ a_{i−1}a_{i} ⋯ a_{|x|} and x1 = a_{1} ⋯ a_{i−1}a_{i} ⋯ a_{|x|}1, the ith digit in g(x) is

a′_{i} = \begin{cases}⌊\frac{a_{i}}{2} ⌋, & if the remainder is 0 when [a_{1} ⋯ a_{i−1}]_{3} is divided by 2; \\ ⌊\frac{1a_{i}}{2} ⌋, & if the remainder is 1 when [a_{1} ⋯ a_{i−1}]_{3} is divided by 2, \end{cases}

for all i ≤ |x|. Applying Observation 12 and calculating ⌊\frac{a_{i}}{2} ⌋ and ⌊\frac{1a_{i}}{2} ⌋, a′_{i} can be obtained as desired. If x is odd, |g(x)| = |x| + 1, so we have to find one more digit. Since the remainder is 1 when [x]_{3} is divided by 2, the last digit in g(x) = (\frac{[x1]_{3}}{2} )_{3} is \frac{[11]_{3}}{2} = 2.

Theorem 27. For any odd ternary string x, let a_{i} ∈ {0, 1, 2} such that x = a_{1}a_{2} ⋯ a_{|x|}. Then the ternary string g(xx) = a′_{1}a′_{2} ⋯ a′_{|x|}a′_{|x|+1} ⋯ a′_{2|x|} such that

\{a′_{i}, a′_{|x|+i}\} = \{ \begin{matrix}\{0, 1\}, & if a_{i} = 0; \\ \{0, 2\}, & if a_{i} = 1; \\ \{1, 2\}, & if a_{i} = 2. \end{matrix}  (8)

Proof. Let a_{|x|+i} be the (|x| + i)th digit in the string xx for any i ≤ |x|. Then a_{|x|+i} = a_{i}, so |a_{1}a_{2} ⋯ a_{|x|+i−1}|_{1} = |a_{1}a_{2} ⋯ a_{|x|}|_{1}+|a_{|x|+1}a_{|x|+2} ⋯ a_{|x|+i−1}|_{1} = |x|_{1}+|a_{1}a_{2} ⋯ a_{i−1}|_{1}. Since x is odd, |x|_{1} is odd. Hence, |a_{1}a_{2} ⋯ a_{i−1}|_{1} is odd, iff |a_{1}a_{2} ⋯ a_{|x|+i−1}|_{1} is even. Since a_{i} = a_{|x|+i}, {a′_{i}, a′_{|x|+i}} collects both images of a_{i} in Theorem 26.

Corollary 28. For an odd ternary string x, the ternary string g(xx) satisfies the following:

(a) |g(xx)|_{0} = |x|_{0} + |x|_{1};

(b) |g(xx)|_{1} = |x|_{0} + |x|_{2};

(c) |g(xx)|_{2} = |x|_{1} + |x|_{2}.

Proof. By Theorem 27, g transforms one-half of the 0 digits and one-half of the 1 digits into the string xx as 0’s, so |g(xx)|_{0} ≥ \frac{1}{2}|xx|_{0} + \frac{1}{2}|xx|_{1} = |x|_{0} + |x|_{1}. Since there is no other way to get digit 0’s in g(xx), (a) is obtained. Similarly, (b) and (c) are proved.

Corollary 29. For any odd ternary strings x,

(a) g(xx) is odd, if and only if |x| is even;

(b) |g(xx)| = 2|x|.

Proof. By Corollary 28 (b), |g(xx)|_{1} = |x|_{0} + |x|_{2} = |x| − |x|_{1}. Since x is odd, |x|_{1} is odd by Observation 12. Hence, (a) is obtained. Since |xx|_{1} = 2|x|_{1} is even, xx is even. By Note 25, |g(xx)| = |xx| = 2|x|.

Corollary 30. For any ternary strings x and z and for any positive integer k,

g(x^{k}z) = (g(xx))^{⌊ \frac{k}{2} ⌋} g(z_{1}),  (9)

where z_{1} = xz, if k is odd, and z_{1} = z, if k is even.

Proof. Since k = 2 · ⌊\frac{k}{2}⌋ + p, where p = 1 for odd k; 0 for even k, x^{k} = (xx)^{⌊ \frac{k}{2} ⌋}x^{p}. Since xx is even, apply Theorem 21 to provide (9).

Theorem 31. For any ternary strings y and z,

g(yz) = (⌊\frac{[y]_{3}}{2} ⌋)_{3} z′,  (10)

for some ternary string z′ such that |z′| = |z|, if yz is even; |z| + 1, if odd.

Proof. If y is even, the ternary string g(yz) = g(y)g(z) by Lemma 20, and yz is even, iff z is even. Since g(y) = (\frac{[y]_{3}}{2} )_{3}, let z′ = g(z). Then |z′| = |z| if yz is even; |z| + 1 if odd.

Assume that y is odd. If z is odd, yz is even. Then [y]_{3} − 1 and 1z are even, and [yz]_{3} = [([y]_{3} − 1)_{3}0^{|z|}]_{3} + [1z]_{3}. Since |1z| = |z| + 1 and (\frac{[1z]_{3}}{2} )_{3} = 0z′ for some ternary string z′ such that |z′| = |z|,

g(yz) = (\frac{[yz]_{3}}{2} )_{3} = (\frac{[([y]_{3} − 1)_{3}0^{|z′|}]_{3}}{2} + [0z′]_{3})_{3} = (\frac{[y]_{3} − 1}{2})_{3} z′.

If z is even, yz is odd. Then [y]_{3} − 1 and 1z1 are even and [yz1]_{3} = [([y]_{3} − 1)_{3}0^{|z1|}]_{3} + [1z1]_{3}. Since |1z1| = |z| + 2 and (\frac{[1z1]_{3}}{2} )_{3} = 0z′2 for some ternary string z′ such that |z′| = |z| by Theorem 26,

g(yz) = (\frac{[yz1]_{3}}{2} )_{3} = (\frac{[([y]_{3} − 1)_{3}0^{|z′|+1}]_{3}}{2} + [0z′2]_{3})_{3} = (\frac{[y]_{3} − 1}{2})_{3} z′2.

Since \frac{[y]_{3}−1}{2} = ⌊\frac{[y]_{3}}{2} ⌋, (10) is obtained.

5 Ternary modified Collatz sequences with a repeating string

A power of 3, 3^{N}, for an arbitrary large positive integer N is complicated, but its ternary representation is simple: (3^{N})_{3} = 1 0^{N}. Consider the ternary representation of the modified Collatz sequence starting with the string 1 0^{N}. For example, the first few numbers in the ternary modified Collatz sequence starting with 1 0^{50} are as follows:

\begin{aligned}1 0^{50} & = 100000000000000000000000000000000000000000000000000; \\ g^{1}(1 0^{50}) & = 0111111111111111111111111111111111111111111111111112; \\ g^{2}(1 0^{50}) & = 0020202020202020202020202020202020202020202020202021; \\ g^{3}(1 0^{50}) & = 00101010101010101010101010101010101010101010101010102; \\ g^{4}(1 0^{50}) & = 000120012001200120012001200120012001200120012001200122. \end{aligned}

Notice that there is a substring repeating in the ternary string g^{n}(1 0^{50}), when we ignore the head digit and a tail string. For example, the string 02 repeats 25 times and the string 0202 repeats 12 times in the ternary string g^{2}(1 0^{50}).

Definition 32. For an arbitrary large integer N and a positive integer n, the nth repeating string r_{n} of the ternary string g^{n}(1 0^{N}) is defined to be the shortest string repeating ⌊\frac{N}{|r_{n}|}⌋ times in g^{n}(1 0^{N}) such that

g^{n}(1 0^{N}) = 0 (r_{n})^{⌊^{\frac{N}{|rn|}}⌋} t,

for some ternary string t.

For n = 1, 2, …, 7, the nth repeating string r_{n} in the ternary string g^{n}(1 0^{N}), for an arbitrary large integer N, is as follows:

r_{1} = 1;
r_{2} = 02;
r_{3} = 01;
r_{4} = 0012;
r_{5} = 00021121;
r_{6} = 0001021011122022;
r_{7} = 00001220020221221112010120211011.

Theorem 33. For any positive integer n, r_{n+1} = g(r_{n}r_{n}), if r_{n} is odd.

Proof. By Definition 32, g^{n}(1 0^{N}) = 0 (r_{n})^{⌊^{\frac{N}{|rn|}}⌋} t for some ternary string t. Then, by Theorem 21 and Corollary 30,

g^{n+1} (1 0^{N}) = g (0 (r_{n})^{⌊^{\frac{N}{|rn|}}⌋} t) = g(0) (g(r_{n}r_{n}))^{⌊⌊ \frac{N}{|rn|} ⌋/2⌋} g(t_{1}),

where t_{1} = r_{n}t, if ⌊\frac{N}{|r_{n}|}⌋ is odd; t, if even. Since ⌊⌊\frac{N}{|r_{n}|}⌋/2⌋ = ⌊\frac{N}{2|r_{n}|}⌋, the ternary string

g(r_{n}r_{n}) is a string repeating ⌊\frac{N}{2|r_{n}|}⌋ times in the ternary string g^{n+1}(1 0^{N}).

Since r_{n} is the shortest string repeating in g^{n}(1 0^{N}), |r_{n+1}| should be a multiple of |r_{n}|. Since r_{n} is odd, g(r_{n}r_{n}) ≠ g(r_{n})g(r_{n}) by Theorem 27. Hence, |r_{n+1}| ≠ |r_{n}|. Since |g(r_{n}r_{n})| = 2|r_{n}| by Corollary 29 (b), the ternary string g(r_{n}r_{n}) is the shortest string repeating ⌊\frac{N}{|g(r_{n}r_{n})|}⌋ times in the ternary string g^{n+1}(1 0^{N}).

Corollary 34. For every integer n ≥ 3, r_{n} is odd and |r_{n}| = 2^{n−2}.

Proof. The proof is done by mathematical induction. r_{3} = 01 is odd and |01| = 2^{3−2}. Assume that r_{n} is odd and |r_{n}| = 2^{n−2}. Then r_{n+1} = g(r_{n}r_{n}) by Theorem 33. By Corollary 29, r_{n+1} is odd, since |r_{n}| is even, and |r_{n+1}| = 2|r_{n}| = 2^{(n+1)−2}.

Remark 35. For an integer n > 2 + log_{2} N, r_{n} does not exist.

Now let’s count the number of 0’s, 1’s, and 2’s in each r_{n} for n ≥ 3. First, we simplify the notation.

\begin{matrix}n & 2^{n} & 0_{n} & 1_{n} & 2_{n} \\ 1 & 2 & 1 & 1 & 0 \\ 2 & 4 & 2 & 1 & 1 \\ 3 & 8 & 3 & 3 & 2 \\ 4 & 16 & 6 & 5 & 5 \\ 5 & 32 & 11 & 11 & 10 \end{matrix}

Table 1: 2^{n}, 0_{n}, 1_{n}, and 2_{n}

Definition 36. For any positive integer n and any digit a ∈ {0, 1, 2}, a_{n} is defined to be the number of a’s in the (n + 2)th repeating string r_{n+2} in g^{n+2}(1 0^{N}), i.e., a_{n} := |r_{n+2}|_{a}.

For example, |r_{n+2}| = 2^{n}, 0_{n}, 1_{n}, and 2_{n}, for n = 1, 2, …, 5, are shown in Table 1. Lemma 37. For any positive integer n,

(a) 0_{n} + 1_{n} + 2_{n} = 2^{n};

(b) 1_{n} is odd. Proof. Since |r_{n+2}| = 2^{n} by Corollary 34, (a) is obtained. Since r_{n+2} is odd by Corollary 34, |r_{n+2}|_{1} is odd. Hence, (b) is obtained. Theorem 38. For any positive integer n,

(a) 0_{n+1} = 0_{n} + 1_{n};

(b) 1_{n+1} = 0_{n} + 2_{n};

(c) 2_{n+1} = 1_{n} + 2_{n}. Proof. Since n ≥ 1, r_{n+2} is odd by Corollary 34, so r_{n+3} = g(r_{n+2}r_{n+2}) by Theorem 33. Then, by Corollary 28, |r_{n+3}|_{0} = |r_{n+2}|_{0} + |r_{n+2}|_{1}; |r_{n+3}|_{1} = |r_{n+2}|_{0} + |r_{n+2}|_{2}; |r_{n+3}|_{2} = |r_{n+2}|_{1} + |r_{n+2}|_{2}. By Definition 36, (a), (b), and (c) are obtained. Corollary 39. For any positive integer n,

(a) 2_{n} + 0_{n+1} = 2^{n};

(b) 1_{n} + 1_{n+1} = 2^{n};

(c) 0_{n} + 2_{n+1} = 2^{n}. Proof. Apply each relation in Theorem 38 to Lemma 37 (a). Corollary 40. For any positive integer n, (a) 0_{n} = 2_{n} + 1;

(b) 0_{n} = 1_{n}, if n is odd; 1_{n} + 1, if n is even;

(c) 2_{n} = 1_{n} − 1, if n is odd; 1_{n}, if n is even. Proof. Applying Theorem 38 (a) and (c),

0_{n} − 2_{n} = (0_{n−1} + 1_{n−1}) − (1_{n−1} + 2_{n−1}) = 0_{n−1} − 2_{n−1}.

Then 0_{n} − 2_{n} = 0_{n−1} − 2_{n−1} = ⋯ = 0_{1} − 2_{1} = 1, so (a) is obtained. Applying Theorem 38 (b) and (c); (a) and (b), we have

\begin{matrix}1_{n} − 2_{n} = (0_{n−1} + 2_{n−1}) − (1_{n−1} + 2_{n−1}) = 0_{n−1} − 1_{n−1}; \\ 0_{n} − 1_{n} = (0_{n−1} + 1_{n−1}) − (0_{n−1} + 2_{n−1}) = 1_{n−1} − 2_{n−1}. \end{matrix}

Combining them, 1_{n} − 2_{n} = 1_{n−2} − 2_{n−2} and 0_{n} − 1_{n} = 0_{n−2} − 1_{n−2}. Hence, if n is even, 1_{n} − 2_{n} = 1_{2} − 2_{2} = 0 and 0_{n} − 1_{n} = 0_{2} − 1_{2} = 1. If n is odd, 1_{n} − 2_{n} = 1_{1} − 2_{1} = 1 and 0_{n} − 1_{n} = 0_{1} − 1_{1} = 0. Therefore, (b) and (c) are obtained. Corollary 41. For any positive integer n,

(a) 0_{n} ≥ 1_{n} ≥ 2_{n};

(b) 0_{n} is odd, if and only if n is odd; 2_{n} is odd, if and only if n is even. Proof. By Corollary 40, (a) is obvious. By Lemma 37 (b) and Corollary 40 (b), 0_{n} = 1_{n} is odd, iff n is odd. By Corollary 40 (a), 2_{n} is even, iff 0_{n} is odd. Corollary 42. For any positive integer n,

0_{n+2} − 0_{n} = 2^{n} = 2_{n+2} − 2_{n}.  (11)

Proof. By Corollary 39 (a), 2_{n+1} = 2^{n+1} − 0_{n+2}, so Corollary 39 (c) becomes 0_{n} + (2^{n+1} − 0_{n+2}) = 2^{n}. Hence, 2^{n} = 0_{n+2} − 0_{n}. Then, by Corollary 40 (a), 2_{n+2} − 2_{n} = (0_{n+2} − 1) − (0_{n} − 1) = 2^{n}. Corollary 43. For any positive integer n,

(a) 0_{n} + 0_{n+1} = 2^{n} + 1;

(b) 2_{n} + 2_{n+1} = 2^{n} − 1. Proof. Applying Corollary 40 (a) to Corollary 39 (a) and (c), we have

(0_{n} − 1) + 0_{n+1} = 2^{n}; (2_{n} + 1) + 2_{n+1} = 2^{n}.

Finally, the explicit formulae for 0_{n}, 1_{n}, and 2_{n} are as follows:

Theorem 44. For any positive integer n, if n is odd,

0_{n} = \frac{2^{n} + 1}{3}; 1_{n} = \frac{2^{n} + 1}{3}; 2_{n} = \frac{2^{n} − 2}{3},

and if n is even,

0_{n} = \frac{2^{n} + 2}{3}; 1_{n} = \frac{2^{n} − 1}{3}; 2_{n} = \frac{2^{n} − 1}{3}.

Proof. By Corollary 40 (a) and (c),

0_{n} + 1_{n} + 2_{n} = \{ \begin{matrix}(2_{n} + 1) + (2_{n} + 1) + 2_{n} = 3 · 2_{n} + 2, & if n is odd; \\ (2_{n} + 1) + 2_{n} + 2_{n} = 3 · 2_{n} + 1, & if n is even . \end{matrix}

Then, by Lemma 37 (a), 2^{n} = 3 · 2_{n} + 2, if n is odd, and 2^{n} = 3 · 2_{n} + 1, if n is even. Solve for 2_{n}, first. Then apply Corollary 40 (a) and (c) to find 0_{n} and 1_{n}.

6 Jacobsthal numbers and their extension

The Jacobsthal numbers (J_{n})_{n≥0} (\underline{A001045}) are the numbers satisfying the following recurrence relation and initial conditions:

J_{n} = J_{n−1} + 2 · J_{n−2}  ;  J_{0} = 0, J_{1} = 1,  (12)

and the nth Jacobsthal number J_{n} is 0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341, for n = 0, 1, …, 10 [6]. Notice that J_{n} = 1_{n} for n = 1, 2, …, 10, which is true for any positive integer n.

Theorem 45. For any positive integer n, 1_{n} = J_{n}.

Proof. By Theorem 38 (b),

\begin{aligned}1_{n−1} + 2 · 1_{n−2} & = (0_{n−2} + 2_{n−2}) + 2 · 1_{n−2} \\ & = (0_{n−2} + 1_{n−2}) + (1_{n−2} + 2_{n−2}) = 0_{n−1} + 2_{n−1} = 1_{n}. \end{aligned}

Hence, 1_{n} satisfies the recurrence relation in (12). Since 1_{1} = 1 = J_{1} and 1_{2} = 1 = J_{2}, 1_{n} = J_{n} for any integer n ≥ 1.

We also find the sequences A_{1n} (\underline{A005578}) and A_{2n} (\underline{A000975}) such that A_{1n} = 0_{n} and A_{2,n−1} = 2_{n} for any positive integer n:

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

for any nonnegative integer n [6]. For n = 0, 1, …, 10, A_{1n} is 1, 1, 2, 3, 6, 11, 22, 43, 86, 171, 342, and A_{2n} is 0, 1, 2, 5, 10, 21, 42, 85, 170, 341. Notice that the index n of J_{n}, A_{1n}, and A_{2n} starts from 0, and the index n of 1_{n}, 0_{n}, and 2_{n} starts from 1. However, using the explicit formulae in Theorem 44, 0_{n}, 1_{n}, and 2_{n} are extended for any integer n.

Definition 46. For any integer n, 0_{n}, 1_{n}, and 2_{n} are defined as follows:

1_{n} := \frac{2^{n} − (−1)^{n}}{3} ;

if n is odd, 0_{n} := 1_{n} and 2_{n} := 1_{n} − 1, and if n is even, 0_{n} := 1_{n} + 1 and 2_{n} := 1_{n}. For example, 0_{n}, 1_{n}, and 2_{n}, for n = −5, −4, …, 4, 5, are shown in Table 2.

\begin{matrix}n & −5 & −4 & −3 & −2 & −1 & 0 & 1 & 2 & 3 & 4 & 5 \\ 0_{n} & \frac{11}{32} & \frac{11}{16} & \frac{3}{8} & \frac{3}{4} & \frac{1}{2} & 1 & 1 & 2 & 3 & 6 & 11 \\ 1_{n} & \frac{11}{32} & −\frac{5}{16} & \frac{3}{8} & −\frac{1}{4} & \frac{1}{2} & 0 & 1 & 1 & 3 & 5 & 11 \\ 2_{n} & −\frac{21}{32} & −\frac{5}{16} & −\frac{5}{8} & −\frac{1}{4} & −\frac{1}{2} & 0 & 0 & 1 & 2 & 5 & 10 \end{matrix}

Table 2: 0_{n}, 1_{n}, and 2_{n}, for n = 0, ±1, ±2, ±3, ±4, ±5

Notice that for any negative integer n, 0_{n} is always positive, 2_{n} is always negative, and 1_{n} alternates the sign. More over, every a_{n}, for any digit a ∈ {0, 1, 2} and any negative integer n, is a fraction, whose numerator in the simplest form is a Jacobsthal number. Theorem 47. For any positive integer n,

0_{−n} = \{ \begin{matrix}\frac{J_{n}}{2^{n}} , & for odd n; \\ \frac{J_{n+1}}{2^{n}} , & for even n; \end{matrix} 1_{−n} = (−1)^{n+1} \frac{J_{n}}{2^{n}}; 2_{−n} = \{ \begin{matrix}−\frac{J_{n+1}}{2^{n}} , & for odd n; \\ −\frac{J_{n}}{2^{n}} , & for even n. \end{matrix}

Proof. By Definition 46 and Theorem 44, for any positive integer n,

1_{−n} = \frac{2^{−n} − (−1)^{−n}}{3} = \frac{1 − (−2)^{n}}{3 · 2^{n}} = (−1)^{n+1} \frac{\frac{2^{n}−(−1)^{n}}{3}}{2^{n}} = (−1)^{n+1} \frac{1_{n}}{2^{n}} .

Since 1_{n} = J_{n} for any positive integer n, 1_{−n} is as desired. Then, by Definition 46, 0_{−n} and 2_{−n} are calculated as desired.

Since the explicit formulae in Theorem 44 hold for any integer n by Definition 46, almost all of the rules in Section 4 hold for any integer n. Lemma 48. For any integer n,

(a) 0_{n} + 1_{n} + 2_{n} = 2^{n};

(b) 0_{n+1} = 0_{n} + 1_{n}; 1_{n+1} = 0_{n} + 2_{n}; 2_{n+1} = 1_{n} + 2_{n};

(c) 2^{n} = 1_{n} + 1_{n+1} = 2_{n+2} − 2_{n} = 0_{n+2} − 0_{n} = 0_{n+1} + 0_{n} − 1 = 2_{n} + 2_{n+1} + 1;

(d) 0_{n} ≥ 1_{n} ≥ 2_{n}.

Hence, even if 0_{n}, 1_{n}, or 2_{n} is not an integer for each negative n, we may say that an extension for each J_{n}, A_{1n}, and A_{2n} is found.

Claim 49. J_{n} (\underline{A001045}), A_{1n} (\underline{A005578}) , and A_{2n} (\underline{A000975}) can be extended as follows: for any integer n,

J_{n} := 1_{n}; A_{1n} := 0_{n}; A_{2,n−1} := 2_{n}.

In particular, an extension of the Jacobsthal numbers is as follows:

Definition 50. For any positive integer n, J_{−n} is defined as follows:

J_{−n} := (−1)^{n+1} \frac{J_{n}}{2^{n}} .

Then the extended Jacobsthal numbers satisfy the same recurrence relation in (12): J_{n−1} + 2 · J_{n−2} = J_{n}, for any integer n. For example, the extended Jacobsthal numbers J_{n}, for n = −7, −6, …, 6, 7, are shown in Table 3.

\begin{matrix}n & −7 & −6 & −5 & −4 & −3 & −2 & −1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ J_{n} & \frac{43}{128} & −\frac{21}{64} & \frac{11}{32} & −\frac{5}{16} & \frac{3}{8} & −\frac{1}{4} & \frac{1}{2} & 0 & 1 & 1 & 3 & 5 & 11 & 21 & 43 \end{matrix}

Table 3: J_{n}, for n = ±1, ±2, …, ±7

7 More repeating strings

For an arbitrary large integer N, the ternary modified Collatz sequence starting with the ternary string 1 0^{N} has a repeating string, and J_{n} counts the number of occurrences of digit 1 in the shortest repeating string in the ternary string g^{n+2}(1 0^{N}). Now, we would like to find more repeating strings, which have J_{n} occurrences of digit 1. We consider the ternary modified Collatz sequence starting with a ternary string y 0^{N} for some ternary string y, which represents a multiple of 3^{N}.

Observation 51. For an arbitrary large integer N and any odd ternary string y, there exist ternary strings h and t such that the ternary string g^{3}(y 0^{N}) = h r^{⌊ \frac{N}{2} ⌋} t, where the string

r = \{ \begin{matrix}01, & if [y]_{3} ≡ 1 (mod 8); \\ 10, & if [y]_{3} ≡ 3 (mod 8); \\ 12, & if [y]_{3} ≡ 5 (mod 8); \\ 21, & if [y]_{3} ≡ 7 (mod 8). \end{matrix}

Proof. Since y is odd, the ternary string y 0^{N} is odd, so g(y 0^{N}) = (\frac{[y 0^{N} 1]_{3}}{2} )_{3} by (5), and

g (y 0^{N}) = (\frac{[y]_{3}−1}{2})_{3} z′ for some string z′ such that |z′| = |z| + 1 by Theorem 31. Since [y0^{N}1]_{3} = [([y]_{3} − 1)_{3}0^{N+1}]_{3} + [10^{N}1]_{3} and (\frac{[10^{N} 1]_{3}}{2} )_{3} = 01^{N}2 by Theorem 26, z′ = 1^{N}2. Hence,

g (y 0^{N}) = (\frac{[y]_{3} − 1}{2})_{3} 1^{N} 2 = (\frac{[y]_{3} − 1}{2})_{3} (11)^{⌊ \frac{N}{2} ⌋} 1^{(\frac{N}{2} −⌊ \frac{N}{2} ⌋)} 2.

If \frac{[y]_{3}−1}{2} is even, ⌊\frac{[y]_{3}−1}{2}⌋ = \frac{[y]_{3}−1}{4}, and g transforms each repeating string 11 in g(y 0^{N}) to 02 in g^{2}(y 0^{N}) by Theorem 26. Hence, by Theorem 31,

g^{2} (y 0^{N}) = (\frac{[y]_{3} − 1}{4})_{3} (02)^{⌊ \frac{N}{2} ⌋} t_{1},

for some string t_{1}. Then g transforms each repeating string 02 in g^{2}(y 0^{N}) to 01 in g^{3}(y 0^{N}) if \frac{[y]_{3}−1}{4} is even; 12 if odd, by Theorem 26. Hence, 01 and 12 repeat ⌊\frac{N}{2} ⌋ times in g^{3}(y 0^{N}), if [y]_{3} ≡ 1 (mod 8) and [y]_{3} ≡ 5 (mod 8), respectively.

If \frac{[y]_{3}−1}{2} is odd, ⌊\frac{[y]_{3}−1}{2}⌋ = \frac{[y]_{3}−3}{4}, and g transforms each repeating string 11 in g(y 0^{N}) to 20 in g^{2}(y 0^{N}) by Theorem 26. Hence, by Theorem 31,

g^{2} (y 0^{N}) = (\frac{[y]_{3} − 3}{4})_{3} (20)^{⌊ \frac{N}{2} ⌋} t_{2},

for some string t_{2}. Then g transforms each repeating string 20 in g^{2}(y 0^{N}) to 10 in g^{3}(y 0^{N}) if \frac{[y]_{3}−3}{4} is even; 21 if odd, by Theorem 26. Hence, 10 and 21 repeat ⌊\frac{N}{2} ⌋ times in g^{3}(y 0^{N}), if [y]_{3} ≡ 3 (mod 8) and [y]_{3} ≡ 7 (mod 8), respectively.

Notice that each r in g^{3}(y 0^{N}) is an odd ternary string of length 2. Hence, we use two copies of r in g^{3}(y_{1} 0^{N}) to find a repeating string in g^{4}(y 0^{N}), and continue to find a repeating string in g^{n+2}(y 0^{N}). Then each repeating string in g^{n+2}(y 0^{N}) has J_{n} or J_{n} ± 1 occurrences of digit 0, J_{n} occurrences of digit 1, and J_{n} or J_{n} ± 1 occurrences of digit 2. This works for any ternary string y, since we can reduce y to an odd string.

Theorem 52. Let N be an arbitrary large integer and y be a ternary string. Then, for any positive integer n, there exists a ternary string r_{n} such that |r_{n}| = 2^{n}, |r_{n}|_{1} = J_{n}, either |r_{n}|_{0} = 0_{n} and |r_{n}|_{2} = 2_{n} or |r_{n}|_{0} = 2_{n} and |r_{n}|_{2} = 0_{n}, and the ternary string

g^{n+i_{y}+2} (y 0^{N}) = h (r_{n})^{⌊ \frac{N}{2^{n}} ⌋} t

for some ternary strings h and t, where i_{y} is the nonnegative integer such that [y]_{3}/2^{i_{y}} is an odd integer.

Proof. If y is even, g^{i_{y}}(y 0^{N}) = g^{i_{y}}(y) 0^{N} by Theorem 21 and 26. Since g^{i_{y}}(y) = (\frac{[y]_{3}}{2^{iy}} )_{3} is

odd, g^{n+i_{y}}(y 0^{N}) = g^{n}(y_{1} 0^{N}) for some odd string y_{1}. Hence, without loss of generality, we assume y is an odd string and i_{y} = 0.

The proof is done by mathematical induction on n. The base case, when n = 1, is shown in Observation 51: the string of length 2 repeating ⌊\frac{N}{2} ⌋ times in the ternary g^{3}(y 0^{N}) are 10, 01, 12, and 21. Hence, |10|_{1} = |01|_{1} = |12|_{1} = |21|_{1} = 1 = J_{1}; |10|_{0} = |01|_{0} = 1 = 0_{1} and |10|_{2} = |01|_{2} = 0 = 2_{1}; |12|_{0} = |21|_{0} = 0 = 2_{1} and |12|_{2} = |21|_{2} = 1 = 0_{1}.

Assume r_{n} is the string of length 2^{n} repeating ⌊\frac{N}{2^{n}} ⌋ times in g^{n+2}(y 0^{N}) such that |r_{n}| = 2^{n}, |r_{n}|_{1} = J_{n}, either |r_{n}|_{0} = 0_{n} and |r_{n}|_{2} = 2_{n} or |r_{n}|_{0} = 2_{n} and |r_{n}|_{2} = 0_{n}. Since J_{n} = 1_{n} is odd for any positive n by Lemma 37 (b), r_{n} is odd. Then g(r_{n}r_{n}) repeats ⌊\frac{N}{2|r_{n}|}⌋ times in g^{n+3}(y 0^{N}) by Corollary 30, and |g(r_{n}r_{n})| = 2|r_{n}| = 2^{n+1} by Corollary 29 (b). Hence, g(r_{n}r_{n}) is the string of length 2^{n+1} repeating ⌊\frac{N}{2^{n+1}} ⌋ times in g^{n+3}(y 0^{N}), i.e., g(r_{n}r_{n}) = r_{n+1}. Then, by Corollary 28,

|r_{n+1}|_{0} = |r_{n}|_{0} + |r_{n}|_{1};  |r_{n+1}|_{1} = |r_{n}|_{0} + |r_{n}|_{2};  |r_{n+1}|_{2} = |r_{n}|_{1} + |r_{n}|_{2}.

If |r_{n}|_{0} = 0_{n} and |r_{n}|_{2} = 2_{n} are assumed in the induction hypothesis, by Theorem 38,

|r_{n+1}|_{0} = 0_{n} + 1_{n} = 0_{n+1}; |r_{n+1}|_{1} = 0_{n} + 2_{n} = 1_{n+1}; |r_{n+1}|_{2} = 1_{n} + 2_{n} = 2_{n+1}.

If |r_{n}|_{0} = 2_{n} and |r_{n}|_{2} = 0_{n} are assumed in the induction hypothesis, by Theorem 38,

|r_{n+1}|_{0} = 2_{n} + 1_{n} = 2_{n+1}; |r_{n+1}|_{1} = 2_{n} + 0_{n} = 1_{n+1}; |r_{n+1}|_{2} = 1_{n} + 0_{n} = 0_{n+1}.

Since 1_{n+1} = J_{n+1}, |r_{n+1}|_{1} = J_{n+1}.

8 Acknowledgments

I would like to thank Mr. Andrew Mosedale for proofreading, although all remaining errors are my own.

References

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

[2] J. C. Lagarias, The Ultimate Challenge: the 3x+1 Problem, American Mathematical Society, 2010.

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

[4] G. E. Révész, Introduction to Formal Languages, McGraw-Hill Book Company, 1983.

[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.

[7] E. W. Weisstein, MathWorld-A Wolfram Web Resource,

    http://mathworld.wolfram.com/Concatenation.html .

2010 Mathematics Subject Classification: Primary 11A67; Secondary 11B75. Keywords: Collatz sequence, Collatz problem, Jacobsthal number, ternary representation, 3x + 1 problem.

(Concerned with sequences \underline{A000975}, \underline{A001045}, and \underline{A005578}.)

Received December 23 2015; revised versions received January 7 2016; August 31 2016; September 2 2016. Published in Journal of Integer Sequences, September 7 2016.

Return to Journal of Integer Sequences home page.