1 Introduction
Two integers
$x,y$
are congruent modulo m, where
$m\in {\mathbb {Z}}^{+}$
, if
$x-y$
is divisible by m. This relation is denoted by
$x\equiv y \pmod m$
. For fixed m, this is an equivalence relation on
$\mathbb {Z}$
. The set of integers congruent to x, that is, the equivalence class containing x, is
$\{y\in \mathbb {Z}: y=x+ ms,$
for some
$s\in \mathbb {Z}$
}. Each integer x is congruent to a unique integer between
$0$
and
$m-1$
. This unique integer will be denoted by
$[x]_{m}$
, and will be called x modulo m. Then
$x=[x]_{m}+mt$
, for some integer t. It is easily verified that
$ [x+y]_{m}\equiv [x]_{m}+[y]_{m} \pmod m$
and
$ [x\cdot y]_{m}\equiv [x]_{m}\cdot [y]_{m} \pmod m$
, for all integers
$x,y$
.
If
$x,y$
are coprime integers, there exist integers
$a,b$
such that
$xa-yb=1$
. This follows from the well-known Bezout’s identity. We will take
$x=2^{u}$
and
$y=3^v$
, or vice versa, for positive integers
$u,v$
. If
$(a,b)$
is a solution of
$2^u x-3^v y=1$
, that is,
$2^u a -3^v b=1$
, the general solution, which is the set of all solutions of
$2^u x-3^v y=1$
, is
$\{(x,y): x=a+3^v t, y=b+2^u t, t\in \mathbb {Z}\}$
. If either of
$a,b$
is positive then so is the other. If
$(a,b)$
is a solution, then a is not divisible by
$3$
and b is odd. Also, if
$a>0$
, the least solution
$(x,y)$
with
$x>0$
is
$x=[a]_{3^v}$
. Similar comments apply to the equation
$3^v x-2^u y=1$
.
Definition 1.1. If z is a nonzero integer, the odd part of z, denoted by
${\cal O}(z)$
, is defined to be the largest odd positive integer dividing z.
Remark 1.2. For any nonzero integer y and positive integer v,
${\cal {O}}(2^{v}y)={\cal {O}}(y)\le \vert y\vert .$
Definition 1.3. The Collatz map is the map
$C: \mathbb {Z}\rightarrow \mathbb {Z}$
defined by
$$ \begin{align*}C(x)=\begin{cases} 3x+1 & \mbox{if } x \mbox{ is odd} \\ x/2 & \mbox{if } x \mbox{ is even}. \end{cases}\end{align*} $$
A Collatz sequence is a sequence of integers in which each term S is obtained from its predecessor T by applying the Collatz map, that is,
$S=C(T)$
. So the sequence with intitial term T is
$T, C(T), C^{(2)}(T),C^{(3)}(T), \ldots .$
The Collatz conjecture is that, starting at any positive integer T, there exists
$n\in \mathbb {N}$
such that
$C^{(n)}(T)=1.$
This conjecture arose in 1937 in the work of L. Collatz [Reference O’Connor and Robertson3] and has yet to be resolved. Recent important results are [Reference Lagarias1, Reference Tao4].
Any odd positive integer M can be written uniquely as
$M=2^{m}x-1$
where
$m, x \in {\mathbb {Z}}^{+}$
. Applying the Collatz rule mentioned above gives the next term as
$2^{m}\cdot 3x-2$
and the next as
$2^{m-1}\cdot 3x-1$
. So, after two applications of the rule, a two has been replaced by a three. After
$2(m-1)$
applications of the rule,
$m-1$
twos have been replaced by threes and we get
$2\cdot 3^{m-1}-1$
, and a further two applications gives the even number
$3^{m}x-1$
, where all the twos have been replaced with threes. Replacing a two with a three gives a larger-valued term, so the sequence is increasing up to this term. The next odd term will be
${\cal O}(3^{m}x-1)$
.The latter is less than its predecessor and equals
$(3^{m}x-1)/2^{q}$
for some positive integer q.
We will consider sequences each beginning at a positive odd integer M expressed in the form
$M=2^{m}x-1$
, where
$m\,,x\in {\mathbb {Z}}^+$
and
$ x$
is odd. We define the map
$$ \begin{align*}L:\{M\in\mathbb{Z}^{+}: M \mbox{ odd}\}\rightarrow \{M\in\mathbb{Z}^{+}: M \mbox{ odd}\} \quad\mbox{by}\quad L(2^m x-1)={\cal O}(3^{m}x-1).\end{align*} $$
Of course,
${\cal O}(3^{m}x-1)=(3^{m}x-1)/2^{q}$
for some positive integer q. The sequences
$$ \begin{align*} T, L(T), L^{(2)}(T),L^{(3)}(T), \ldots, \end{align*} $$
where T is an odd positive integer, are the sequences under consideration in this paper. For convenience we will call them L-sequences.
Slightly more detail of the sequence
$T, L(T), L^{(2)}(T),L^{(3)}(T), \ldots $
with initial term
$T=2^{m_1}x_{1}-1$
, comes from
$$ \begin{align*}2^{m_1}x_{1}-1\mapsto 2^{m_2}x_2-1\mapsto 2^{m_3}x_3-1\mapsto 2^{m_4}x_4-1\mapsto \ldots, \end{align*} $$
where
$x_k$
is an odd positive integer defined by
$L(2^{m_k}x_{k}-1)={\cal O}(3^{m_k}x_{k}-1)=(3^{m_k}x_k-1)/ 2^{q_k}=2^{m_{k+1}}x_{k+1}-1$
, for all
$k\ge 1$
. Throughout the paper the notation
${x\mapsto y}$
will be reserved for the L-map, that is, it will mean that x and y are positive odd integers and
$L(x)=y$
.
Example 1.4. (i)
$3\,165 \mapsto 1\,187\mapsto 167\mapsto 283\mapsto 319$
since
$$ \begin{align*} 3\,165=2\cdot 1\,583-1 \quad & \mbox{and}\quad 3\cdot 1\,583 -1= 2^2\cdot 1\,187, \\ 1\,187=2^2\cdot 297-1 \quad & \mbox{and}\quad 3^2\cdot 297 -1= 2^4\cdot 167, \\ 167=2^3\cdot 21-1 \quad & \mbox{and}\quad 3^3\cdot 21 -1= 2\cdot 283, \\ 283=2^2\cdot 71-1 \quad & \mbox{and}\quad 3^2\cdot 71 -1= 2\cdot 319. \end{align*} $$
(ii)
$331\,247 \mapsto 838\,471 \mapsto 1\,414\,921 \mapsto 1\,061\,191 \mapsto 1\,790\,761$
since
$$ \begin{align*} 331\,247=2^4\cdot 20\,703-1 \quad & \mbox{and}\quad 3^4 \cdot 20\,703 -1= 2\cdot 838\,471, \\ 838\,471=2^3\cdot 104\,809 -1 \quad & \mbox{and}\quad 3^3 \cdot 104\,809 -1= 2\cdot 1\,414\,921, \\ 1\,414\,921=2\cdot 707\,461-1 \quad & \mbox{and}\quad 3\cdot 707\,461 -1= 2\cdot 1\,061\,191, \\ 1\,061\,191=2^3\cdot 132\,649-1 \quad & \mbox{and}\quad 3^3 \cdot 132\,649 -1= 2\cdot 1\,790\,761. \end{align*} $$
Definition 1.5. For
$u,P\in \mathbb {Z}^+$
with P odd satisfying
$1\le P\le 2^{u+1}-1$
define
$$ \begin{align*}{\cal C}^{+}(u,P)=\{2^{u+1}N+P: N\in \mathbb{N}\}.\end{align*} $$
Below we consider L-sequences all of whose terms belong to a class
${\cal C}^{+}(u,P)$
for some fixed u and P.
2 Main theorem
Before proving our main theorem we consider the action of the L map
$L(2^m x-1)= {\cal O}(3^m x -1)$
, where
$m,\,x\in \mathbb {Z}^+$
and x is odd, on the classes
${\cal C}^{+}(u,P)$
. Proposition 2.1 below shows that, given a class
${\cal C}^+ (u,P)$
, there always exists an element T of it such that
$L(T)$
does not belong to it. Proposition 2.2 shows that all of the elements of
${\cal C}^+ (u,P)$
can have this property, so that there are no L-sequences in
${\cal C}^+ (u,P)$
of length more than one. Proposition 2.4 shows that there is a
${\cal C}^+ (u,P)$
containing L-sequences of arbitrary length. Our main theorem will show that there are many such classes.
Proposition 2.1. Let
$u,P\in \mathbb {Z}^+$
with P odd satisfying
$1\le P\le 2^{u+1}-1$
. There exists
$T\in {\cal C}^{+}(u,P)$
such that
$L(T)\not \in {\cal C}^+(u,P)$
.
Proof. If
$L(P)\not \in {\cal C}^{+}(u,P)$
the statement is proved. Otherwise, let
$P=2^v d-1$
with
$v,d\in \mathbb {Z}^+$
and d odd. Also, let
$3^v d-1= 2^r f$
, where
$r,f\in \mathbb {Z}^+$
and f is odd. Then
$P\mapsto f$
since
$P=2^v d-1\mapsto {\cal O}(3^v d-1)= f$
. Hence
$f=2^{u+1}M +P$
for some
$M\in \mathbb {N}$
. Consider
$$ \begin{align*}2^{u+1} \cdot(2^{v+r-1})+P=2^v\{2^{u+r}+d\}-1\mapsto {\cal O}(3^v\cdot 2^{u+r} +2^r f)=3^v\cdot 2^{u} +f.\end{align*} $$
If
$3^v\cdot 2^{u} +f\in {\cal C}^{+}(u,P)$
then
$3^v\cdot 2^{u} +f=2^{u+1}K+P$
, for some
$K\in \mathbb {N}$
. Then
$$ \begin{align*}3^v\cdot 2^{u} +f=3^v\cdot 2^{u} +2^{u+1}M+P=2^{u+1}K+P,\end{align*} $$
so
$2^{u+1}K-3^v\cdot 2^{u}=2^{u+1}M$
and hence
$2K-3^v=2M$
, which is a contradiction. Thus
$T=2^{u+1} \cdot (2^{v+r-1})+P$
satisfies
$L(T)\not \in {\cal C}^{+}(u,P)$
.
Proposition 2.2. Let
$u,P\in \mathbb {Z}^+$
with P odd satisfying
$1\le P\le 2^{u+1}-1$
. If
${P=2^v d-1}$
with
$v,d \ge 1$
and d odd, and
$3^v d-1=2^r f$
with
$r,f\ge 1$
and f odd, then there are no
$T\in {\cal C}^{+}(u,P)$
such that
$L(T)\in {\cal C}^{+}(u,P)$
if
$u-v>r$
and
$(f-P)/2$
is odd.
Proof. Let
$u-v>r$
and
$(f-P)/2$
be odd. Then, for any
$N\in \mathbb {N}$
,
$$ \begin{align*} T & =2^{u+1}N+P=2^v\{2^{u-v+1}N+d\}-1\mapsto{\cal O}(3^{v}\cdot 2^{u-v+1}+3^{v}\cdot d -1) \\ & ={\cal O}(3^{v}\cdot 2^{u-v+1}+2^r f )={\cal O}(3^{v}\cdot 2^{u-v-r+1}+f )=3^{v}\cdot 2^{u-v-r+1}+f. \end{align*} $$
Now
$3^{v}\cdot 2^{u-v-r+1}+f\in {\cal C}^{+}(u,P)$
if and only if there exists
$M\in \mathbb {N}$
for which we have
$3^{v}\cdot 2^{u-v-r+1}+f=2^{u+1}M+P$
, that is, if and only if
$2^{u}M-3^{v}\cdot 2^{u-v-r} N=(f-P)/2$
. Since
$u-v>r$
and
$(f-P)/2$
is odd, no such M can exist.
Example 2.3. If
$u\ge 4$
there is no
$N\in \mathbb {N}$
such that
$L(2^{u+1}N+11)=2^{u+1}M+11$
, for some
$M\in \mathbb {N}$
. Here
$v=2, d=3, w=1, r=1, f=13.$
Briefly,
$2^{u+1} N+11=2^2\{2^{u-1}N+3\}-1\mapsto {\cal O}(3^2\cdot 2^{u-1}N +26)=3^2\cdot 2^{u-2}N+13=2^{u+1}M+11$
if and only if
$2^u M-3^2\cdot 2^{u-3}N=1$
.
Proposition 2.4. For every
$n\in \mathbb {Z}^+, n\ge 2$
, let
$T_{1}^{(n)}=4\cdot 8^{n+1}-5$
. Then
$T_{1}^{(n)}$
is the first term of an L-sequence in
${\cal C}^+(4,27)$
with n terms.
Proof. For
$2\le k\le n$
define
$T_{k}^{(n)}$
by
$T_{k}^{(n)}=4\cdot 3^{2(k-1)}\cdot 8^{n-k+2}-5$
. We show that
$L(T_{k}^{(n)})=T_{k+1}^{(n)}$
, for
$1\le k\le n-1$
. This is true if
$k=1$
since
$T_{1}^{(n)}=4\cdot 8^{n+1}-5=4\{8^{n+1}-1\}-1\mapsto {\cal O}(3^2\cdot 8^{n+1}-10)=4\cdot 3^{2}\cdot 8^n-5$
. Let
$2\le k\le n-1$
. We have
$T_{k}^{(n)}{\kern1pt}={\kern1pt}4{\kern1pt}\cdot{\kern1pt} 3^{2(k-1)}{\kern1pt}\cdot{\kern1pt} 8^{n-k+2}{\kern1pt}-{\kern1pt}5{\kern1pt}={\kern1pt}4\{3^{2(k-1)}{\kern1pt}\cdot{\kern1pt} 8^{n-k+2}-1\}{\kern1pt}-{\kern1pt}1{\kern1pt}\mapsto{\kern1pt} {\cal O}(3^{2k}\cdot 8^{n-k+2}{\kern1pt}-{\kern1pt}10)= 4\cdot 3^{2k}\cdot 8^{n-k+1}-5$
. Since
$T_{k}^{(n)}=32(3^{2(k-1)}\cdot 8^{n-k+1}-1)+27$
, for
$1\le k\le n$
,
$T_{1}^{(n)}$
is the first term of an L-sequence in
${\cal C}^+(4,27)$
with n terms.
Definition 2.5. For
$p\in \mathbb {N}$
and
$U\in \mathbb {Z}, U\ne 1$
, define
$Z_p(U)={(U^{p}-1)}/{(U-1)}$
, taking
$0^0=1$
so that
$Z_0(0)=0$
.
Remark 2.6. Note that, for
$p\ge 1$
,
$Z_p(U)=1+U+U^2+\cdots +U^{p-1}$
, so
$Z_{p+1}(U)=Z_{p}(U)+U^{p}$
and
$Z_p(U)=UZ_{p-1}(U)+1$
.
Lemma 2.7. For all
$k\in \mathbb {N}$
, if
$a,b,u,v\in \mathbb {Z}^+$
with
$2^u a-3^v b=1$
and
$Y=3^v(a-b)$
, then
$3^{v(k+1)}b(a-b)^k + 3^{v}a Z_{k}(Y)=2^{u}aZ_{k+1}(Y)-1$
.
Proof. Notice first that
$3^v a Z_{k}(Y)= 2^u a Z_k(Y)+Y^k -1$
. This follows from
$$ \begin{align*}(2^u a-3^v a)Z_{k}(Y)=(2^u a-3^v b+3^v(b-a))Z_{k}(Y)=(1-Y)Z_k (Y)=1 -Y^k.\end{align*} $$
Then
$$ \begin{align*} &3^{v(k+1)}b(a-b)^k + 3^{v} aZ_{k}(Y)=3^{v}bY^{k}+ 2^{u}a Z_{k}(Y)+Y^{k}-1 \\ &\quad = (3^{v}b-2^u a)Y^{k}+ 2^{u}a (Y^k +Z_{k}(Y))+Y^{k}-1 \\ &\quad =-Y^{k}+ 2^{u}a Z_{k+1}(Y)+Y^{k}-1= 2^{u}a Z_{k+1}(Y)-1.\\[-2.8pc] \end{align*} $$
Theorem 2.8 (Main Theorem).
Let
$v,w\in \mathbb {Z}^+$
and let
$(f,d)$
be the solution to
$3^v d-2^w f=1$
which has f as the smallest odd positive integer. Let
$P=2^v d-1$
and
$u=v+w$
. Let
$(a,b)$
be the least positive solution of
$2^u a -3^v b=1$
and let
$(A,B)$
be the least positive solution of
$2^u A-3^v B=C$
where
$C=(f-P)/2$
. Let
$E=b(A-B)$
and
$F=a(A-B)$
.
-
(i) The integer d is odd and
$1\le P< 2^{u+1}-1.$
-
(ii)
$L(2^{u+1}N+P)=2\cdot 3^v N+f$
, that is,
$2^{u+1}N+P\mapsto 2\cdot 3^v N+f$
, for every
$N\in \mathbb {N}$
. -
(iii) For
$n\in \mathbb {Z}^+,\, n\ge 2$
, define
$T_{1}^{(n)}$
by where
$$ \begin{align*}T_1^{(n)}= 2^{u+1}B+P+E\, 2^{2u+1}Z_{n-2}(X),\end{align*} $$
$X=2^{u}(a-b)$
. Let
$t\in \mathbb {Z}$
be such that
$S_{1}^{(n;t)}=T_1^{(n)}+2^{nu+1}t$
is positive. Then
$\{S_{k}^{(n;t)}: 1\le k\le n\}$
is an L-sequence in
${\cal C}^{+}(u,P)$
where for
$$ \begin{align*} S_{k}^{(n;t)} & = 2^{u+1}A+P+E 2^{u+1}\cdot 3^{v(k-1)}(a-b)^{k-2}Z_{n-k}(X) \\ &\quad +F 2^{u+1}\cdot 3^v Z_{k-2}(Y) +3^{(k-1)v}\cdot 2^{(n-k+1)u+1}t, \end{align*} $$
$2\le k\le n$
, where
$Y=3^v(a-b)$
.
-
(iv) We have
$C>0$
if and only if
$3^v>2^u$
if and only if
$L(2^{u+1}N+P)>2^{u+1}N+P, $
for every
$N\in \mathbb {N}$
. Consequently,
$\{S_{k}^{(n;t)}: 1\le k\le n\}$
is an increasing sequence if
$3^v>2^u$
. -
(v) If
$C\ne 0$
we have
$C<0$
if and only if
$3^v<2^u$
if and only if
$L(2^{u+1}N+P)<2^{u+1}N+P, $
for every
$N\in \mathbb {N}$
. Consequently,
$\{S_{k}^{(n;t)}: 1\le k\le n\}$
is a decreasing sequence if
$3^v<2^u$
and
$ C\ne 0$
. -
(vi)
-
(a) With
$T_{n}^{(n)}$
defined by
$T_{n}^{(n)}= 2^{u+1}A+P+F\,2^{u+1}\cdot 3^v Z_{n-2}(Y)$
, every L-sequence in
${\cal C}^+(u,P)$
with
$n\ge 2$
terms has initial term
$T_{1}^{(n)}+ 2^{nu+1}s$
, and final term
$T_{n}^{(n)}+2^{u+1}\cdot 3^{(n-1)v}s$
for some
$s\in \mathbb {Z}.$
-
(b) The least initial term of an L-sequence in
${\cal C}^+(u,P)$
with n terms is
$[T_{1}^{(n)}]_{2^{nu+1}}$
.
-
Proof. (i) Clearly d must be odd. Let
$d_0, f_0$
be the smallest positive solution of
$3^v d_0-2^w f_0=1$
. Then
$f=f_0$
if
$f_0$
is odd and
$f_0+3^v$
otherwise. Correspondingly,
$d=d_0$
or
$d_0+2^w$
. But
$d_0<2^w$
so
$d<2^{w+1}$
and
$P=2^v d-1<2^{u+1}-1$
since
$u=v+w$
.
(ii) Let
$N\in \mathbb {N}$
. Then
$2^{u+1}N+P=2^{u+1}N+2^v d-1=2^v\{2^{w+1}N+d\}-1\mapsto {\cal O}(3^v \cdot 2^{w+1}N+3^v d-1) ={\cal O}(3^v \cdot 2^{w+1}N+2^w f)=3^v \cdot 2N+f$
.
(iii) Clearly
$S_{k}^{(n;t)}$
is congruent to P modulo
$2^{u+1}$
, for
$1\le k\le n$
. Since
$L(T)\ge 1$
, for every
$T\in \mathbb {Z}^+$
it only remains to show that
$L(S_{k}^{(n;t)})=S_{k+1}^{(n;t)}$
, for
$1\le k\le n$
. We have
$$ \begin{align*} S_{1}^{(n;t)} & = 2^{u+1}B+P+E2^{2u+1}Z_{n-2}(X)+2^{nu+1}t \\& =2^v\{2^{w+1}B+E2^{u+w+1}Z_{n-2}(X) +2^{(n-1)u+w+1}t+d\}-1 \\& \mapsto {\cal O}(3^v\cdot 2^{w+1}B+E2^{u+w+1}\cdot 3^vZ_{n-2}(X)+3^v\cdot 2^{(n-1)u+w+1}t+2^w f ) \\& =3^v\cdot 2 B+E2^{u+1}\cdot 3^v Z_{n-2}(X)+3^v\cdot 2^{(n-1)u+1}t+f \\& =2^{u+1}A+P+E2^{u+1}\cdot 3^v Z_{n-2}(X)+3^v\cdot 2^{(n-1)u+1}t, \end{align*} $$
since
$2^u A-3^v B=(f-P)/2$
. Thus
$L(S_{1}^{(n;t)})=S_{2}^{(n;t)}$
. Let
$2\le k\le n$
. Then
$$ \begin{align*} S_{k}^{(n;t)} &= 2^{u+1}A+P+E 2^{u+1}\cdot 3^{v(k-1)}(a-b)^{k-2}Z_{n-k}(X)\\&\quad+F 2^{u+1}\cdot 3^v Z_{k-2}(Y)+3^{(k-1)v}\cdot2^{(n-k+1)u+1}t \\ & =E 2^{u+1}\cdot 3^{v(k-1)}(a -b)^{k-2}{Z_{n-k}(X)}+F2^{u +1}\cdot 3^{v}Z_{k-2}(Y)\\&\quad+2^{u+1}A+3^{(k-1)v}\cdot 2^{(n-k+1)u+1}t+2^v d-1 \\ & =2^{v}\{E 2^{w+1}\cdot 3^{v(k-1)}(a -b)^{k-2}{Z_{n-k}(X)}+F 2^{w+1}\cdot 3^{v}Z_{k-2}(Y)\\&\quad+2^{w +1}A +3^{(k-1)v}\cdot 2^{(n-k)u+w+1}t + d\}-1 \\ & \mapsto{\cal O}(E 2^{w+1}\cdot 3^{vk}(a -b)^{k-2}Z_{n-k}(X)+F 2^{w +1}\cdot 3^{2v}Z_{k-2}(Y)\\&\quad+2^{w +1}\cdot 3^{v}A + 3^{kv}\cdot 2^{(n-k)u+w+1}t +2^{w}f) \\ & =E 2\cdot 3^{vk}(a -b)^{k-2}Z_{n-k}(X)+F 2\cdot 3^{2v}Z_{k-2}(Y)+2\cdot 3^{v}A\\&\quad+3^{kv}\cdot 2^{(n-k)u+1}t + f =L(S^{(n;t)}_{k}). \end{align*} $$
Since
$Z_p(U)=UZ_{p-1}+1$
,
$$ \begin{align*} L(S^{(n;t)}_{k}) & =E 2\cdot 3^{vk}(a -b)^{k-2}X Z_{n-k-1}(X)+E 2\cdot 3^{vk}(a -b)^{k-2} \\ &\quad+F 2\cdot 3^{2v}Z_{k-2}(Y)+2\cdot 3^{v}A +3^{kv}\cdot 2^{(n-k)u+1}t+ f. \end{align*} $$
Now, using Lemma 2.7,
$$ \begin{align*} E2\cdot 3^{vk}(a -b)^{k-2}+F 2\cdot 3^{2v}Z_{k-2}(Y) & =2(A-B)3^{v}\{3^{v(k-1)}(a-b)^{k-2} b+ a 3^{v} Z_{k-2}(Y)\} \\ & =2(A-B)3^{v}(a 2^{u}Z_{k-1}(Y)-1). \end{align*} $$
So
$$ \begin{align*} & E2\cdot 3^{vk}(a -b)^{k-2}+F 2\cdot 3^{2v}Z_{k-2}(V)+2\cdot 3^{v}A + f \\ &\quad =2(A-B)3^{v}\{a 2^{u}Z_{k-1}(Y)-1\}+2\cdot 3^{v}A + f \\ &\quad =2^{u +1} F 3^{v}Z_{k-1}(Y)-2(A-B)3^{v}+2\cdot 3^{v}A + f \\ &\quad =2^{u +1} F 3^{v}Z_{k-1}(Y)+2\cdot 3^{v}B + f =2^{u +1} F 3^{v}Z_{k-1}(Y)+2^{u +1}A+P. \end{align*} $$
Since
$X=2^{u}(a-b)$
this gives the value of
$L(S_{k}^{(n;t)})$
as
$$ \begin{align*} & E 2\cdot 3^{vk}(a -b)^{k-2}X Z_{n-k-1}(X)+2^{u +1} F 3^{v}Z_{k-1}(Y)+2^{u +1}A+P+3^{kv}\cdot 2^{(n-k)u+1}t \\ & \quad=E 2^{u +1}\cdot 3^{vk}(a -b)^{k-1}Z_{n-k-1}(X)+2^{u +1} F 3^{v}Z_{k-1}(Y)+2^{u +1}A+P+3^{kv}\cdot 2^{(n-k)u+1}t, \end{align*} $$
that is,
$S_{k+1}^{(n;t)}$
. Thus
$\{S_{k}^{(n;t)}: 1\le k\le n\}$
is an L-sequence in
${\cal C}^+(u,P)$
.
(iv) and (v). We have
$2C\kern1.4pt{=}\kern1.4pt f-P$
giving the equations
$2^{w+1}C\kern1.4pt{=}\kern1.4pt 2^w f -2^w(2^v d-1)\kern1.4pt{=} 3^vd-1-2^ud +2^w=(3^v-2^u)d+2^w -1$
so
$2^{w+1}C=(3^v-2^u)d+2^w -1$
. Rearranging the latter gives a second equation
$(3^v-2^u)d=2^w(2C-1)+1$
.
From the first equation
$3^v>2^u$
implies
$C>0$
. From the second equation
$C>0$
implies
$3^v>2^u$
.
Suppose that
$C\ne 0$
. The first equation shows that
$C<0$
implies
$3^v<2^u$
. The second equation shows that
$3^v<2^u$
implies
$2C<1$
which implies
$C<0$
.
By (i), for every
$n\in \mathbb {N}$
,
$L(2^{u+1}N+P)-(2^{u+1}N+P)=2N(3^v-2^u)+2C$
. The desired results follow.
(vi)(a) We prove the result by induction on n.
Let
$W_1=2^{u+1}N_1+P$
and
$W_2=2^{u+1}N_2+P$
for some
$N_1, N_2\in \mathbb {N}$
with
$L(W_1)=W_2$
. By (i),
$L(W_1)=2\cdot 3^v N_1+f$
so
$2^{u+1}N_2+P=2\cdot 3^v N_1+f$
. This gives
$2^u N_2- 3^v N_1=C$
. Since
$2^u A-3^v B=C$
it follows that
$N_1=B+2^u s, N_2=A+3^v s$
, for some
$s\in \mathbb {Z}$
. Hence
$W_1=2^{u+1}B+P+2^{2u+1}s$
and
$W_2=2^{u+1}A+P+2^{u+1}\cdot 3^v s$
. Since
$T_{1}^{(2)}=2^{u+1}B+P$
and
$T_{2}^{(2)}=2^{u+1}A+P$
the result is proved for
$n=2$
.
Let
$n\ge 2$
and suppose that the result is true for n. Let
$\{W_k\}_{1}^{n+1}$
be an L-sequence in
${\cal C}^+(u,P)$
. By the induction assumption, since
$\{W_k\}_{1}^{n}$
and
$\{W_k\}_{2}^{n+1}$
are L-sequences in
${\cal C}^+(u,P)$
,
$W_1=T_1^{(n)}+2^{nu+1}p$
for some
$p\in \mathbb {Z}$
and
$W_2=T_1^{(n)}+2^{nu+1}q$
, for some
$q\in \mathbb {Z}$
. Also
$W_{n+1}=T_n^{(n)}+2^{u+1}\cdot 3^{(n-1)v}q$
. Additionally, since
$W_2=L(W_1)$
we have
$2^u N_2-3^v N_1=C $
where
$W_1=2^{u+1}N_1+P$
and
$W_2=2^{u+1}N_2+P$
. Let
$T_{1}^{(n)}=2^{u+1}{N_1^{(n)}+P}$
. Then
$N_1=N_1^{(n)}+2^{(n-1)u}p$
,
$N_2=N_1^{(n)}+2^{(n-1)u}q$
and
$$ \begin{align*}2^u\{N_1^{(n)}+2^{(n-1)u}q\}-3^v\{N_1^{(n)}+2^{(n-1)u}p\}=C.\end{align*} $$
This gives
$$ \begin{align} 2^{nu}q-2^{(n-1)u}\cdot 3^v p=C-(2^u - 3^v)N_1^{(n)}. \end{align} $$
Now
$N_1^{(n)}=B+b(A-B)2^u Z_{n-2}(X)$
and
$C=2^u A-3^v B$
, so
$$ \begin{align*} C-(2^u - 3^v)N_1^{(n)} & =2^u A-3^v B-2^u B + 3^v B-(2^u-3^v)b(A-B)2^u Z_{n-2}(X) \\ & =2^u(A-B)\{1-b(2^u-3^v)Z_{n-2}(X)\} \\ & =2^u(A-B)\{1-(2^u b-2^u a+ 2^u a-3^v b)Z_{n-2}(X)\} \\ & =2^u(A-B)\{1-(1-2^u(a-b))Z_{n-2}(X)\} \\ & =2^u(A-B)\{1-(1-X)Z_{n-2}(X)\}=2^u(A-B) X^{n-2} \\ & =2^{(n-1)u}(A-B)(a-b)^{n-2}. \end{align*} $$
Substituting this in (2.1) gives
$$ \begin{align*}2^u q-3^v p=(A-B)(a-b)^{n-2}.\end{align*} $$
Since
$2^u a -3^v b=1$
this implies that
$p=b(A-B)(a-b)^{n-2}+2^u s$
and
$q= a(A-B)(a-b)^{n-2}+3^v s$
for some
$s\in \mathbb {Z}$
. Substituting these values for
$p,q$
in the equations for
$W_1$
and
$W_{n+1}$
gives
$$ \begin{align*} W_1 & =T_1^{(n)}+2^{nu+1}\{b(A-B)(a-b)^{n-2}+2^u s\} \\ & =\{T_1^{(n)}+2^{nu+1}b(A-B)(a-b)^{n-2}\}+2^{(n+1)u+1}s=T_1^{(n+1)}+2^{(n+1)u+1}s \end{align*} $$
and
$$ \begin{align*} W_{n+1} & =T_n^{(n)}+2^{u+1}\cdot 3^{(n-1)v}\{a(A-B)(a-b)^{n-2}+3^v s\} \\ &=\{T_n^{(n)}+2^{u+1}\cdot 3^{(n-1)v}a(A-B)(a-b)^{n-2}\}+ 2^{u+1}\cdot 3^{nv}=T_{n+1}^{(n+1)}+2^{u+1}\cdot 3^{nv}s, \end{align*} $$
where we have used the facts
$$ \begin{align*} T_{1}^{(n+1)}-T_{1}^{(n)} & =b(A-B)2^{2u+1}\{Z_{n-1}(X)-Z_{n-2}(X)\} \\ &=b(A-B)2^{2u+1}X^{n-2}=b(A-B)2^{nu+1}(a-b)^{n-2} \end{align*} $$
and
$$ \begin{align*} T_{n+1}^{(n+1)}-T_{n}^{(n)} & =a(A-B)2^{u+1}\cdot 3^v\{Z_{n-1}(Y)-Z_{n-2}(Y)\} \\ & =a(A-B)2^{u+1}\cdot 3^vY^{n-2}=a(A-B)2^{u+1}\cdot 3^{(n-1)v}(a-b)^{n-2}. \end{align*} $$
This completes the proof by induction.
(vi)(b) Let
$t\in \mathbb {Z}$
and suppose that
$W_1=T_1^{(n)}+2^{nu+1}t\in {\cal C}^+(u,P)$
. Let
$\{W_k\}_{1}^{n}$
be the L-sequence with initial term
$W_1$
. Let
$T_{k}^{(n)}=2^{u+1}N_{k}^{(n)}+P$
for
$1\le k\le n$
. We prove by induction that, for
$1\le k\le n$
,
$$ \begin{align*}W_k=2^{u+1}N_{k}^{(n)}+2^{(n-k+1)u+1}\cdot 3^{(k-1)v}t +P. \end{align*} $$
The result is true for
$k=1$
. Let
$1\le k\le n-1$
and suppose that the result is true for k. Then
$$ \begin{align*} W_k & =2^{u+1}N_{k}^{(n)}+ 2^{(n-k+1)u+1}\cdot 3^{(k-1)v}t +P = 2^v\{2^{w+1}N_{k}^{(n)}+2^{(n-k)u+w+1}\cdot 3^{(k-1)v}t +d\}-1 \\ & \mapsto{\cal O}(2^{w+1}\cdot 3^vN_{k}^{(n)}+2^{(n-k)u+w+1}\cdot 3^{kv}t +2^w f) =2\cdot 3^v N_{k}^{(n)}+2^{(n-k)u+1}\cdot 3^{kv}t +f. \end{align*} $$
But
$T_{k+1}^{(n)}=L(T_{k}^{(n)})= 2\cdot 3^v N_{k}^{(n)}+f$
, so
$$ \begin{align*}W_{k+1}=T_{k+1}^{(n)}+2^{(n-k)u+1}\cdot 3^{kv}t=2^{u+1}N_{k+1}^{(n)}+2^{(n-k)u+1}\cdot 3^{kv}t+P.\end{align*} $$
This completes the induction proof. Clearly,
$W_k\in {\cal C}^+(u,P)$
for
$1\le k\le n$
.
By (iii) and (vi)(a), a positive odd integer T is the initial term of an L-sequence with
$n\ge 2$
terms in
${\cal C}^+(u,P)$
if and only if
$T\equiv T_{1}^{(n)}$
(mod
$2^{nu+1})$
. The least such T is
$[T_{1}^{(n)}]_{2^{nu+1}}$
.
Remark 2.9. The following remarks are presented in the context of the hypotheses of Theorem 2.8.
If
$a=b$
, the formula
$T_1^{(n)}= 2^{u+1}B+P+E\, 2^{2u+1}Z_{n-2}(X)$
in the theorem becomes
$$ \begin{align*}T_1^{(n)}= 2^{u+1}B+P+b(A-B) 2^{2u+1}Z_{n-2}(0) =2^{u+1}B+P+b(A-B) 2^{2u+1}.\end{align*} $$
This is independent of n for
$n\ge 2$
. An explanation for this is as follows. If
$a=b$
then
$(2^u-3^v)b=1.$
Thus
$b=1 $
and
$2^u-3^v=1$
so
$u>1$
. By the truth of the Catalan conjecture [Reference Mihailescu2] we must then have
$v=1$
, so
$u=2$
and
$w=1$
. Also
$3^v d-2^w f=1$
becomes
$3d-2f=1$
so
$f=d=1$
. Then
$P=1$
and
$C=0$
. Since
$2^u A-3^v B=C$
,
$A=3$
and
$B=4$
, so
$A-B=-1$
. Substituting these values into the formula for
$T_1^{(n)}$
we get
$T_1^{(n)}= 2^3\cdot 4+1-2^5=1$
. Of course
$L(1)=1$
so the L-sequence that we get in
${\cal C}^+(2,1)$
is the constant sequence
$1$
.
If
$A=B$
, the formula
$T_1^{(n)}= 2^{u+1}B+P+E\, 2^{2u+1}$
becomes
$T_1^{(n)}= 2^{u+1}B+P$
. Again this is independent of n for
$n\ge 2$
. If
$A=B$
, then
$(2^u-3^v)B=C$
. Since
$2C=f-P$
,
$$ \begin{align*}2^{w+1}(2^u-3^v)B=2^w(f-P)=3^vd -1-2^u d+2^w.\end{align*} $$
Rearranging this gives
$$ \begin{align*}(2^u-3^v)\{2^{w+1}B +d\}=2^w-1.\end{align*} $$
Since
$2^w -1>0$
,
$2^u-3^v\ge 1$
so
$B=0$
since
$2^{w+1}>2^w$
. Then
$C=0$
so
$f=P$
. Since we always have
$L(P)=f$
we deduce that
$T_1^{(n)}= P$
and the L-sequence that we get in
${\cal C}^+(u,P)$
is the constant sequence P. (If
$(2^{v+w}-3^v)d=2^w-1$
has only the trivial solution
$v=w=d=1$
then
$P=1$
. The author has not been able to prove this.)
Example 2.10. Again, the examples are based on the hypotheses of Theorem 2.8.
(1) Suppose
$v=w=1$
. Clearly
$d=f=1$
and
$P=1, C=(f-p)/2=0$
. Also,
$u=2$
and
$a=b=1$
since
$2^2a-3b=1$
. By the case
$a=b$
of Remark 2.9, the L-sequence that we get in
${\cal C}^+(2,1)$
is the constant sequence
$1$
.
(2) Suppose
$v=2, w=3$
. Since
$3^2 d-2^3 f=1$
, once again
$d=f=1$
. This time
$P=3, u=5$
and
$C= -1$
. Since
$2^5 a-3^2 b=1$
, we have
$a=2, b=7$
so
$X=2^{5}(-5)=-160$
. Since
$2^5 A-3^2 B=-1$
, we have
$A=7, B=25$
. Then
$$ \begin{align*}T_{1}^{(n)}=2^{6}\cdot 25+3+7(-18)2^{11}Z_{n-2}(-160).\end{align*} $$
For example, taking
$n=4$
gives
$T_{1}^{(4)}=41\,031\,235$
and we get the L-sequence
$$ \begin{align*}41\,031\,235\mapsto 11\,540\,035\mapsto 3\,245\,635\mapsto 912\,835\end{align*} $$
in
${\cal C}^+(5,3)$
. (Here
$C<0$
and
$3^v-2^u=-23<0$
so we expect this sequence to be decreasing.) Since
$[T_{1}^{(n)}]_{2^{nu+1}}=[41\,031\,235]_{2\,097\,152}=1\,185\,347$
, the least initial term of an L-sequence in
${\cal C}^+(5,3)$
with four terms is
$1\,185\,347$
. In fact,
$$ \begin{align*}1\,185\,347\mapsto 333\,379\mapsto 93\,763\mapsto 26\,371.\end{align*} $$
(3) Suppose
$v=4, w=2$
. Since
$3^4 d-2^2 f=1$
, we have
$d=5$
and
$f=101$
(recall that f must be odd). This time,
$P=79, u=6$
and
$C= 11$
. Since
$2^6 a-3^4 b=1$
, we have
$a=19, b=15$
, so
$X=2^{6}(4)=2^8$
. Since
$2^6 A-3^4 B=11$
, we have
$A=47, B=37$
. Then
$$ \begin{align*}T_{1}^{(n)}=2^{7}\cdot 37+79+15(10)2^{13}Z_{n-2}(2^8).\end{align*} $$
For example, taking
$n=4$
gives
$T_{1}^{(4)}=315\,806\,415$
and we get the L-sequence
$$ \begin{align*}315\,806\,415\mapsto 399\,692\,495\mapsto 505\,860\,815\mapsto 640\,230\,095\end{align*} $$
in
${\cal C}^+(6,79)$
. (Here
$3^v-2^u=17>0$
so we expect this sequence to be increasing.) Since
$[T_{1}^{(n)}]_{2^{nu+1}}=[315\,806\,415]_{33\,554\,432}=13\,816\,527$
, the least initial term of an L-sequence in
${\cal C}^+(6,79)$
with four terms is
$13\,816\,527$
. In fact,
$$ \begin{align*}13\,816\,527\mapsto 17\,486\,543\mapsto 22\,131\,407\mapsto 28\,010\,063.\end{align*} $$
Table 1 shows all of the classes
${\cal C}^+(u,P)$
satisfying the hypotheses of our main theorem for values of the parameters v and w satisfying
$1\le v,w\le 4$
. It also shows whether an increasing or decreasing L-sequence is obtained by applying the theorem.
3 Increasing sequences
Table 1 indicates that examples of increasing L-sequences are harder to find. These are the type of sequences that may be useful in developing techniques to solve the Collatz problem. Table 2 gives more examples of increasing L-sequences derived from Theorem 2.8(iii).
Classes
$\mathcal {C}^+(u,P)$
for Theorem 2.8 with
$1\le v,w\le 4$
.
Increasing L-sequences.
We conclude by considering increasing L-sequences in the classes of the form
${\cal C}^+(4, P)$
for P an odd integer satisfying
$1\le P\le 31$
. The following list of data (which continues on the next page) will be useful. For every
$N\in \mathbb {N}$
,
$$ \begin{align*} & 32N+1=2\{16N+1\}-1 \mapsto 24N+1 \ (\, < 32N+1 \mbox{ if } N>0), \\& 32N+3=4\{8N+1\}-1 \mapsto {\cal{O}}(9N+1)\le 9N+1< 32N+3, \\& 32N+5=2\{16N+3\}-1 \mapsto 6N+1<32N+5, \\& 32N+9=2\{16N+5\}-1 \mapsto 24N+7<32N+9, \\& 32N+13=2\{16N+7\}-1 \mapsto 12N+5<32N+13, \\& 32N+17=2\{16N+9\}-1 \mapsto 24N+13<32N+17, \\& 32N+19=4\{8N+5\}-1 \mapsto 18N+11<32N+19, \\& 32N+21=2\{16N+11\}-1 \mapsto {\cal{O}}(3N+2)\le 3N+2<32N+21, \\& 32N+23=8\{4N+3\}-1 \mapsto {\cal{O}}(27N+20)\le 27N+20<32N+23, \\& 32N+25=2\{16N+13\}-1 \mapsto 24N+19<32N+25, \\& 32N+29=2\{16N+15\}-1 \mapsto 12N+11< 32N+29, \\[5pt]& 32N+7=8\{4N+1\}-1 \mapsto 54N+13>32N+7, \\& 32N+11=4\{8N+3\}-1 \mapsto 36N+13>32N+11, \\& 32N+27=4\{8N+7\}-1 \mapsto 36N+31>32N+27, \\[5pt]& 32N+15=16\{2N+1\}-1 \mapsto {\cal O}(81N+40), \\& 32N+31=32\{N+1\}-1\mapsto ? \end{align*} $$
For the first eleven cases in the above list there can be no increasing L-sequences in
$ {\cal C}^+(4,P)$
since we have
$L(T)<T$
, for every
$T\ne 1$
.
For
$P\in \{7,15,31\}$
increasing L-sequences in
$ {\cal C}^+(4,P)$
exist, directly or indirectly, by (iii) of our main theorem. Proof of this for the case
$P=7$
follows directly from (iii) of our main theorem (see row (9) of Table 1). For the case
$P=15$
, proof follows indirectly from (iii) of our main theorem, once it is observed that
${\cal C}^+(5,47)\subseteq {\cal C}^+( 4,15)$
and
${\cal C}^+(5,47)$
occurs as row (10) of Table 1. For the case
$P=31$
, proof follows indirectly from (iii) of our main theorem. Note that each of
${\cal C}^+(7,191), {\cal C}^+(9,63), {\cal C}^+(8,127), {\cal C}^+(9,895), {\cal C}^+(10,1\,407)$
is a subset of
${\cal C}^+(4,31)$
, since
$191$
,
$63$
,
$127$
,
$895$
,
$1\,407$
are all congruent to
$31$
modulo
$32$
. These classes occur as rows (19), (21), (22), (23), (25), respectively, of Table 2.
The case
$P=27$
is established by Proposition 2.4. Note that from the data listed above,
$L(T)>T$
for all
$T\in {\cal C}^+(4,27)$
so this L-sequence is increasing.
The case
$P=11$
is extreme. We observed in Example 2.3 that
$L(T)\not \in {\cal C}^+(4,11)$
for every
$T\in {\cal C}^+(4,11)$
(so the longest L-sequence in
${\cal C}^+(4,11)$
has length one).
Remark 3.1. With the hypotheses and notation of the main theorem, notice that
$$ \begin{align*}T_{1}^{(n+1)}-T_{1}^{(n)}=b(A-B)2^{2u+1}\{Z_{n-1}(X)-Z_{n-2}(X)\}=b(A-B)(a-b)^{n-2}2^{nu+1}.\end{align*} $$
The examples of increasing L-sequences that we obtain from (iv) of our main theorem arise when
$3^v>2^u$
. In this case
$T_{1}^{(n)}$
increases with n. For if
$3^v>2^u$
we must have
$a-b>0$
and
$A-B>0$
. Indeed, if
$a<b$
then
$1=2^u a-3^v b<(2^u -3^v) b<0$
. Similarly, if
$A<B$
then
$C=2^u A-3^v B<(2^u-3^v)B<0$
, a contradiction.
For example, taking
$P=1\,407$
and
$u=10$
(so
$v=7, w=3$
) gives
$$ \begin{align*}T_{1} ^{(n+1)}=T_{1}^{(n)}+168\,844 (251)^{n-2}\cdot 2^{10n +1}.\end{align*} $$
Using this iteration,
$T_{1}^{(4)}=1\,599\,633\,425\,791$
. Since this is less that
$2^{41}$
, it follows from (vi)(b) of our main theorem that the L-sequence with four terms, each term congruent to
$1\,407$
modulo
$ 2^{11}$
with least initial term has initial term
$1\,599\,633\,425\,791\approx 1.599\times 10^{12}$
. It is
$$ \begin{align*} 1\,599\,633\,425\,791\mapsto 3\,416\,404\,591\,999 & \mapsto 7\,296\,559\,416\,703 \\ & \mapsto15\,583\,569\,769\,855. \end{align*} $$
