\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{notation}[theorem]{Notation} \newtheorem{observation}[theorem]{Observation} \newtheorem{note}[theorem]{Note} \newtheorem{strategy}[theorem]{Strategy} \begin{center} \vskip 1cm{\LARGE\bf Ternary Modified Collatz Sequences \\ \vskip .03in And Jacobsthal Numbers \\ } \vskip 1cm \large Ji Young Choi\\ Department of Mathematics\\ Shippensburg University of Pennsylvania\\ 1871 Old Main Drive\\ Shippensburg, PA 17257 \\ USA\\ \href{mailto:jychoi@ship.edu}{\tt jychoi@ship.edu} \\ \end{center} \vskip .2 in \begin{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. \end{abstract} \section{Introduction} \begin{definition}\cite{Col} For any positive integer $m$, the \textit{Collatz function} $f$ on $m$ is defined as follows: \begin{equation}\label{E:collatz} f(m):= \begin{cases} \begin{array}{ll} \frac m 2, &\text{ if } m \text{ is even};\\ 3m+1, &\text{ if } m \text{ is odd}. \end{array} \end{cases} \end{equation} \end{definition} For any positive integer $m$, consider a sequence satisfying: $a_0=m$ and $a_n=f(a_{n-1})$ for $n>1$. Collatz \cite{Col} 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 \cite{Lag} that for every positive integer $m< 5.7646\cdot 10^{18}$ there exists $n > 0$ such that $f^n(m)=1$. If there is an integer $m$ such that $f^n(m)\neq 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$. \begin{definition} \cite{Riho} \label{D:modi} For any positive integer $m$, the \textit{modified Collatz function} $g$ on $m$ is defined as follows: \begin{equation}\label{E:modifiedcollatz} g(m):=\begin{cases}\begin{array}{ll} f(m)=\frac m 2, &\text{ if } m \text{ is even};\\ f^2(m)=\frac {3 m+1} 2, &\text{ if } m \text{ is odd}. \end{array} \end{cases} \end{equation} \end{definition} 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\cdots0$ 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 \ref{S:notation} clarifies notation for this paper. Sections \ref{S:ternary} and \ref{S:modifed} show how to apply the Collatz function and the modified Collatz function to the ternary representation of integers. In Section \ref{S:final}, a repeating string of digits in the ternary modified Collatz sequence starting with the string $100\cdots 0$ is studied, and the number of occurrences of each digit in each repeating string is counted. Section \ref{S:jacobsthal} shows that the number of $1$ digits counted in Section \ref{S:final} is identified as a Jacobsthal number, and suggests an extension of Jacobsthal numbers. Section \ref{S:additional} generalizes Section \ref{S:final}. \section{Notation} \label{S: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 \textit{empty string}, which contains no digits, denoted by $\epsilon$ \cite{Sha}. The notation for the number of digits in a string is as follows: \begin{definition} \cite{Sha} 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$. \end{definition} \begin{lemma}\label{L:sharp} For any string $x$ in $\{0, 1, 2\}^*$, $$ |x|=|x|_0+|x|_1+|x|_2. $$ \end{lemma} 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 \cite{Sha, Wei}: \begin{definition} For any strings $x$ and $y$ and any positive integer $n$, the \textit{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_1a_2\cdots a_{|x|}$ and $y=b_1b_2\cdots b_{|y|}$ for some $a_i, b_i \in \{0, 1, 2\}$, $$ xy=a_1a_2\cdots a_{|x|} b_1b_2\cdots b_{|y|} \text{, and } x^n=xx\cdots x \text{ ($n$ times)}. $$ For a convention, $x^{ 0}$ is defined to be $\epsilon$. \end{definition} Then concatenation is associative, and the length of the concatenation of two strings is the sum of each string length. \begin{lemma}\label{L:associative} For any ternary strings $x$, $y$, and $z$, $x y z=(x y) z= x (y z)$. \end{lemma} \begin{lemma} For any strings $x$ and $y$ and a nonnegative integer $n$, $|xy|=|x|+|y|$ and $|x^n|=n|x|$. \end{lemma} For example, $102\text{ }00=10200$, $(10)^{ 3} =101010$, and $1=1\text{ } (10)^{ 0}$. $|102\text{ }00|=|102|+|00|=3+2=5$ and $|(10)^{ 3}|=3|10|=3\cdot 2 =5$. For a finite string $x$, a substring $y$ is called a \textit{head} of $x$ if there exists a string $z$ such that $x=yz$, and a substring $z$ is called a \textit{tail} of $x$ if there exists a string $y$ such that $x=yz$ \cite{Rev}. 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 \textit{ternary string} throughout this paper. When we have to distinguish an integer and its ternary string, we use the following notation. \begin{notation} For any integer $m$ with base 3-representation $x$, we write $m=[x]_3$ or $(m)_3=x$. \end{notation} 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$. \begin{notation} For a ternary string $x$, the \textit{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$. \end{notation} Then the ternary string $g(x)$ is identified as follows: \begin{lemma}\label{L:modiCol} For a ternary string $x$, $$ g(x)= \begin{cases} \begin{array}{ll} f(x), &\text{ if } x \text{ is even};\\ f(f(x)), &\text{ if } x \text{ is odd}. \end{array} \end{cases} $$ \end{lemma} 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. \begin{definition} For any ternary string $x$, $x$ is said to be \textit{odd} if $[x]_3$ is odd, and $x$ is said to be \textit{even} if $[x]_3$ is even. \end{definition} \section{The Collatz function on ternary strings}\label{S:ternary} Every ternary string represents a sum of powers of 3. For example, $[102211]_3=1\cdot 3^5+2\cdot 3^3+2\cdot 3^2+1\cdot 3^1+1\cdot 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. \begin{observation} \label{O:odd} For a ternary string $x$, $|x|_1$ is odd, if and only if $x$ is odd. \end{observation} For an odd ternary string $x$, the ternary string $f(x)=\left(3[x]_3+1\right)_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. \begin{lemma}\label{L:Collatzodd} For any odd ternary string $x$, $ f(x)=x{} 1. $ \end{lemma} \begin{proof} $3 [x]_3+1 = [10]_3 [x]_3 +1=[x{} 0]_3 +1=[x{} 1]_3$. \end{proof} For example, $f(11102)=11102\text{ }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$. \begin{lemma}\label{L:Collatzeven} For a ternary string $x=a_1{} a_2{} \cdots {} a_{|x|}$, if each $a_i$ is either 0 or 2, $$ f(x)=a'_1{} a'_2{} \cdots{} a'_{|x|}\text{, where } a'_i= \left\{ \begin{array}{ll} 0, & \hbox{if $a_i=0$;}\\ 1, & \hbox{if $a_i=2$.} \end{array} \right. $$ \end{lemma} \begin{proof} Since $|x|_1=0$, $x$ is even, so $f(x)=\left(\frac {[x]_3} 2\right)_3$. Since $|a_1{} a_2{} \cdots {} a_{i-1}|_1=0$, $a_1{} a_2{} \cdots {} a_{i-1}$ is even for any $i=1, \ldots, |x|$. Hence, when $[a_1{} a_2{} \cdots {} a_{i-1}]_3$ is divided by 2, the remainder is 0. Hence, the $i$th digit $a'_i$ in $f(x)$ is $\frac{a_i}2$, which is 0 if $a_i=0$; 1 if $a_i=2$. \end{proof} Secondly, consider another even ternary string $1{} x{} 1$, where the string $x$ does not contain any digit 1. \begin{lemma}\label{L:collatzeven1} For a ternary string $x= a_1{} a_2{} \cdots {} a_{|x|}$, if each $a_i$ is either 0 or 2, $$ f(1{} x {} 1)=0{} a'_1{} a'_2{} \cdots{} a'_{|x|} {} 2 \text{, where } a'_i= \left\{ \begin{array}{ll} 1, & \hbox{if $a_i=0$;}\\ 2, & \hbox{if $a_i=2$.} \end{array} \right. $$ \end{lemma} \begin{proof} Since $|1{} x {} 1|_1=2$ is even, $1{} x{} 1$ is even, so $f(1{} x{} 1)=\left(\frac{[1{} x{} 1]_3}2\right)_3$. The head digit in $\left(\frac{[1{} x{} 1]_3}2\right)_3$ is 0, because the head digit 1 in $1{} x {} 1$ is less than the divisor 2. Since $|1{} a_1{} a_2{} \cdots {} a_{i-1}|_1=1$ is odd, $1{} a_1{} a_2{} \cdots {} a_{i-1}$ is odd for any $i=1, \ldots, |x|$, so the remainder when $[1{} a_1{} a_2{} \cdots {} 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 $[1{} a_i]_3$ is divided by 2, i.e. $a'_i=\lfloor \frac {[1{} a_i]_3}2\rfloor$, which is 1 if $a_i=0$; 2 if $a_i=2$. Similarly, since $1{} x$ is odd, the remainder when $[1{} x]_3$ is divided by 2 is 1. Hence, the last digit in $f(1x1)$ is $\frac {[11]_3}2=2$. \end{proof} \begin{note}\label{N:length1} In this paper, for any string $x$ with the head digit 1, when $f$ transforms the head digit 1 to digit 0, we \textbf{keep the new head digit 0}, so that $ |x|=|f(x)|. $ \end{note} For example, $f(12200201)=02211212$, so $|f(12200201)|=|02211212|$. Now consider a ternary string $y{} z$, where $y$ and $z$ are even ternary strings. \begin{lemma}\label{L:collatzevenodd} For any even ternary strings $y$ and $z$, \begin{equation}\label{E:yz} f(y{} z)=f(y){} f(z). \end{equation} \end{lemma} \begin{proof} Since $y$ and $z$ are even, $|y|_1$ and $|z|_1$ are even, and $f(y)=\left(\frac{[y]_3}2\right)_3$ and $f(z)=\left(\frac{[z]_3}2\right)_3$. Since $|y{} z|_1=|y|_1+|z|_1$ is even, $y{} z$ is even, so $f(y{} z) = \left( \frac {[y{} z]_3} 2\right)_3$. Since $[y{} z]_3=[ y0^{|z|}]_3 +[z]_3$, $$ \frac{[y{} z]_3}2=\frac{[y 0^{|z|}]_3}2+\frac {[z]_3} 2=\left[\left(\frac {[y]_3} 2\right)_3 0^{|z|}\right]_3+\frac {[z]_3} 2. $$ Since $|z|=|f(z)|$ and $\frac{[z]_3}2 =[f(z)]_3$, $$ f(yz)=\left( \left[f(y) 0^{|f(z)|}\right]_3+[f(z)]_3\right)_3 =\left( \left[f(y)f(z)\right]_3\right)_3=f(y)f(z). $$ \end{proof} Now consider an arbitrary even ternary string $x$. By Observation \ref{O:odd}, $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 \ref{L:Collatzeven} or Lemma \ref{L:collatzeven1}. That is, $x=y_1{} y_2{} \cdots {} y_k$, for some integer $k$, such that $y_i=$ either $x_i$ or $1{} x_i{} 1$, where $|x_i|_1=0$ for all $i$. For example, $x=10210022112012001=1021\text{ } 0022\text{ } 11\text{ } 20\text{ } 12001$. Applying Lemma \ref{L:Collatzeven} and \ref{L:collatzeven1}, we find each ternary string $f(y_i)$ for all $i$. Then we use the following theorem to put them together for $f(x)$. \begin{theorem}\label{L:Collatzeven0} For any even ternary string $y_i$ for $i=1, 2, \ldots, k$, \begin{equation}\label{E:yy} f(y_1{} y_2{} \cdots {} y_k)=f(y_1){} f(y_2){} \cdots {} f(y_k). \end{equation} \end{theorem} \begin{proof} By Lemma \ref{L:associative}, $y_1{} y_2{} \cdots {} y_k=y_1{} \left(y_2{} \cdots {} y_k\right)$. Then, by Lemma \ref{L:collatzevenodd}, $f(y_1{} y_2{} \cdots {} y_k)=f(y_1){} f(y_2{} \cdots {} y_k)$. Continuing this, (\ref{E:yy}) is obtained. \end{proof} \begin{example} The Collatz function $f$ transforms the ternary string 10210022112012001 to the following ternary string: $$ \begin{array}{ll} f(10210022112012001)&=f(1021\text{ } 0022\text{ }11\text{ }20\text{ } 12001)\\ &= f(1021) {} f(0022) {} f(11) {} f(20){} f(12001)\\ &=0122\text{ }0011\text{ }02\text{ }10\text{ }02112= 01220011021002112. \end{array} $$ \end{example} \section{The modified Collatz function on ternary strings} \label{S:modifed} We have found how to transform a ternary string $x$ into the ternary string $f(x)$ in Section \ref{S:ternary}. We use the same method to find the ternary string $g(x)$ for any ternary string $x$, since \begin{equation}\label{E:Def} g(x)=\begin{cases} f(x)=\left(\frac{[x]_3}{2}\right)_3, & \mbox{if $x$ is even;} \\ f(x1)=\left(\frac{[x1]_3}{2}\right)_3, & \mbox{if $x$ is odd}, \end{cases} \end{equation} by Lemma \ref{L:modiCol} and Lemma \ref{L:Collatzodd}. \begin{lemma}\label{L:modifiedCo0} For any ternary strings $y$ and $z$, if $y$ is even, \begin{equation}\label{E:modiyz} g(y{} z)=g(y){} g(z). \end{equation} \end{lemma} \begin{proof} Since $y$ is even, $|y|_1$ is even. Hence, $|y{} z|_1=|y|_1+|z|_1$ is even, iff $|z|_1$ is even. Therefore, if $z$ is even, $y{} z$ is even, so $g(y{} z)=f(y{} z)$. By Lemma \ref{L:collatzevenodd}, (\ref{E:modiyz}) is obtained. If $z$ is odd, $y{} z$ is odd and $z{} 1$ is even. By (\ref{E:Def}) and Lemma \ref{L:collatzevenodd}, $$ g(yz)=f(y{} z{} 1)=f(y){} f(z{} 1)=g(y) g(z). $$ \end{proof} \begin{theorem}\label{T:modified} Let $y_i$ and $z$ be ternary strings for $i=1, 2, \ldots k$. If every $y_i$ is even, \begin{equation}\label{E:y123} g(y_1{} y_2{} \cdots {} y_k{} z)=g(y_1){} g(y_2){} \cdots {} g(y_k){} g(z). \end{equation} \end{theorem} \begin{proof} Since every $y_i$ is even, $y_1{} y_2{} \cdots {} y_k$ is even, so $g(y_i)=f(y_i)$ for each $i$ and $g(y_1{} y_2{} \cdots {} y_k)$ $=f(y_1{} y_2{} \cdots {} y_k)$. By Lemma \ref{L:modifiedCo0}, $ g(y_1{} y_2{} \cdots {} y_k{} z)=g(y_1{} y_2{} \cdots {} y_k){} g(z)=f(y_1{} y_2{} \cdots {} y_k){} g(z). $ Applying Theorem \ref{L:Collatzeven0}, (\ref{E:y123}) is obtained. \end{proof} \begin{lemma}\label{L:modi} For a ternary string $x=a_1{} a_2{} \cdots {} a_{|x|}$, if each $a_i$ is either 0 or 2, \begin{itemize} \item[\normalfont{(a)}] $g(x)=a'_1{} a'_2{} \cdots {} a'_{|x|}\text{, where } a'_i= 0, \text{ if } a_i=0\text{; } a'_i=1, \text{ if } a_i=2$; \item[\normalfont{(b)}] $g(1{} x{} 1)=0{} a'_1{} a'_2{} \cdots {} a'_{|x|}{} 2\text{, where } a'_i= 1, \text{ if } a_i=0\text{; } a'_i=2, \text{ if } a_i=2$; \item[\normalfont{(c)}] $g(1{} x)=0{} a'_1{} a'_2{} \cdots {} a'_{|x|}{} 2\text{, where } a'_i= 1, \text{ if } a_i=0\text{; } a'_i=2, \text{ if } a_i=2$. \end{itemize} \end{lemma} \begin{proof}Since $x$ and $1{} x{} 1$ are even, $g(x)=f(x)$ and $g(1{} x {} 1)=f(1{} x{} 1)$. Hence, (a) and (b) are obtained by Lemmas \ref{L:Collatzeven} and \ref{L:collatzeven1}. Since $1{} x$ is odd, $g(1{} x)=f(1{} x{} 1)$ by (\ref{E:Def}). Since $1{} x{} 1$ is even, $f(1{} x{} 1)=g(1{} x{} 1)$, so we apply (b) to get (c). \end{proof} \begin{strategy}\label{Strategy} For any ternary string $x$, the modified Collatz function $g$ transforms $x$ into the ternary string $g(x)$ as follows: \begin{enumerate} \item break $x$: $x=y_1{} y_2{} \cdots {} y_k y_{k+1}$, for some integer $k$, such that $y_i=$ either $x_i$ or $1{} x_i{} 1$ for all $i\leq k$, and $y_{k+1}=x_{k+1}$, $1{} x_{k+1}{} 1$, or $1{} x_{k+1}$, where $|x_i|_1=0$ for all $i=1, 2, \ldots, k, k+1$; \item find $g(y_i)$: apply Lemma \ref{L:modi} to find each ternary string $g(y_i)$; \item concatenate all $g(y_i)$'s: apply Theorem \ref{T:modified} to find the ternary string $g(x)$. \end{enumerate} \end{strategy} \begin{example} The modified Collatz function transforms the ternary string 120100211102 to the following ternary string: $$ \begin{array}{ll} g(120100211102)&=g(1201\text{ } 002\text{ }11\text{ }102)\\ &=g(1201){} g(002){} g(11){} g(102)\\ &=0212\text{ } 001\text{ } 02\text{ } 0122=0212001020122 \end{array} $$ \end{example} In this paper, for any ternary string $x$ with the head digit 1, when $g$ transforms the head digit 1 to digit 0, we \textbf{keep the new head digit 0} in $g(x)$, so the length of the ternary string $g(x)$ can be calculated as follows: \begin{note}\label{N:length} For any ternary strings $x$, $|g(x)|=|x|$, if $x$ is even; and $|x|+1$, if odd. \end{note} In order to apply the modified Collatz function $g$ to a lengthy ternary string in Section \ref{S:final} and \ref{S:additional}, we need to study more on $g$. \begin{theorem}\label{T:001122} For any ternary string $x$, let $a_i\in \{0, 1, 2\}$ such that $x=a_1{} a_2{} \cdots {} a_{|x|}$. Then $$ g(x)= \begin{cases} \begin{array}{ll} a'_1{} a'_2\cdots {} a'_{|x|}, &\text{ if } x \text{ is even};\\ a'_1{} a'_2\cdots {} a'_{|x|} 2, &\text{ if } x \text{ is odd}, \end{array} \end{cases} $$ where $$ \begin{array}{ll} a'_i= \left\{ \begin{array}{ll} 0, & \hbox{\text{ if } $a_i=0$;} \phantom{mmm}\\ 0, & \hbox{\text{ if } $a_i=1$;} \\ 1, & \hbox{\text{ if } $a_i=2$}, \end{array} \right. & a'_i= \left\{ \begin{array}{ll} 1, & \hbox{\text{ if } $a_i=0$;} \\ 2, & \hbox{\text{ if } $a_i=1$;} \\ 2, & \hbox{\text{ if } $a_i=2$}, \end{array} \right.\\ \text{if } |a_1{} a_2 {} \cdots {} a_{i-1}|_1 \text{ is even;}\phantom{mmmmmmmm} & \text{if } |a_1{} a_2 {} \cdots {} a_{i-1}|_1 \text{ is odd.} \\ \end{array} $$ \end{theorem} \begin{proof} By(\ref{E:Def}), $g$ divides either $[x]_3$ or $[x1]_3$ by 2. Since $x=a_1\cdots a_{i-1}a_i\cdots a_{|x|}$ and $x1=a_1\cdots a_{i-1}a_i\cdots a_{|x|}1$, the $i$th digit in $g(x)$ is $$ a'_i= \begin{cases} \lfloor\frac{a_i}{2}\rfloor, & \mbox{if the remainder is 0 when $[a_1{} \cdots {} a_{i-1}]_3$ is divided by 2;} \\ \lfloor\frac{1a_i}{2}\rfloor, & \mbox{if the remainder is 1 when $[a_1 \cdots {} a_{i-1}]_3$ is divided by 2,} \end{cases} $$ for all $i\leq |x|$. Applying Observation \ref{O:odd} and calculating $\lfloor\frac{a_i}{2}\rfloor$ and $\lfloor\frac{1a_i}{2}\rfloor$, $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)=\left(\frac{[x1]_3}2\right)_3$ is $\frac{[11]_3}2=2$. \end{proof} \begin{theorem}\label{T:012} For any odd ternary string $x$, let $a_i\in \{0, 1, 2\}$ such that $x=a_1{} a_2{} \cdots {} a_{|x|}$. Then the ternary string $g(x{} x)=a'_1{}a'_2 \cdots {} a'_{|x|}a'_{|x|+1}\cdots a'_{2|x|}$ such that \begin{equation}\label{E:double digit} \{a'_i, a'_{|x|+i}\}= \left\{ \begin{array}{ll} \{0,1\}, & \hbox{\text{if } $a_i=0$;} \\ \{0,2\}, & \hbox{\text{if } $a_i=1$;} \\ \{1,2\}, & \hbox{\text{if } $a_i=2$.} \end{array} \right. \end{equation} \end{theorem} \begin{proof} Let $a_{|x|+i}$ be the $(|x|+i)$th digit in the string $x{} x$ for any $i\leq |x|$. Then $a_{|x|+i}=a_i$, so $ |a_1{}a_2{} \cdots{} a_{|x|+i-1}|_1=|a_1{}a_2{} \cdots {} a_{|x|}|_1+|a_{|x|+1}{} a_{|x|+2}{} \cdots a_{|x|+i-1}|_1=|x|_1+|a_1{}a_2{} \cdots{} a_{i-1}|_1. $ Since $x$ is odd, $|x|_1$ is odd. Hence, $|a_1{} a_2{} \cdots{} a_{i-1}|_1$ is odd, iff $| a_1{} a_2{} \cdots{} 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 \ref{T:001122}. \end{proof} \begin{corollary}\label{C:sharp} For an odd ternary string $x$, the ternary string $g(x{}x)$ satisfies the following: \begin{itemize} \item[\normalfont{(a)}] $|g(x{} x)|_0=|x|_0+|x|_1$; \item[\normalfont{(b)}] $|g(x{} x)|_1=|x|_0+|x|_2$; \item[\normalfont{(c)}] $|g(x{} x)|_2=|x|_1+|x|_2$. \end{itemize} \end{corollary} \begin{proof} By Theorem \ref{T:012}, $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 \geq \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. \end{proof} \begin{corollary}\label{C:012} For any odd ternary strings $x$, \begin{itemize} \item[\normalfont{(a)}] $g(x{} x)$ is odd, if and only if $|x|$ is even; \item[\normalfont{(b)}] $|g(x{} x)|=2|x|$. \end{itemize} \end{corollary} \begin{proof} By Corollary \ref{C:sharp} (b), $|g(x{} x)|_1=|x|_0+|x|_2=|x|-|x|_1$. Since $x$ is odd, $|x|_1$ is odd by Observation \ref{O:odd}. Hence, (a) is obtained. Since $|x{} x|_1=2|x|_1$ is even, $x{} x$ is even. By Note \ref{N:length}, $|g(x{} x)|=|x{} x|=2|x|$. \end{proof} \begin{corollary}\label{C:xx} For any ternary strings $x$ and $z$ and for any positive integer $k$, \begin{equation}\label{E:xx} g(x^{ k} {} z)= \left(g(x{} x)\right)^{ \lfloor \frac k 2\rfloor}{} g(z_1), \end{equation} where $z_1=x{} z$, if $k$ is odd, and $z_1=z$, if $k$ is even. \end{corollary} \begin{proof} Since $k=2\cdot \lfloor \frac k 2\rfloor +p$, where $p=1$ for odd $k$; 0 for even $k$, $x^{ k}=(x{} x)^{\lfloor \frac k 2\rfloor}{} x^{p}$. Since $x{} x$ is even, apply Theorem \ref{T:modified} to provide (\ref{E:xx}). \end{proof} \begin{theorem}\label{T:yz} For any ternary strings $y$ and $z$, \begin{equation}\label{E:yz2} g(y{} z)=\left(\left\lfloor \frac {[y]_3} 2\right\rfloor \right)_3{} z', \end{equation} for some ternary string $z'$ such that $|z'|= |z|$, if $y{} z$ is even; $|z|+1$, if odd. \end{theorem} \begin{proof} If $y$ is even, the ternary string $g(y{} z)=g(y){} g(z)$ by Lemma \ref{L:modifiedCo0}, and $yz$ is even, iff $z$ is even. Since $g(y)=\left(\frac {[y]_3} 2\right)_3$, let $z'=g(z)$. Then $|z'|=|z|$ if $y{} z$ is even; $|z|+1$ if odd. Assume that $y$ is odd. If $z$ is odd, $y{} z$ is even. Then $[y]_3-1$ and $1z$ are even, and $[yz]_3=[([y]_3-1)_30^{|z|}]_3+[1z]_3$. Since $|1z|=|z|+1$ and $\left(\frac{[1z]_3}{2}\right)_3=0z'$ for some ternary string $z'$ such that $|z'|=|z|$, $$ g(yz)=\left(\frac{[yz]_3}{2}\right)_3=\left(\frac{[([y]_3-1)_30^{|z'|}]_3}{2}+[0z']_3\right)_3=\left(\frac{[y]_3-1}{2}\right)_3 z'. $$ If $z$ is even, $y{} z$ is odd. Then $[y]_3-1$ and $1z1$ are even and $[yz1]_3=[([y]_3-1)_30^{|z1|}]_3+[1z1]_3$. Since $|1z1|=|z|+2$ and $\left(\frac{[1z1]_3}{2}\right)_3=0z'2$ for some ternary string $z'$ such that $|z'|=|z|$ by Theorem \ref{T:001122}, $$ g(yz)=\left(\frac{[yz1]_3}{2}\right)_3=\left(\frac{[([y]_3-1)_30^{|z'|+1}]_3}{2}+[0z'2]_3\right)_3=\left(\frac{[y]_3-1}{2}\right)_3 z'2. $$ Since $\frac{[y]_3-1}{2}=\lfloor\frac{[y]_3}{2}\rfloor$, (\ref{E:yz2}) is obtained. \end{proof} \section{Ternary modified Collatz sequences with a repeating string}\label{S:final} 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\text{ } 0^{ N}$. Consider the ternary representation of the modified Collatz sequence starting with the string $1 \text{ } 0^{ N}$. For example, the first few numbers in the ternary modified Collatz sequence starting with $1\text{ } 0^{ 50}$ are as follows: $$ \begin{array}{rl} 1\text{ } 0^{ 50}&=100000000000000000000000000000000000000000000000000;\\ g^1(1\text{ } 0^{ 50})&=0111111111111111111111111111111111111111111111111112;\\ g^2(1\text{ } 0^{ 50})&=0020202020202020202020202020202020202020202020202021;\\ g^3(1\text{ } 0^{ 50})&=00101010101010101010101010101010101010101010101010102;\\ g^4(1\text{ } 0^{ 50})&=000120012001200120012001200120012001200120012001200122. \end{array} $$ Notice that there is a substring repeating in the ternary string $g^n(1\text{ } 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 \text{ }0^{ 50})$. \begin{definition}\label{D:repeating string} For an arbitrary large integer $N$ and a positive integer $n$, the \textit{$n$th repeating string} $r_n$ of the ternary string $g^n(1\text{ } 0^{ N})$ is defined to be the shortest string repeating $\left\lfloor\frac{N}{|r_n|}\right\rfloor$ times in $g^n(1 \text{ }0^{ N})$ such that $$ g^n(1 \text{ }0^{ N})=0\text{ } (r_n) ^{ \left\lfloor\frac{N}{|r_n|}\right\rfloor} \text{ } t, $$ for some ternary string $t$. \end{definition} For $n=1, 2, \ldots, 7$, the $n$th repeating string $r_n$ in the ternary string $g^n(1\text{ } 0^{ N})$, for an arbitrary large integer $N$, is as follows: $$ \begin{array}{l} r_1=1;\\ r_2=02;\\ r_3=01;\\ r_4=0012;\\ r_5=00021121;\\ r_6=0001021011122022;\\ r_7=00001220020221221112010120211011. \end{array} $$ \begin{theorem}\label{T:rn} For any positive integer $n$, $r_{n+1}=g(r_n{} r_n)$, if $r_n$ is odd. \end{theorem} \begin{proof} By Definition \ref{D:repeating string}, $g^n(1\text{ } 0^{ N})=0\text{ } (r_n) ^{ \left\lfloor\frac{N}{|r_n|}\right\rfloor} \text{ } t$ for some ternary string $t$. Then, by Theorem \ref{T:modified} and Corollary \ref{C:xx}, $$ g^{n+1}\left(1\text{ } 0 ^{ N}\right)=g\left(0\text{ } (r_n) ^{ \left\lfloor\frac{N}{|r_n|}\right\rfloor}\text{ } t\right)=g(0)\text{ } \left(g(r_n{} r_n)\right)^{ \left\lfloor\lfloor\frac{N}{|r_n|}\rfloor/2\right\rfloor} \text{ } g(t_1), $$ where $t_1=r_n{} t$, if $\left\lfloor\frac{N}{|r_n|}\right\rfloor$ is odd; $t$, if even. Since $\left\lfloor\lfloor\frac{N}{|r_n|}\rfloor/2\right\rfloor=\left\lfloor\frac{N}{2|r_n|}\right\rfloor$, the ternary string $g(r_n{} r_n)$ is a string repeating $\left\lfloor\frac{N}{2|r_n|}\right\rfloor$ times in the ternary string $g^{n+1}(1\text{ } 0^{ N})$. Since $r_n$ is the shortest string repeating in $g^n(1\text{ } 0^{ N})$, $|r_{n+1}|$ should be a multiple of $|r_n|$. Since $r_n$ is odd, $g(r_n{} r_n)\neq g(r_n){} g(r_n)$ by Theorem \ref{T:012}. Hence, $|r_{n+1}|\neq|r_n|$. Since $|g(r_n{} r_n)|=2|r_n|$ by Corollary \ref{C:012} (b), the ternary string $g(r_n{} r_n)$ is the shortest string repeating $\left\lfloor\frac{N}{|g(r_n{} r_n)|}\right\rfloor$ times in the ternary string $g^{n+1}(1\text{ } 0^{ N})$. \end{proof} \begin{corollary}\label{T:reapeating string} For every integer $n\geq 3$, $r_n$ is odd and $|r_n|=2^{n-2}$. \end{corollary} \begin{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 \ref{T:rn}. By Corollary \ref{C:012}, $r_{n+1}$ is odd, since $|r_n|$ is even, and $|r_{n+1}|=2|r_n|=2^{(n+1)-2}$. \end{proof} \begin{remark} For an integer $n> 2+\log_2 N$, $r_n$ does not exist. \end{remark} Now let's count the number of 0's, 1's, and 2's in each $r_n$ for $n\geq 3$. First, we simplify the notation. \begin{definition} \label{D:an} For any positive integer $n$ and any digit $a \in\{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\text { }0^N)$, i.e., $ a_n:=|r_{n+2}|_a. $ \end{definition} For example, $|r_{n+2}|=2^n$, $0_n$, $1_n$, and $2_n$, for $n=1, 2, \ldots, 5$, are shown in Table \ref{Table1}. \begin{table}[ht] \begin{center} \begin{tabular}{|r|llll|} \hline $n$ & $2^n$&$0_n$ & $1_n$ & $2_n$\\ \hline 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\\ \hline \end{tabular} \end{center} \caption{$2^n$, $0_n$, $1_n$, and $2_n$} \label{Table1} \end{table} \begin{lemma} \label{L:odd} For any positive integer $n$, \begin{itemize} \item[\normalfont{(a)}] $0_n+1_n+2_n=2^n$; \item[\normalfont{(b)}] $1_n$ is odd. \end{itemize} \end{lemma} \begin{proof} Since $|r_{n+2}|=2^n$ by Corollary \ref{T:reapeating string}, (a) is obtained. Since $r_{n+2}$ is odd by Corollary \ref{T:reapeating string}, $|r_{n+2}|_1$ is odd. Hence, (b) is obtained. \end{proof} \begin{theorem}\label{T:main relations} For any positive integer $n$, \begin{itemize} \item[\normalfont{(a)}] $0_{n+1}=0_n+1_n$; \item[\normalfont{(b)}] $1_{n+1}=0_n+2_n$; \item[\normalfont{(c)}] $2_{n+1}=1_n+2_n$. \end{itemize} \end{theorem} \begin{proof} Since $n\geq 1$, $r_{n+2}$ is odd by Corollary \ref{T:reapeating string}, so $r_{n+3}=g(r_{n+2}{} r_{n+2})$ by Theorem \ref{T:rn}. Then, by Corollary \ref{C:sharp}, $ |r_{n+3}|_0=|r_{n+2}|_0+|r_{n+2}|_1;\text{ } |r_{n+3}|_1=|r_{n+2}|_0+|r_{n+2}|_2;\text{ } |r_{n+3}|_2=|r_{n+2}|_1+|r_{n+2}|_2. $ By Definition \ref{D:an}, (a), (b), and (c) are obtained. \end{proof} \begin{corollary} \label{C:012sum} For any positive integer $n$, \begin{itemize} \item[\normalfont{(a)}] $2_n+0_{n+1}=2^n$; \item[\normalfont{(b)}] $1_n+1_{n+1}=2^{n}$; \item[\normalfont{(c)}] $0_n+2_{n+1}=2^n$. \end{itemize} \end{corollary} \begin{proof} Apply each relation in Theorem \ref{T:main relations} to Lemma \ref{L:odd} (a). \end{proof} \begin{corollary}\label{C:relations012} For any positive integer $n$, \begin{itemize} \item[\normalfont{(a)}] $0_n=2_n+1$; \item[\normalfont{(b)}] $0_n=1_n$, if $n$ is odd; $1_n+1$, if $n$ is even; \item[\normalfont{(c)}] $2_n=1_n-1$, if $n$ is odd; $1_n$, if $n$ is even. \end{itemize} \end{corollary} \begin{proof} Applying Theorem \ref{T:main relations} (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}=\cdots=0_1-2_1=1$, so (a) is obtained. Applying Theorem \ref{T:main relations} (b) and (c); (a) and (b), we have $$ \begin{array}{l} 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{array} $$ 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. \end{proof} \begin{corollary} For any positive integer $n$, \begin{itemize} \item[\normalfont{(a)}] $0_n\geq 1_n\geq 2_n$; \item[\normalfont{(b)}] $0_n$ is odd, if and only if $n$ is odd; $2_n$ is odd, if and only if $n$ is even. \end{itemize} \end{corollary} \begin{proof} By Corollary \ref{C:relations012}, (a) is obvious. By Lemma \ref{L:odd} (b) and Corollary \ref{C:relations012} (b), $0_n=1_n$ is odd, iff $n$ is odd. By Corollary \ref{C:relations012} (a), $2_n$ is even, iff $0_n$ is odd. \end{proof} \begin{corollary} For any positive integer $n$, \begin{equation}\label{E:coro02} 0_{n+2}-0_n=2^n=2_{n+2}-2_n. \end{equation} \end{corollary} \begin{proof} By Corollary \ref{C:012sum} (a), $2_{n+1}=2^{n+1}-0_{n+2}$, so Corollary \ref{C:012sum} (c) becomes $0_n+(2^{n+1}-0_{n+2})=2^n$. Hence, $2^n=0_{n+2}-0_n$. Then, by Corollary \ref{C:relations012} (a), $2_{n+2}-2_{n}=(0_{n+2}-1)-(0_n-1)=2^n$. \end{proof} \begin{corollary} For any positive integer $n$, \begin{itemize} \item[\normalfont{(a)}] $0_n+0_{n+1}=2^n+1$; \item[\normalfont{(b)}] $2_n+2_{n+1}=2^n-1$. \end{itemize} \end{corollary} \begin{proof} Applying Corollary \ref{C:relations012} (a) to Corollary \ref{C:012sum} (a) and (c), we have $$ (0_n-1)+0_{n+1}=2^n; \phantom{m}(2_n+1)+2_{n+1}=2^n. $$ \end{proof} Finally, the explicit formulae for $0_n$, $1_n$, and $2_n$ are as follows: \begin{theorem} \label{T:explicit} For any positive integer $n$, if $n$ is odd, $$ 0_n=\frac {2^n+1}3 ; \phantom{m} 1_n=\frac {2^n+1}3; \phantom{m} 2_n=\frac {2^n-2}3, $$ and if $n$ is even, $$ 0_n=\frac {2^n+2}3 ;\phantom{m} 1_n=\frac {2^n-1}3;\phantom{m} 2_n=\frac {2^n-1}3. $$ \end{theorem} \begin{proof} By Corollary \ref{C:relations012} (a) and (c), $$ 0_n+1_n+2_n=\left\{ \begin{array}{ll} (2_n+1)+(2_n+1)+2_n =3\cdot 2_n +2, & \hbox{if \emph{n} is odd;}\\ (2_n+1)+2_n+2_n =3\cdot 2_n+1, & \hbox{if \emph{n} is even .} \end{array} \right. $$ Then, by Lemma \ref{L:odd} (a), $2^n=3\cdot 2_n +2$, if $n$ is odd, and $2^n= 3\cdot 2_n +1$, if $n$ is even. Solve for $2_n$, first. Then apply Corollary \ref{C:relations012} (a) and (c) to find $0_n$ and $1_n$. \end{proof} \section{Jacobsthal numbers and their extension}\label{S:jacobsthal} The Jacobsthal numbers $(J_n)_{n\geq 0}$ (\seqnum{A001045}) are the numbers satisfying the following recurrence relation and initial conditions: \begin{equation}\label{E:Jacobstalrec0} J_n=J_{n-1}+2\cdot J_{n-2}\phantom{mmm};\phantom{mmm} J_0=0,\phantom{m} J_1=1, \end{equation} and the $n$th Jacobsthal number $J_n$ is $0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341$, for $n=0, 1, \ldots, 10$ \cite{Sl}. Notice that $J_n=1_n$ for $n=1, 2, \ldots, 10$, which is true for any positive integer $n$. \begin{theorem} For any positive integer $n$, $1_n=J_n$. \end{theorem} \begin{proof} By Theorem \ref{T:main relations} (b), $$ \begin{array}{ll} 1_{n-1}+2\cdot 1_{n-2}&=(0_{n-2}+2_{n-2})+2\cdot 1_{n-2}\\ &=(0_{n-2}+1_{n-2})+(1_{n-2}+2_{n-2})=0_{n-1}+2_{n-1}=1_n. \end{array} $$ Hence, $1_n$ satisfies the recurrence relation in (\ref{E:Jacobstalrec0}). Since $1_1=1=J_1$ and $1_2=1=J_2$, $1_n=J_n$ for any integer $n\geq 1$. \end{proof} We also find the sequences $A_{1n}$ (\seqnum{A005578}) and $A_{2n}$ (\seqnum{A000975}) such that $A_{1 n}=0_n$ and $A_{2,n-1}=2_n$ for any positive integer $n$: $$ A_{1n}:=\left\lceil \frac{2^n}3 \right\rceil; \phantom{mm} A_{2n}:=\left\lceil \frac {2(2^n-1)}3\right\rceil, $$ for any nonnegative integer $n$ \cite{Sl}. For $n=0, 1, \ldots, 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 \ref{T:explicit}, $0_n$, $1_n$, and $2_n$ are extended for any integer $n$. \begin{definition}\label{D:012} 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$. \end{definition} For example, $0_n$, $1_n$, and $2_n$, for $n=-5, -4, \ldots, 4, 5$, are shown in Table \ref{Table2}. \begin{table}[ht] \begin{center} \begin{tabular}{|r|rrrrrrrrrrr|} \hline $n$& $-5$&$-4$& $-3$& $-2$&$-1$&0&1&2&3&4&5\\ \hline $0_n$&$\frac{11}{32}$&$\frac{11}{16}$&$\frac38$&$\frac34$&$\frac12$&1&1&2&3&6&11\\ $1_n$&$\frac{11}{32}$&$-\frac5{16}$&$\frac38$&$-\frac14$&$\frac12$&0&1&1&3&5&11\\ $2_n$&$-\frac{21}{32}$&$-\frac5{16}$&$-\frac58$&$-\frac14$&$-\frac12$&0&0&1&2&5&10\\ \hline \end{tabular} \end{center} \caption{$0_n$, $1_n$, and $2_n$, for $n=0, \pm1, \pm2, \pm3, \pm4, \pm5$} \label{Table2} \end{table} 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\in \{0, 1, 2 \}$ and any negative integer $n$, is a fraction, whose numerator in the simplest form is a Jacobsthal number. \begin{theorem} For any positive integer $n$, $$ 0_{-n}=\left\{ \begin{array}{ll} \frac{J_{n}}{2^n}, & \hbox{for odd \emph{n}}; \\ \frac {J_{n+1}}{2^n}, & \hbox{for even \emph{n};} \end{array} \right. \phantom{mm} 1_{-n}=(-1)^{n+1}\frac{J_{n}}{2^n} ; \phantom{mm} 2_{-n}=\left\{ \begin{array}{ll} -\frac{J_{n+1}}{2^n}, & \hbox{for odd \emph{n};} \\ -\frac {J_{n}}{2^n}, & \hbox{for even \emph{n}.} \end{array} \right. $$ \end{theorem} \begin{proof} By Definition \ref{D:012} and Theorem \ref{T:explicit}, for any positive integer $n$, $$ 1_{-n}=\frac{2^{-n}-(-1)^{-n}}3 =\frac{1-(-2)^n}{3\cdot 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 \ref{D:012}, $0_{-n}$ and $2_{-n}$ are calculated as desired. \end{proof} Since the explicit formulae in Theorem \ref{T:explicit} hold for any integer $n$ by Definition \ref{D:012}, almost all of the rules in Section \ref{S:modifed} hold for any integer $n$. \begin{lemma}\label{L:rel} For any integer $n$, \begin{itemize} \item[\normalfont{(a)}] $0_n+1_n+2_n=2^n$; \item[\normalfont{(b)}] $0_{n+1}=0_n+1_n;$ $1_{n+1}=0_n+2_n;$ $2_{n+1}=1_n+2_n$; \item[\normalfont{(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$; \item[\normalfont{(d)}] $0_n\geq1_n\geq2_n$. \end{itemize} \end{lemma} 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. \begin{claim} $J_n$ (\seqnum{A001045}), $A_{1n}$ (\seqnum{A005578}) , and $A_{2n}$ (\seqnum{A000975}) can be extended as follows: for any integer $n$, $$ J_n:=1_n; \phantom{mm} A_{1n}:=0_n; \phantom{mm} A_{2, n-1}:=2_n. $$ \end{claim} In particular, an extension of the Jacobsthal numbers is as follows: \begin{definition} For any positive integer $n$, $J_{-n}$ is defined as follows: $$ J_{-n}:=(-1)^{n+1}\frac {J_{n}}{2^n}. $$ \end{definition} Then the extended Jacobsthal numbers satisfy the same recurrence relation in (\ref{E:Jacobstalrec0}): $ J_{n-1}+2\cdot J_{n-2}=J_{n}, $ for any integer $n$. For example, the extended Jacobsthal numbers $J_n$, for $n=-7, -6, \ldots, 6, 7$, are shown in Table \ref{Table3}. \begin{table}[ht] \begin{center} \begin{tabular}{|r|rrrrrrrrrrrrrrr|} \hline $n$&$-7$&$-6$&$-5$&$-4$&$-3$&$-2$&$-1$&0&1&2&3&4&5&6&7\\ \hline $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\\ \hline \end{tabular} \end{center} \caption{$J_n$, for $n=\pm1, \pm2, \ldots, \pm7$} \label{Table3} \end{table} \section{More repeating strings}\label{S:additional} For an arbitrary large integer $N$, the ternary modified Collatz sequence starting with the ternary string $1\text{ }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\text{ } 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\text{ } 0^N$ for some ternary string $y$, which represents a multiple of $3^N$. \begin{observation}\label{O:seq} 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\text{ } 0^{ N})=h\text{ } r^{ \lfloor\frac N 2\rfloor}\text{ } t, $ where the string $$ r= \left\{ \begin{array}{ll} 01, & \hbox{if } [y]_3 \equiv 1 \text{ }(\text{mod } 8); \\ 10, & \hbox{if } [y]_3 \equiv 3 \text{ }(\text{mod } 8);\\ 12, & \hbox{if } [y]_3 \equiv 5 \text{ }(\text{mod } 8);\\ 21, & \hbox{if } [y]_3 \equiv 7 \text{ }(\text{mod } 8). \end{array} \right. $$ \end{observation} \begin{proof} Since $y$ is odd, the ternary string $y\text{ } 0^{ N}$ is odd, so $ g(y\text{ }0^N)=\left(\frac{[y\text{ } 0^N 1]_3}2\right)_3 $ by (\ref{E:Def}), and $ g\left(y\text{ } 0^{ N}\right)=\left(\frac {[y]_3-1}2\right)_3 z' $ for some string $z'$ such that $|z'|=|z|+1$ by Theorem \ref{T:yz}. Since $[y0^N1]_3=[([y]_3-1)_30^{N+1}]_3+[10^N1]_3$ and $ \left(\frac{[10^N1]_3}{2}\right)_3=01^N2 $ by Theorem \ref{T:001122}, $z'=1^N2$. Hence, $$ g\left(y\text{ } 0^{ N}\right)=\left(\frac {[y]_3-1}2\right)_3 1^N \text{ } 2 =\left(\frac {[y]_3-1}2\right)_3 (11)^{ \lfloor\frac{N}2\rfloor}\text{ } 1^{\left(\frac N 2-\lfloor\frac{N}2\rfloor\right)} \text{ } 2. $$ If $\frac{[y]_3-1}2$ is even, $\left\lfloor\frac{[y]_3-1}2\right\rfloor=\frac{[y]_3-1}4$, and $g$ transforms each repeating string 11 in $g(y\text{ } 0^{ N})$ to 02 in $g^2(y\text{ } 0^{ N})$ by Theorem \ref{T:001122}. Hence, by Theorem \ref{T:yz}, $$ g^2\left(y\text{ } 0^{ N}\right)=\left(\frac{[y]_3-1}4\right)_3\text{ } (02)^{ \lfloor\frac{N}2\rfloor}\text{ } t_1, $$ for some string $t_1$. Then $g$ transforms each repeating string 02 in $g^2(y\text{ } 0^{ N})$ to 01 in $g^3(y\text{ } 0^{ N})$ if $\frac{[y]_3-1}4$ is even; 12 if odd, by Theorem \ref{T:001122}. Hence, 01 and 12 repeat $\lfloor\frac{N}2\rfloor$ times in $g^3(y\text{ } 0^{ N})$, if $[y]_3 \equiv 1$ (mod 8) and $[y]_3\equiv 5$ (mod 8), respectively. If $\frac{[y]_3-1}2$ is odd, $\left\lfloor\frac{[y]_3-1}2\right\rfloor=\frac{[y]_3-3}4$, and $g$ transforms each repeating string 11 in $g(y\text{ } 0^{ N})$ to 20 in $g^2(y\text{ } 0^{ N})$ by Theorem \ref{T:001122}. Hence, by Theorem \ref{T:yz}, $$ g^2\left(y\text{ } 0^{ N}\right)=\left(\frac{[y]_3-3}4\right)_3\text{ } (20)^{ \lfloor\frac{N}2\rfloor}\text{ } t_2, $$ for some string $t_2$. Then $g$ transforms each repeating string 20 in $g^2(y\text{ } 0^{ N})$ to 10 in $g^3(y\text{ } 0^{ N})$ if $\frac{[y]_3-3}4$ is even; 21 if odd, by Theorem \ref{T:001122}. Hence, 10 and 21 repeat $\lfloor\frac{N}2\rfloor$ times in $g^3(y\text{ } 0^{ N})$, if $[y]_3 \equiv 3$ (mod 8) and $[y]_3\equiv7$ (mod 8), respectively. \end{proof} Notice that each $r$ in $g^3(y\text{ } 0^{ N})$ is an odd ternary string of length 2. Hence, we use two copies of $r$ in $g^3(y_1\text{ } 0^{ N})$ to find a repeating string in $g^4(y\text{ } 0^{ N})$, and continue to find a repeating string in $g^{n+2}(y\text{ } 0^{ N})$. Then each repeating string in $g^{n+2}(y\text{ } 0^{ N})$ has $J_n$ or $J_n\pm 1$ occurrences of digit 0, $J_n$ occurrences of digit 1, and $J_n$ or $J_n\pm 1$ occurrences of digit 2. This works for any ternary string $y$, since we can reduce $y$ to an odd string. \begin{theorem} 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}\left(y\text{ } 0^{ N}\right)=h\text{ } (r_n)^{ \lfloor\frac{N}{2^n}\rfloor}\text{ } 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. \end{theorem} \begin{proof} If $y$ is even, $g^{i_y}(y\text{ }0^N)=g^{i_y}(y)\text{ }0^N$ by Theorem \ref{T:modified} and \ref{T:001122}. Since $g^{i_y}(y)=\left(\frac{[y]_3}{2^{i_y}}\right)_3$ is odd, $g^{n+i_y}(y\text{ } 0^{ N})=g^n(y_1\text{ } 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 \ref{O:seq}: the string of length $2$ repeating $\lfloor\frac{N}{2}\rfloor$ times in the ternary $g^3(y\text{ } 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 $\lfloor\frac{N}{2^n}\rfloor$ times in $g^{n+2}(y\text{ } 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 \ref{L:odd} (b), $r_n$ is odd. Then $g(r_n{} r_n)$ repeats $\lfloor\frac{N}{2|r_n|}\rfloor$ times in $g^{n+3}(y\text{ } 0^{ N})$ by Corollary \ref{C:xx}, and $|g(r_n{} r_n)|=2|r_n|=2^{n+1}$ by Corollary \ref{C:012} (b). Hence, $g(r_n{} r_n)$ is the string of length $2^{n+1}$ repeating $\lfloor\frac{N}{2^{n+1}}\rfloor$ times in $g^{n+3}(y\text{ } 0^{ N})$, i.e., $g(r_n{} r_n)=r_{n+1}$. Then, by Corollary \ref{C:sharp}, $$ |r_{n+1}|_0=|r_n|_0+|r_n|_1;\phantom{mmm} |r_{n+1}|_1=|r_n|_0+|r_n|_2;\phantom{mmm} |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 \ref{T:main relations}, $$ |r_{n+1}|_0= 0_n+1_n=0_{n+1};\phantom{mm} |r_{n+1}|_1=0_n+2_n=1_{n+1};\phantom{mm} |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 \ref{T:main relations}, $$ |r_{n+1}|_0= 2_n+1_n=2_{n+1};\phantom{mm} |r_{n+1}|_1=2_n+0_n=1_{n+1};\phantom{mm} |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}$. \end{proof} \section{Acknowledgments} I would like to thank Mr. Andrew Mosedale for proofreading, although all remaining errors are my own. \begin{thebibliography}{99} \bibitem{Col} L. Collatz, On the motivation and origin of the ($3n+1$) problem, \textit{J. Qufu Normal University, Natural Science Edition} \textbf{3} (1986) 9--11. \bibitem{Lag} J. C. Lagarias, \textit{The Ultimate Challenge: the 3x+1 Problem}, American Mathematical Society, 2010. \bibitem{Riho} R. Terras, A stopping time problem on the positive integers, \textit{Acta Arithmetica} \textbf{30} (1976) 241--252. \bibitem{Rev} G. E. R$\acute{e}$v$\acute{e}$sz, \textit{Introduction to Formal Languages}, McGraw-Hill Book Company, 1983. \bibitem{Sha} J. Shallit, \textit{A Second Course in Formal Languages and Automata Theory}, Cambridge University Press, 2009. \bibitem{Sl} N. J. A. Sloane, Online Encyclopedia of Integer Sequences, \url{http://oeis.org}. \bibitem{Wei} E. W. Weisstein, MathWorld-A Wolfram Web Resource, \\ \url{http://mathworld.wolfram.com/Concatenation.html} . \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 11A67; Secondary 11B75. \noindent {\it Keywords}: Collatz sequence, Collatz problem, Jacobsthal number, ternary representation, $3x+1$ problem. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000975}, \seqnum{A001045}, and \seqnum{A005578}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received December 23 2015; revised versions received January 7 2016; August 31 2016; September 2 2016. Published in {\it Journal of Integer Sequences}, September 7 2016. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}