Open AccessArticle

An E-Sequence Approach to the 3x + 1 Problem

Sanmin Wang

Faculty of Science, Zhejiang Sci-Tech University, Hangzhou 310018, China

Symmetry 2019, 11(11), 1415; https://doi.org/10.3390/sym11111415

Submission received: 17 October 2019 / Revised: 6 November 2019 / Accepted: 12 November 2019 / Published: 15 November 2019

(This article belongs to the Special Issue Symmetry and Dynamical Systems)

Download Versions Notes

Abstract

For any odd positive integer x, define

{(x_{n})}_{n ⩾ 0}

and

{(a_{n})}_{n ⩾ 1}

by setting

x_{0} = x, x_{n} = \frac{3 x_{n - 1} + 1}{2^{a_{n}}}

such that all

x_{n}

are odd. The

3 x + 1

problem asserts that there is an

x_{n} = 1

for all x. Usually,

{(x_{n})}_{n ⩾ 0}

is called the trajectory of x. In this paper, we concentrate on

{(a_{n})}_{n ⩾ 1}

and call it the E-sequence of x. The idea is that we generalize E-sequences to all infinite sequences

{(a_{n})}_{n ⩾ 1}

of positive integers and consider all these generalized E-sequences. We then define

{(a_{n})}_{n ⩾ 1}

to be

Ω

-convergent to x if it is the E-sequence of x and to be

Ω

-divergent if it is not the E-sequence of any odd positive integer. We prove a remarkable fact that the

Ω

-divergence of all non-periodic E-sequences implies the periodicity of

{(x_{n})}_{n ⩾ 0}

for all

x_{0}

. The principal results of this paper are to prove the

Ω

-divergence of several classes of non-periodic E-sequences. Especially, we prove that all non-periodic E-sequences

{(a_{n})}_{n ⩾ 1}

with

\underset{n \to \infty}{lim^{¯}} \frac{b_{n}}{n} > {log}_{2} 3

are

Ω

-divergent by using Wendel’s inequality and the Matthews and Watts’ formula

x_{n} = \frac{3^{n} x_{0}}{2^{b_{n}}} \prod_{k = 0}^{n - 1} (1 + \frac{1}{3 x_{k}})

, where

b_{n} = \sum_{k = 1}^{n} a_{k}

. These results present a possible way to prove the periodicity of trajectories of all positive integers in the

3 x + 1

problem, and we call it the E-sequence approach.

Keywords:

3x + 1 problem; E-sequence approach; Ω-divergence of non-periodic E-sequences; Wendel’s inequality

MSC:

11A99; 11B83

1. Introduction

For any odd positive integer x, define two infinite sequences

{(x_{n})}_{n ⩾ 0}

and

{(a_{n})}_{n ⩾ 1}

of positive integers by setting:

x_{0} = x, x_{n} = \frac{3 x_{n - 1} + 1}{2^{a_{n}}}

(1)

such that

x_{n}

is odd for all

n \in N = {1, 2, \dots}

. The

3 x + 1

problem asserts that there is

n \in N

such that

x_{n} = 1

for all odd positive integers x. For a survey, see [1]. For recent developments, see [2,3,4,5,6,7].

Usually,

{(x_{n})}_{n ⩾ 0}

is called the trajectory of x. In this paper, we concentrate on

{(a_{n})}_{n ⩾ 1}

and call it the E-sequence of x. The idea is that we generalize E-sequences to all infinite sequences

{(a_{n})}_{n ⩾ 1}

of positive integers. Given any generalized E-sequence

{(a_{n})}_{n ⩾ 1}

, if it is the E-sequence of the odd positive integer x, it is called

Ω

-convergent to x and denoted by

Ω - lim a_{n} = x

; if

{(a_{n})}_{n ⩾ 1}

is not the E-sequence of any odd positive integer, it is called

Ω

-divergent and denoted by

Ω - lim a_{n} = \infty

. Subsequently, these generalized E-sequences are also called E-sequences for simplicity.

The

3 x + 1

problem in the form (1.1) should be owed to Crandall and Sander et al., see [8,9]. E-sequences are some variants of Everett’s parity sequences [10] and Terras’ encoding representations [11]. Everett and Terras focused on finite E-sequences resulting from (1.1). What we are concerned with is the

Ω

-convergence and

Ω

-divergence of any infinite sequence of positive integers, i.e., the generalized E-sequences.

A possible way to prove the

3 x + 1

problem was devised by Möller as follows (see [12]):

Conjecture 1.

(i)

{(x_{n})}_{n ⩾ 0}

is periodic for all odd positive integers

x_{0}

;

(ii)

(1, 1, \dots)

is the unique pure periodic trajectory.

Usually, we can convert one claim about trajectories into the one about E-sequences. As for E-sequences, we have the following conjecture.

Conjecture 2.

Let

b_{n} = \sum_{i = 1}^{n} a_{i}

. Then,

(i) all non-periodic E-sequences are

Ω

-divergent;

(ii) every E-sequence

{(a_{n})}_{n ⩾ 1}

satisfying

3^{n} > 2^{b_{n}}

for all

n \in N

Ω

-divergent.

Note that Conjecture 2(i) does not hold for some generalizations of the

3 x + 1

problem studied by Möller, Matthews, and Watts in [12,13]; Conjecture 2(ii) implies that there is some n such that

2^{b_{n}} > 3^{n}

in the E-sequence

{(a_{n})}_{n ⩾ 1}

of every odd positive integer x, which is a conjecture posed by Terras in [11] about his

τ

-stopping time.

A remarkable fact is that Conjecture 1(i) is a corollary of Conjecture 2(i) by Theorem 3. This means that the

Ω

-divergence of all non-periodic E-sequences implies the periodicity of

{(x_{n})}_{n ⩾ 1}

for all positive integers x. Then, Conjecture 2(i) is of significance to the study of the

3 x + 1

problem. The principal results of this paper are to prove that several classes of non-periodic E-sequences are

Ω

-divergent. In particular, we prove that:

(i): All non-periodic E-sequences ${(a_{n})}_{n ⩾ 1}$ with $\underset{n \to \infty}{lim^{¯}} \frac{b_{n}}{n} > {log}_{2} 3$ are $Ω$ -divergent.
(ii): If ${(a_{n})}_{n ⩾ 0}$ is $12121112 \dots$ , where $a_{n} = 2$ if $n \in {2^{1}, 2^{2}, 2^{3}, \dots}$ and $a_{n} = 1$ , otherwise, then $Ω - lim a_{n} = \infty$ ;
(iii): Let $θ ⩾ 1$ be an irrational number, and define $a_{n} = [n θ] - [(n - 1) θ]$ , then $Ω - lim a_{n} = \infty$ , where $[a]$ denotes the integral part of a for any real a.

Note that we prove the above claim (i) by using Wendel’s inequality and the Matthews and Watts’ formula

x_{n} = \frac{3^{n} x_{0}}{2^{b_{n}}} \prod_{k = 0}^{n - 1} (1 + \frac{1}{3 x_{k}})

. In addition, it seems that our approach cannot help to prove the conjecture 1(ii) of the unique cycle. For such a topic, see [14].

2. Preliminaries

Let

{(a_{n})}_{n ⩾ 1}

be an E-sequence. In most cases, there is no odd positive integer x such that

{(a_{n})}_{n ⩾ 1}

is the E-sequence of x, i.e.,

Ω - lim a_{n} = \infty

. However, there always exists

x \in N

such that the first n terms of the E-sequence of x are

(a_{1} \dots a_{n})

. Furthermore, for any

1 ⩽ u ⩽ v ⩽ n

, there always exists

x \in N

such that the first

v - u + 1

terms of the E-sequence of x are the designated block

(a_{u} \dots a_{v})

(a_{1} \dots a_{n})

, which is illustrated as

(a_{1} \dots a_{u - 1}) (a_{u} \dots a_{v}) (a_{v + 1} \dots a_{n})

Definition 1.

Define

b_{0} = 0

b_{n} = \sum_{i = 1}^{n} a_{i}, B_{n} = \sum_{i = 0}^{n - 1} 3^{n - 1 - i} 2^{b_{i}}

Clearly,

B_{1} = 1

B_{n} = 3 B_{n - 1} + 2^{b_{n - 1}}

2 ∤ B_{n}

3 ∤ B_{n}

Proposition 1.

Let

{(x_{n})}_{n ⩾ 1}

and

{(a_{n})}_{n ⩾ 1}

be defined as in (1.1). Then

x_{n} = \frac{3^{n} x + B_{n}}{2^{b_{n}}}

Proof.

The proof is by a procedure similar to that of Theorem 1.1 in [11] and omitted. □

Proposition 2.

Given any positive integer n, there exist two integers

x_{n}

and

x_{0}

such that

2^{b_{n}} x_{n} - 3^{n} x_{0} = B_{n}

1 ⩽ x_{n} < 3^{n}

, and

1 ⩽ x_{0} < 2^{b_{n}}

Proof.

gcd (2^{b_{n}}, 3^{n}) = 1

, there exist two integers

x_{n}

and

x_{0}

such that

2^{b_{n}} x_{n} - 3^{n} x_{0} = B_{n}

and

1 ⩽ x_{n} ⩽ 3^{n}

. Then,

x_{n} < 3^{n}

3 ∤ B_{n}

. By

B_{n} ⩾ 1

, we have

x_{0} = \frac{2^{b_{n}} x_{n} - B_{n}}{3^{n}} < \frac{2^{b_{n}} x_{n}}{3^{n}} < 2^{b_{n}}

. Thus,

x_{0} < 2^{b_{n}}

2^{b_{n}} x_{n} - 3^{n} x_{0} = B_{n}

, we have

2^{b_{n}} x_{n} \equiv B_{n} (mod 3^{n})

. Then

2^{b_{n - 1}} (2^{a_{n}} x_{n} - 1) \equiv 3 B_{n - 1} (mod 3^{n})

B_{n} = 2^{b_{n - 1}} + 3 B_{n - 1}

. Thus,

3 | 2^{a_{n}} x_{n} - 1

. Define

x_{n - 1} = \frac{2^{a_{n}} x_{n} - 1}{3}

. Then,

x_{n - 1} \in Z

x_{n} = \frac{3 x_{n - 1} + 1}{2^{a_{n}}}

and

2^{b_{n - 1}} x_{n - 1} \equiv B_{n - 1} (mod 3^{n - 1})

. Sequentially, define

x_{n - 2}, \dots, x_{1}

such that

x_{n - 1} = \frac{3 x_{n - 2} + 1}{2^{a_{n - 1}}}

, …,

x_{1} = \frac{3 x_{0} + 1}{2^{a_{1}}}

. Then,

x_{i} \in Z

for all

0 ⩽ i ⩽ n

Suppose that

x_{0} < 0

. We then sequentially have

x_{1} < 0, \dots, x_{n} < 0

, which contradicts

x_{n} ⩾ 1

. Thus,

x_{0} ⩾ 1

. □

Note that the validity of Proposition 2 is dependent on the structure of

B_{n}

. We formulate the middle part of the above proof as the following proposition.

Proposition 3.

Assume that

x_{n}, x_{0} \in Z

and

2^{b_{n}} x_{n} - 3^{n} x_{0} = B_{n}

. Define

x_{1} = \frac{3 x_{0} + 1}{2^{a_{1}}}

,…,

x_{n - 1} = \frac{3 x_{n - 2} + 1}{2^{a_{n - 1}}}

. Then,

x_{n} = \frac{3 x_{n - 1} + 1}{2^{a_{n}}}

and

x_{i} \in Z

for all

0 ⩽ i ⩽ n

Definition 2.

For any

1 ⩽ u ⩽ v

, define

b_{u}^{u - 1} = 0

b_{u}^{v} = \sum_{i = u}^{v} a_{i}

B_{u}^{u - 2} = 0

B_{u}^{u - 1} = 1

B_{u}^{v} = 3^{v - u + 1} + 3^{v - u} 2^{b_{u}^{u}} + \dots + 3^{1} 2^{b_{u}^{v - 1}} + 2^{b_{u}^{v}} = \sum_{i = 0}^{v - u + 1} 3^{v - u + 1 - i} 2^{b_{u}^{u - 1 + i}}

Then,

b_{u}^{u} = a_{u}

b_{u}^{u + 1} = a_{u} + a_{u + 1}

B_{u}^{u} = 3 + 2^{a_{u}}

B_{u}^{u + 1} = 3^{2} + 3 \cdot 2^{a_{u}} + 2^{a_{u} + a_{u + 1}}

B_{u}^{v} = 3 B_{u}^{v - 1} + 2^{b_{u}^{v}} = \sum_{i = u - 1}^{v} 3^{v - i} 2^{b_{u}^{i}}

. Clearly,

b_{1}^{n}

and

B_{1}^{n - 1}

are the same as

b_{n}

and

B_{n}

, respectively.

Proposition 4.

B_{n} = 3^{n - u + 1} B_{1}^{u - 2} + 3^{n - 1 - v} 2^{b_{u - 1}} B_{u}^{v} + 2^{b_{v + 1}} B_{v + 2}^{n - 1} .

Proof.

B_{1}^{u - 2} = \sum_{i = 0}^{u - 2} 3^{u - 2 - i} 2^{b_{i}}

and

B_{v + 2}^{n - 1} = \sum_{i = v + 1}^{n - 1} 3^{n - 1 - i} 2^{b_{v + 2}^{i}}

, we have:

\begin{matrix} B_{n} & = B_{1}^{n - 1} = \sum_{i = 0}^{n - 1} 3^{n - 1 - i} 2^{b_{i}} = \sum_{i = 0}^{u - 2} 3^{n - 1 - i} 2^{b_{i}} + \sum_{i = u - 1}^{v} 3^{n - 1 - i} 2^{b_{i}} + \sum_{i = v + 1}^{n - 1} 3^{n - 1 - i} 2^{b_{i}} \\ = 3^{n - u + 1} \sum_{i = 0}^{u - 2} 3^{u - 2 - i} 2^{b_{i}} + 3^{n - 1 - v} 2^{b_{u - 1}} \sum_{i = u - 1}^{v} 3^{v - i} 2^{b_{u}^{i}} + 2^{b_{v + 1}} \sum_{i = v + 1}^{n - 1} 3^{n - 1 - i} 2^{b_{v + 2}^{i}} \\ = 3^{n - u + 1} B_{1}^{u - 2} + 3^{n - 1 - v} 2^{b_{u - 1}} B_{u}^{v} + 2^{b_{v + 1}} B_{v + 2}^{n - 1} . \end{matrix}

□

Definition 3.

For any

1 ⩽ u ⩽ v

, define two integers

x_{0}^{u, v}

and

x_{v - u + 1}^{u, v}

such that

2^{b_{u}^{v}} x_{v - u + 1}^{u, v} - 3^{v - u + 1} x_{0}^{u, v} = B_{u}^{v - 1}

1 ⩽ x_{0}^{u, v} < 2^{b_{u}^{v}}

, and

1 ⩽ x_{v - u + 1}^{u, v} < 3^{v - u + 1}

. Further, define

x_{1}^{u, v} = \frac{3 x_{0}^{u, v} + 1}{2^{a_{u}}}

x_{2}^{u, v} = \frac{3 x_{1}^{u, v} + 1}{2^{a_{u + 1}}}

,…,

x_{v - u}^{u, v} = \frac{3 x_{v - u - 1}^{u, v} + 1}{2^{a_{v - 1}}}

Clearly,

x_{0}^{1, n}

and

x_{n}^{1, n}

are the same as

x_{0}

and

x_{n}

in Proposition 2, respectively.

Proposition 5.

(i): $x_{v - u + 1}^{u, v} = \frac{3 x_{v - u}^{u, v} + 1}{2^{a_{v}}};$
(ii): For any $0 ⩽ k ⩽ v - u$ , $x_{k}^{u, v} = \frac{3^{k} x_{0}^{u, v} + B_{u}^{u + k - 2}}{2^{b_{u}^{u + k - 1}}}$ , and
$x_{v - u + 1}^{u, v} = \frac{3^{v - u + 1 - k} x_{k}^{u, v} + B_{u + k}^{v - 1}}{2^{b_{u + k}^{v}}}$ ;
(iii): $x_{0}^{u, v} ⩽ x_{0}^{u, v + 1}$ ;
(iv): $Ω - lim a_{n} = x$ if and only if ${lim}_{n \to \infty} x_{0}^{1, n} = x$ ;
(v): $Ω - lim a_{n} = \infty$ if and only if ${lim}_{n \to \infty} x_{0}^{1, n} = \infty$ .

Proof.

(i) is from Proposition 3(ii), which is from (i) and Proposition 1.

(iii) By Definition 3,

2^{b_{u}^{v}} x_{v - u + 1}^{u, v} - 3^{v - u + 1} x_{0}^{u, v} = B_{u}^{v - 1}

2^{b_{u}^{v + 1}} x_{v - u + 2}^{u, v + 1} - 3^{v - u + 2} x_{0}^{u, v + 1} = B_{u}^{v}

. Then,

3^{v - u + 1} x_{0}^{u, v} + B_{u}^{v - 1} \equiv 0 (mod 2^{b_{u}^{v}})

3^{v - u + 2} x_{0}^{u, v + 1} + B_{u}^{v} \equiv 0 (mod 2^{b_{u}^{v + 1}})

. Thus,

3^{v - u + 1} x_{0}^{u, v + 1} + B_{u}^{v - 1} \equiv 0 (mod 2^{b_{u}^{v}})

B_{u}^{v} = 3 B_{u}^{v - 1} + 2^{b_{u}^{v}}

. Hence,

x_{0}^{u, v} \equiv x_{0}^{u, v + 1} (mod 2^{b_{u}^{v}})

. Therefore,

x_{0}^{u, v} ⩽ x_{0}^{u, v + 1}

1 ⩽ x_{0}^{u, v} < 2^{b_{u}^{v}}

and

1 ⩽ x_{0}^{u, v + 1} < 2^{b_{u}^{v + 1}}

By (iii),

{(x_{0}^{1, n})}_{n ⩾ 1}

is increasing, then (iv) and (v) hold trivially. □

Proposition 5(iv) shows that if

Ω - lim a_{n} = x

, then

x_{0}^{1, n} = x

for all sufficiently large n. Proposition 5(v) shows the reasonableness of

Ω - lim a_{n} = \infty

3. Periodic E-Sequences

Definition 4.

(i): ${(a_{n})}_{n ⩾ 1}$ is periodic if there exist two integers
$l ⩾ 0$ , $r ⩾ 1$ such that $a_{n} = a_{n + r}$ for all $n > l$ ;
(ii): r is called the period of ${(a_{n})}_{n ⩾ 1}$ ;
(iii): $(a_{1} \dots a_{l})$ and $(a_{l + 1} \dots a_{l + r} \dots)$ are called the non-periodic part and periodic part of ${(a_{n})}_{n ⩾ 1}$ , respectively;
(iv): ${(a_{n})}_{n ⩾ 1}$ is called purely periodic if $l = 0$ and eventually periodic if $l > 0$ ;
(v): The E-sequence is denoted by $a_{1} \dots a_{l} \bar{a_{l + 1} \dots a_{l + r}}$ .

Throughout the remainder of this section, define

s = b_{l + 1}^{l + r}

B_{r} = B_{l + 1}^{l + r - 1}

, and let

k ⩾ 0

be an integer.

Proposition 6.

Let

a_{1} \dots a_{l} \bar{a_{l + 1} \dots a_{l + r}}

be a periodic E-sequence. Then,

B_{r k + l} = 3^{r k} B_{l} + 2^{b_{l}} B_{r} \frac{3^{r k} - 2^{s k}}{3^{r} - 2^{s}}

Proof.

By Proposition 4,

B_{r k + l} = B_{1}^{r k + l - 1} = 3^{r k} B_{1}^{l - 1} + 3^{r k - r} 2^{b_{l}} B_{l + 1}^{l + r - 1} +

3^{r k - 2 r} 2^{b_{l + r}} B_{l + r + 1}^{l + 2 r - 1} + \dots + 2^{b_{l + r k - r}} B_{l + 1 + r (k - 1)}^{l + r k - 1} .

b_{l + r} = b_{l} + s, b_{l + 2 r} = b_{l} + 2 s, \dots,

b_{l + r k - r} = b_{l} + (k - 1) s, B_{1}^{l - 1} = B_{l}, B_{l + r + 1}^{l + 2 r - 1} = \dots = B_{l + 1 + r (k - 1)}^{l + r k - 1} = B_{r}

, we have:

\begin{matrix} B_{r k + l} & = 3^{r k} B_{l} + 3^{r k - r} 2^{b_{l}} B_{r} + 3^{r k - 2 r} 2^{b_{l}} 2^{s} B_{r} + \dots + 2^{b_{l}} 2^{(k - 1) s} B_{r} \\ = 3^{r k} B_{l} + 2^{b_{l}} B_{r} (3^{r k - r} 2^{0} + 3^{r k - 2 r} 2^{s} + \dots + 3^{0} 2^{(k - 1) s}) \\ = 3^{r k} B_{l} + 2^{b_{l}} B_{r} \frac{3^{r k} - 2^{s k}}{3^{r} - 2^{s}} . \end{matrix}

□

Proposition 7.

Let

a_{1} \dots a_{l} \bar{a_{l + 1} \dots a_{l + r}}

be a periodic E-sequence. By Proposition 2, define two integers

x_{0}

and

x_{r k + l}

such that

2^{s k + b_{l}} x_{r k + l} - 3^{r k + l} x_{0} = B_{r k + l}

1 ⩽ x_{0} < 2^{s k + b_{l}}

and

1 ⩽ x_{r k + l} < 3^{r k + l}

. Then, there is a constant

K \in N

, depending on

a_{1}, \dots, a_{l + r}

such that when

k > K

and,

(i): if $2^{s} > 3^{r}$ , there is $u_{r k + l} \in Z$ , $0 ⩽ u_{r k + l} < (2^{s} - 3^{r}) 3^{l}$ such that
$x_{0} = \frac{2^{s k + b_{l}} u_{r k + l} - B_{l} (2^{s} - 3^{r}) + 2^{b_{l}} B_{r}}{(2^{s} - 3^{r}) 3^{l}}$ , $x_{r k + l} = \frac{3^{r k} u_{r k + l} + B_{r}}{2^{s} - 3^{r}}$ ;
(ii): if $3^{r} > 2^{s}$ , there is $u_{r k + l} \in N$ , $1 ⩽ u_{r k + l} ⩽ (3^{r} - 2^{s}) 3^{l}$ such that
$x_{0} = \frac{2^{s k + b_{l}} u_{r k + l} - B_{l} (3^{r} - 2^{s}) - 2^{b_{l}} B_{r}}{(3^{r} - 2^{s}) 3^{l}}$ , $x_{r k + l} = \frac{3^{r k} u_{r k + l} - B_{r}}{3^{r} - 2^{s}}$ .

Proof.

(i): $2^{s} > 3^{r}$ . By $x_{r k + l} = \frac{3^{r k + l} x_{0} + B_{r k + l}}{2^{s k + b_{l}}}$ , we have $2^{s k + b_{l}} x_{r k + l} \equiv B_{r k + l} (m o d 3^{r k + l})$ . Then, $2^{s k + b_{l}} x_{r k + l} \equiv 3^{r k} B_{l} + 2^{b_{l}} B_{r} \frac{2^{s k} - 3^{r k}}{2^{s} - 3^{r}} (m o d 3^{r k + l})$ by Proposition 6. Thus, $(2^{s} - 3^{r}) 2^{s k + b_{l}} x_{r k + l} \equiv (2^{s} - 3^{r}) 3^{r k} B_{l} + (2^{s k} - 3^{r k}) 2^{b_{l}} B_{r} (m o d (2^{s} - 3^{r}) 3^{r k + l})$ . Hence, $2^{s k + b_{l}} ((2^{s} - 3^{r}) x_{r k + l} - B_{r}) \equiv 3^{r k} ((2^{s} - 3^{r}) B_{l} - 2^{b_{l}} B_{r}) (m o d (2^{s} - 3^{r}) 3^{r k + l}) .$ Define $u_{r k + l} = \frac{(2^{s} - 3^{r}) x_{r k + l} - B_{r}}{3^{r k}}$ . Then, $u_{r k + l} \in Z$ and $2^{s k + b_{l}} u_{r k + l} \equiv (2^{s} - 3^{r}) B_{l} - 2^{b_{l}} B_{r} (m o d (2^{s} - 3^{r}) 3^{l})$ . Hence $x_{r k + l} = \frac{3^{r k} u_{r k + l} + B_{r}}{2^{s} - 3^{r}}$ and:

$\begin{matrix} x_{0} & = \frac{2^{s k + b_{l}} x_{r k + l} - B_{r k + l}}{3^{r k + l}} \\ = \frac{2^{s k + b_{l}} \frac{3^{r k} u_{r k + l} + B_{r}}{2^{s} - 3^{r}} - 3^{r k} B_{l} - 2^{b_{l}} B_{r} \frac{2^{s k} - 3^{r k}}{2^{s} - 3^{r}}}{3^{r k + l}} \\ = \frac{3^{r k} 2^{s k + b_{l}} u_{r k + l} + 2^{s k + b_{l}} B_{r} - 3^{r k} B_{l} (2^{s} - 3^{r}) + 3^{r k} 2^{b_{l}} B_{r} - 2^{s k + b_{l}} B_{r}}{(2^{s} - 3^{r}) 3^{r k + l}} \\ = \frac{2^{s k + b_{l}} u_{r k + l} - B_{l} (2^{s} - 3^{r}) + 2^{b_{l}} B_{r}}{(2^{s} - 3^{r}) 3^{l}} . \end{matrix}$

By $x_{r k + l} = \frac{3^{r k} u_{r k + l} + B_{r}}{2^{s} - 3^{r}} < 3^{r k + l}$ , we have $u_{r k + l} < \frac{3^{r k + l} (2^{s} - 3^{r}) - B_{r}}{3^{r k}} = 3^{l} (2^{s} - 3^{r}) - \frac{B_{r}}{3^{r k}} < 3^{l} (2^{s} - 3^{r})$ . By $x_{r k + l} = \frac{3^{r k} u_{r k + l} + B_{r}}{2^{s} - 3^{r}} > 0$ , we have $u_{r k + l} > - \frac{B_{r}}{3^{r k}}$ . Since ${lim}_{k \to \infty} - \frac{B_{r}}{3^{r k}} = 0$ and $u_{r k + l} \in Z$ , there is a constant $K \in N$ , depending on $a_{1}, \dots, a_{l + r}$ such that $u_{r k + l} ⩾ 0$ when $k > K$ .
(ii): $3^{r} > 2^{s}$ . By $x_{r k + l} = \frac{3^{r k + l} x_{0} + B_{r k + l}}{2^{s k + b_{l}}}$ , we have:

$2^{s k + b_{l}} ((3^{r} - 2^{s}) x_{r k + l} + B_{r}) \equiv 3^{r k} ((3^{r} - 2^{s}) B_{l} + 2^{b_{l}} B_{r}) (m o d (3^{r} - 2^{s}) 3^{r k + l}) .$

Define $u_{r k + l} = \frac{(3^{r} - 2^{s}) x_{r k + l} + B_{r}}{3^{r k}}$ . Then:

$u_{r k + l} \in Z, 2^{s k + b_{l}} u_{r k + l} \equiv (3^{r} - 2^{s}) B_{l} + 2^{b_{l}} B_{r} (m o d (3^{r} - 2^{s}) 3^{l}) .$

Thus, $x_{r k + l} = \frac{3^{r k} u_{r k + l} - B_{r}}{3^{r} - 2^{s}}$ , $x_{0} = \frac{2^{s k + b_{l}} u_{r k + l} - B_{l} (3^{r} - 2^{s}) - 2^{b_{l}} B_{r}}{(3^{r} - 2^{s}) 3^{l}}$ . Since $x_{r k + l} = \frac{3^{r k} u_{r k + l} - B_{r}}{3^{r} - 2^{s}} > 0$ , then $u_{r k + l} > \frac{B_{r}}{3^{r k}}$ , and thus, $1 ⩽ u_{r k + l}$ .
By $x_{0} = \frac{2^{s k + b_{l}} u_{r k + l} - B_{l} (3^{r} - 2^{s}) - 2^{b_{l}} B_{r}}{(3^{r} - 2^{s}) 3^{l}} < 2^{s k + b_{l}}$ , we have $u_{r k + l} < (3^{r} - 2^{s}) 3^{l} + \frac{B_{l} (3^{r} - 2^{s}) + 2^{b_{l}} B_{r}}{2^{s k + b_{l}}}$ . Since ${lim}_{k \to \infty} \frac{B_{l} (3^{r} - 2^{s}) + 2^{b_{l}} B_{r}}{2^{s k + b_{l}}} = 0$ and $u_{r k + l} \in Z$ , there is a $K \in N$ such that $u_{r k + l} ⩽ (3^{r} - 2^{s}) 3^{l}$ when $k > K$ .

□

Theorem 1.

3^{r} > 2^{s}

, then

a_{1} \dots a_{l} \bar{a_{l + 1} a_{l + 2} \dots a_{l + r - 1} a_{l + r}}

is Ω-divergent.

Proof.

By Proposition 7(ii),

x_{0} = \frac{2^{s k + b_{l}} u_{r k + l} - B_{l} (3^{r} - 2^{s}) - 2^{b_{l}} B_{r}}{(3^{r} - 2^{s}) 3^{l}}

and

u_{r k + l} ⩾ 1

. Then,

x_{0} \to + \infty

k \to \infty .

Thus, the E-sequence is

Ω

-divergent. □

Theorem 2.

a_{1} \dots a_{l} \bar{a_{l + 1} a_{l + 2} \dots a_{l + r - 1} a_{l + r}}

is Ω-convergent to x, then

{(x_{n})}_{n ⩾ 0}

is periodic.

Proof.

By Theorem 1,

2^{s} > 3^{r}

. By Proposition 7(i),

x_{0} = \frac{2^{s k + b_{l}} u_{r k + l} - B_{l} (2^{s} - 3^{r}) + 2^{b_{l}} B_{r}}{(2^{s} - 3^{r}) 3^{l}}

and

u_{r k + l} ⩾ 0

for all

k > K

. Since

x_{0} = x < \infty

for all sufficiently large k, by Proposition 5(iv), then

u_{r k + l} = 0

. Thus,

x_{0} = \frac{2^{b_{l}} B_{r} - B_{l} (2^{s} - 3^{r})}{(2^{s} - 3^{r}) 3^{l}}

and

x_{r k + l} = \frac{B_{r}}{2^{s} - 3^{r}}

for all

k \geq 0

. Hence,

{(x_{n})}_{n ⩾ 0}

is periodic, and its non-periodic part and periodic part are

(x_{0} x_{1} \dots x_{l})

and

\bar{x_{l + 1} \dots x_{l + r}}

, respectively. □

Theorem 3.

Assume that all non-periodic E-sequence are Ω-divergent. Then, the trajectory of every odd positive integer is periodic.

Proof.

Suppose that x is an odd positive integer,

{(x_{n})}_{n ⩾ 0}

and

{(a_{n})}_{n ⩾ 1}

are its trajectory and E-sequence, respectively. Then,

Ω - lim a_{n} = x

. Thus,

{(a_{n})}_{n ⩾ 1}

is periodic by the assumption. Hence,

{(x_{n})}_{n ⩾ 0}

is periodic by Theorem 2. □

4. Non-Periodic E-Sequences

For any real number

α

{α}

denotes its fractional part. The following lemma is due to Matthews and Watts (see Lemma 2(b) in [13]). We present its proof for the reader’s convenience.

Lemma 1.

Let

{(a_{n})}_{n ⩾ 1}

be an E-sequence such that

Ω - lim a_{n} = x_{0}

and

{(x_{n})}_{n ⩾ 0}

is unbounded. Then,

\underset{n \to \infty}{lim^{¯}} \frac{b_{n}}{n} ⩽ {log}_{2} 3

Proof.

From

x_{k} = \frac{3 x_{k - 1} + 1}{2^{a_{k}}}

, we have

2^{a_{k}} = \frac{3 x_{k - 1} + 1}{x_{k}}

. Then:

2^{b_{n}} = \prod_{k = 1}^{n} 2^{a_{k}} = \prod_{k = 1}^{n} \frac{3 x_{k - 1} + 1}{x_{k}} = \frac{x_{0}}{x_{n}} \prod_{k = 1}^{n} \frac{3 x_{k - 1} + 1}{x_{k - 1}} = \frac{3^{n} x_{0}}{x_{n}} \prod_{k = 1}^{n} (1 + \frac{1}{3 x_{k - 1}}) .

Thus:

x_{n} = \frac{3^{n} x_{0}}{2^{b_{n}}} \prod_{k = 1}^{n} (1 + \frac{1}{3 x_{k - 1}})

which we call the Matthews and Watts’ formula (see Lemma 1(b) in [13]).

Since

{(x_{n})}_{n ⩾ 1}

is unbounded, all

x_{n}

are distinct. Then:

1 ⩽ x_{n} ⩽ \frac{3^{n} x_{0}}{2^{b_{n}}} \prod_{k = 1}^{n} (1 + \frac{1}{3 k}) .

Thus:

0 ⩽ log \frac{3^{n}}{2^{b_{n}}} + log x_{0} + \sum_{k = 1}^{n} log (1 + \frac{1}{3 k}) ⩽ log 3^{n} - log 2^{b_{n}} + log x_{0} + \sum_{k = 1}^{n} \frac{1}{3 k} .

Hence:

log 2^{b_{n}} ⩽ log 3^{n} + log x_{0} + \frac{1}{3} \sum_{k = 1}^{n} \frac{1}{k} .

Therefore:

\frac{b_{n}}{n} ⩽ {log}_{2} 3 + \frac{{log}_{2} x_{0}}{n} + \frac{1}{n log 8} \sum_{k = 1}^{n} \frac{1}{k} .

Then:

\underset{n \to \infty}{lim^{¯}} \frac{b_{n}}{n} ⩽ {log}_{2} 3 .

□

Theorem 4.

Let

{(a_{n})}_{n ⩾ 1}

be a non-periodic E-sequence such that

\underset{n \to \infty}{lim^{¯}} \frac{b_{n}}{n} > {log}_{2} 3

. Then,

Ω - lim a_{n} = \infty .

Proof.

Suppose that

Ω - lim a_{n} = x_{0}

for some positive integer

x_{0}

. It follows from Lemma 1 and

\underset{n \to \infty}{lim^{¯}} \frac{b_{n}}{n} > {log}_{2} 3

that

{(x_{n})}_{n ⩾ 0}

is bounded. Then,

{(x_{n})}_{n ⩾ 0}

is periodic. Thus,

{(a_{n})}_{n ⩾ 1}

is periodic, which contradicts the non-periodicity of

{(a_{n})}_{n ⩾ 1}

. Hence,

Ω - lim a_{n} = \infty

. □

The following lemma is the well known Wendel’s inequality (see [15]). Lemma 3 is a consequence of an easy calculation.

Lemma 2.

Let x be a positive real number, and let

s \in (0, 1)

. Then,

\frac{Γ (x + s)}{Γ (x)} ⩽ x^{s}

Lemma 3.

Let a and b be two integers with

a ⩾ 1

and

a ∤ b

. Then,

\prod_{k = 0}^{n} (1 + \frac{z}{a k + b}) = \frac{Γ (\frac{b}{a}) Γ (\frac{b + z}{a} + n + 1)}{Γ (\frac{b + z}{a}) Γ (\frac{b}{a} + n + 1)}

Lemma 4.

\prod_{1 ⩽ k < 3 n, k \equiv 1, 5 (mod 6)} (1 + \frac{1}{3 k}) < 1.5 n^{\frac{1}{9}}

for all

n ⩾ 1

Proof.

Let

2 | n

. Then:

\prod_{k = 0}^{\frac{n}{2} - 1} (1 + \frac{1}{3 (6 k + 1)}) = \frac{Γ (\frac{1}{6}) Γ (\frac{n}{2} + \frac{2}{9})}{Γ (\frac{2}{9}) Γ (\frac{n}{2} + \frac{1}{6})} ⩽ \frac{Γ (\frac{1}{6})}{Γ (\frac{2}{9})} {(\frac{n}{2} + \frac{1}{6})}^{\frac{1}{18}}

and:

\prod_{k = 0}^{\frac{n}{2} - 1} (1 + \frac{1}{3 (6 k + 5)}) = \frac{Γ (\frac{5}{6}) Γ (\frac{n}{2} + \frac{8}{9})}{Γ (\frac{8}{9}) Γ (\frac{n}{2} + \frac{5}{6})} ⩽ \frac{Γ (\frac{5}{6})}{Γ (\frac{8}{9})} {(\frac{n}{2} + \frac{5}{6})}^{\frac{1}{18}}

by Wendel’s inequality. Thus,

\begin{matrix} \prod_{1 ⩽ k < 3 n, k \equiv 1, 5 (mod 6)} & (1 + \frac{1}{3 k}) = \prod_{k = 0}^{\frac{n}{2} - 1} (1 + \frac{1}{3 (6 k + 1)}) \prod_{k = 0}^{\frac{n}{2} - 1} (1 + \frac{1}{3 (6 k + 5)}) ⩽ \\ \frac{Γ (\frac{1}{6}) Γ (\frac{5}{6})}{Γ (\frac{2}{9}) Γ (\frac{8}{9})} {(\frac{n}{2} + \frac{5}{6})}^{\frac{1}{18}} {(\frac{n}{2} + \frac{1}{6})}^{\frac{1}{18}} ⩽ 1.4196 {(\frac{n^{2}}{3})}^{\frac{1}{18}} < 1.5 n^{\frac{1}{9}} . \end{matrix}

Let

2 ∤ n

. Then:

\prod_{k = 0}^{\frac{n + 1}{2} - 1} (1 + \frac{1}{3 (6 k + 1)}) = \frac{Γ (\frac{1}{6}) Γ (\frac{n}{2} + \frac{13}{18})}{Γ (\frac{2}{9}) Γ (\frac{n}{2} + \frac{2}{3})} ⩽ \frac{Γ (\frac{1}{6})}{Γ (\frac{2}{9})} {(\frac{n}{2} + \frac{2}{3})}^{\frac{1}{18}}

and

\prod_{k = 0}^{\frac{n + 1}{2} - 2} (1 + \frac{1}{3 (6 k + 5)}) = \frac{Γ (\frac{5}{6}) Γ (\frac{n}{2} + \frac{7}{18})}{Γ (\frac{8}{9}) Γ (\frac{n}{2} + \frac{1}{3})} ⩽ \frac{Γ (\frac{5}{6})}{Γ (\frac{8}{9})} {(\frac{n}{2} + \frac{1}{3})}^{\frac{1}{18}}

by Wendel’s inequality. Thus,

\begin{matrix} \prod_{1 ⩽ k < 3 n, k \equiv 1, 5 (mod 6)} (1 + \frac{1}{3 k}) = & \prod_{k = 0}^{\frac{n + 1}{2} - 1} (1 + \frac{1}{3 (6 k + 1)}) \prod_{k = 0}^{\frac{n + 1}{2} - 2} (1 + \frac{1}{3 (6 k + 5)}) ⩽ \\ \frac{Γ (\frac{1}{6}) Γ (\frac{5}{6})}{Γ (\frac{2}{9}) Γ (\frac{8}{9})} {(\frac{n}{2} + \frac{2}{3})}^{\frac{1}{18}} {(\frac{n}{2} + \frac{1}{3})}^{\frac{1}{18}} < 1.5 n^{\frac{1}{9}} . \end{matrix}

□

Theorem 5.

Let

2^{b_{n}} x_{n} - 3^{n} x_{0} = B_{n}

such that

1 ⩽ x_{0} < 2^{b_{n}}, 1 ⩽ x_{n} < 3^{n}

3 ∤ x_{0}

, and

x_{0}, \dots, x_{n - 1}

are distinct integers. Then,

x_{0} > \frac{B_{n}}{3^{n} (1.5 n^{\frac{1}{9}} - 1)}

Proof.

From the Matthews and Watts’ formula and Lemma 4, we have:

\frac{2^{b_{n}} x_{n}}{3^{n} x_{0}} = \prod_{k = 1}^{n} (1 + \frac{1}{3 x_{k - 1}}) ⩽ \prod_{1 ⩽ k < 3 n, k \equiv 1, 5 (mod 6)} (1 + \frac{1}{3 k}) < 1.5 n^{\frac{1}{9}} .

Then,

\frac{3^{n} x_{0} + B_{n}}{3^{n} x_{0}} < 1.5 n^{\frac{1}{9}}

. Thus,

x_{0} > \frac{B_{n}}{3^{n} (1.5 n^{\frac{1}{9}} - 1)}

. □

Corollary 1.

Let

θ ⩾ {l o g}_{2} 3

be an irrational number. Define

a_{n} = [n θ] - [(n - 1) θ]

. Then,

Ω - lim a_{n} = \infty

Proof.

Let

θ = {l o g}_{2} 3

. Then,

\frac{B_{n}}{3^{n}} = \sum_{k = 1}^{n} \frac{2^{[(k - 1) {log}_{2} 3]}}{3^{k}} > \frac{n}{8}

\frac{2^{[(k - 1) {log}_{2} 3]}}{3^{k}} > \frac{1}{8}

. Thus,

\frac{B_{n}}{3^{n} (1.5 n^{\frac{1}{9}} - 1)} > \frac{n}{8 (1.5 n^{\frac{1}{9}} - 1)} \to \infty

, as

n \to \infty

. Hence,

Ω - lim a_{n} = \infty

by Theorem 5.

Let

θ > {log}_{2} 3

. Then,

lim_{n \to \infty} \frac{b_{n}}{n} = lim_{n \to \infty} \frac{[n θ]}{n} = θ > {log}_{2} 3

. Since

θ

is an irrational number,

{(a_{n})}_{n ⩾ 1}

is non-periodic. Thus,

Ω - lim a_{n} = \infty

by Theorem 4. □

Lemma 5.

Let x and n be two positive integers. Then, (i)

\prod_{k = 0}^{n - 1} (1 + \frac{1}{3 (x + k)}) \leq 1 + \frac{n}{3 x};

(ii)

\prod_{k = 0}^{n - 1} (1 + \frac{1}{3 (x - k)}) \geq 1 + \frac{n}{3 x}

for

x \geq n

; (iii)

\prod_{k = 0}^{n - 1} (1 + \frac{1}{3 (x - k)}) > \frac{3 x}{3 x - n}

for

x \geq n \geq 2

Proof.

(i) The proof is by induction on n. For the base step, let

n = 1

, then

\prod_{k = 0}^{n - 1} (1 + \frac{1}{3 (x + k)}) = 1 + \frac{1}{3 x} = 1 + \frac{n}{3 x}

. For the induction step, assume that

\prod_{k = 0}^{n - 1} (1 + \frac{1}{3 (x + k)}) \leq 1 + \frac{n}{3 x}

. Then,

\prod_{k = 0}^{n} (1 + \frac{1}{3 (x + k)}) \leq (1 + \frac{n}{3 x}) (1 + \frac{1}{3 (x + n)}) = 1 + \frac{n}{3 x} + \frac{1}{3 (x + n)} + \frac{n}{9 x (x + n)} \leq 1 + \frac{n + 1}{3 x} .

Thus, the inequality holds for all

n \geq 1

. The proof of (ii) is similar to that of (i) and omitted.

(iii) Let

n = 2

. Since

3 x \cdot 3 x - 2 \cdot 3 x - 3 x + 2 > 3 x \cdot 3 x - 3 \cdot 3 x

, then

\frac{3 x - 1}{3 x \cdot 3 (x - 1)} > \frac{1}{3 x - 2}

. Thus,

1 + \frac{1}{3 x} + \frac{1}{3 (x - 1)} + \frac{1}{3 x \cdot 3 (x - 1)} > \frac{3 x - 2 + 2}{3 x - 2} = 1 + \frac{2}{3 x - 2}

. Hence,

(1 + \frac{1}{3 x}) (1 + \frac{1}{3 (x - 1)}) > \frac{3 x}{3 x - 2}

. Therefore,

\prod_{k = 0}^{n - 1} (1 + \frac{1}{3 (x - k)}) > \frac{3 x}{3 x - n}

Assume that

\prod_{k = 0}^{n - 1} (1 + \frac{1}{3 (x - k)}) > \frac{3 x}{3 x - n}

. Since

(3 x - 3 n + 1) (3 x - n - 1) > (3 x - n) (3 x - 3 n)

, then

\frac{3 x (3 x - 3 n) + 3 x}{(3 x - n) (3 x - 3 n)} > \frac{3 x}{3 x - n - 1}

. Thus,

\prod_{k = 0}^{n} (1 + \frac{1}{3 (x - k)}) > \frac{3 x}{3 x - n} (1 + \frac{1}{3 (x - n)}) = \frac{3 x}{3 x - n} + \frac{3 x}{(3 x - n) (3 x - 3 n)} > \frac{3 x}{3 x - n - 1}

. □

Lemma 6.

Let

2^{b_{n}} x_{n} - 3^{n} x_{0} = B_{n}

such that

1 \leq x_{0} < 2^{b_{n}}

1 \leq x_{n} < 3^{n}

x_{i} \neq x_{j}

for all

0 \leq i < j \leq n - 1

. Then, (i)

\frac{B_{n}}{3^{n}} \leq \frac{n}{3}

x_{k} > x_{0}

for all

1 \leq k \leq n - 1

; (ii)

\frac{B_{n}}{2^{b_{n}}} < \frac{n}{3}

x_{n} < x_{k}

for all

0 \leq k \leq n - 1

; (iii)

\frac{B_{n}}{2^{b_{n}}} > \frac{n}{3}

x_{n} > x_{i}

for all

0 \leq i \leq n - 1

; (iv)

\frac{B_{n}}{3^{n}} \geq \frac{n}{3}

x_{0} > x_{k}

for all

1 \leq k \leq n

Proof.

(i) From

\frac{2^{b_{n}} x_{n}}{3^{n} x_{0}} = \prod_{k = 0}^{n - 1} (1 + \frac{1}{3 x_{k}})

, we have:

1 + \frac{B_{n}}{3^{n} x_{0}} = \prod_{k = 0}^{n - 1} (1 + \frac{1}{3 x_{k}}) \leq \prod_{k = 0}^{n - 1} (1 + \frac{1}{3 (x_{0} + k)}) .

Then,

1 + \frac{B_{n}}{3^{n} x_{0}} \leq 1 + \frac{n}{3 x_{0}}

by Lemma 5(i). Thus,

\frac{B_{n}}{3^{n}} \leq \frac{n}{3}

(ii) From

\frac{2^{b_{n}} x_{n}}{3^{n} x_{0}} = \prod_{k = 0}^{n - 1} (1 + \frac{1}{3 x_{k}})

, we have:

\frac{2^{b_{n}} x_{n} - B_{n}}{2^{b_{n}} x_{n}} = \prod_{k = 0}^{n - 1} (1 + \frac{1}{3 x_{k}})^{- 1} \geq \prod_{k = 0}^{n - 1} (1 + \frac{1}{3 (x_{n} + k)})^{- 1} .

Then,

1 - \frac{B_{n}}{2^{b_{n}} x_{n}} \geq \prod_{k = 0}^{n - 1} {(1 + \frac{1}{3 (x_{n} + k)})}^{- 1} \geq {(1 + \frac{n}{3 x_{n}})}^{- 1}

by Lemma 5(i). Thus:

\frac{B_{n}}{2^{b_{n}} x_{n}} \leq 1 - {(1 + \frac{n}{3 x_{n}})}^{- 1} = \frac{n}{3 x_{n} + n} .

Hence,

\frac{B_{n}}{2^{b_{n}}} \leq \frac{n x_{n}}{3 x_{n} + n} < \frac{n}{3}

(iii) Let

n = 1

. Then,

x_{1} = \frac{3 x + 1}{2^{a_{1}}} > x

. Thus,

(3 - 2^{a_{1}}) x + 1 > 0

. Hence,

a_{1} = 1

. Therefore,

\frac{B_{n}}{2^{b_{n}}} = \frac{B_{1}}{2^{b_{1}}} = \frac{1}{2} > \frac{1}{3} = \frac{n}{3}

Let

x_{n} \geq n \geq 2

. By Lemma 5(iii), we have

\frac{2^{b_{n}} x_{n}}{3^{n} x_{0}} = \prod_{k = 0}^{n - 1} (1 + \frac{1}{3 x_{k}}) \geq \prod_{k = 0}^{n - 1} (1 + \frac{1}{3 (x_{n} - k)}) > \frac{3 x_{n}}{3 x_{n} - n}

. Then,

\frac{2^{b_{n}} x_{n}}{2^{b_{n}} x_{n} - B_{n}} > \frac{3 x_{n}}{3 x_{n} - n}

. Thus,

\frac{2^{b_{n}} x_{n} - B_{n}}{2^{b_{n}} x_{n}} < \frac{3 x_{n} - n}{3 x_{n}}

. Hence,

\frac{B_{n}}{2^{b_{n}}} > \frac{n}{3} .

(iv) By Lemma 5(ii), we have:

1 + \frac{B_{n}}{3^{n} x_{0}} = \frac{2^{b_{n}} x_{n}}{3^{n} x_{0}} = \prod_{k = 0}^{n - 1} (1 + \frac{1}{3 x_{k}}) \geq \prod_{k = 0}^{n - 1} (1 + \frac{1}{3 (x_{0} - k)}) \geq 1 + \frac{n}{3 x_{0}} .

Then,

\frac{B_{n}}{3^{n}} \geq \frac{n}{3}

. □

A direct consequence of Lemma 6 is the following theorem, which may imply something unknown.

Theorem 6.

Let

2^{b_{n}} x_{n} - 3^{n} x_{0} = B_{n}

such that

1 \leq x_{0} < 2^{b_{n}}

1 \leq x_{n} < 3^{n}

x_{i} \neq x_{j}

for all

0 \leq i < j \leq n - 1

. Then:

(i)

\frac{B_{n}}{3^{n}} > \frac{n}{3}

implies

x_{k} \leq x_{0}

for some

1 \leq k \leq n - 1

;

(ii)

\frac{B_{n}}{3^{n}} < \frac{n}{3}

implies

x_{0} \leq x_{k}

for some

1 \leq k \leq n

;

(iii)

\frac{B_{n}}{2^{b_{n}}} \leq \frac{n}{3}

implies

x_{n} \leq x_{i}

for some

0 \leq i \leq n - 1

;

(iv)

\frac{B_{n}}{2^{b_{n}}} \geq \frac{n}{3}

implies

x_{n} \geq x_{k}

for some

0 \leq k \leq n - 1

Theorem 7.

Let

{(a_{n})}_{n ⩾ 1}

be an E-sequence such that (i)

3^{n} > 2^{b_{n}}

for all

n \in N

; (ii) there is a constant

c > {log}_{2} 3

such that there are infinitely many distinct pairs

(k, l)

of positive integers such that

l > k c

a_{k + 1} = \dots = a_{l} = 1

. Then,

Ω - lim a_{n} = \infty

Proof.

It follows from (i) that

B_{n} < 3^{n} n

for all

n \in N

by induction on n.

B_{k + 1}^{l - 1} = 3^{l - k} - 2^{l - k}

by Proposition 6.

Let

x_{l}^{1, l} = \frac{3^{l} x_{0}^{1, l} + B_{1}^{l - 1}}{2^{b_{l}}}

1 ⩽ x_{0}^{1, l} < 2^{b_{l}}

1 ⩽ x_{l}^{1, l} < 3^{l}

. Then,

x_{k}^{1, l} = \frac{3^{k} x_{0}^{1, l} + B_{1}^{k - 1}}{2^{b_{k}}}

x_{l}^{1, l} = \frac{3^{l - k} x_{k}^{1, l} + B_{k + 1}^{l - 1}}{2^{b_{k + 1}^{l}}}

by Proposition 5(ii). By

B_{k + 1}^{l - 1} = 3^{l - k} - 2^{l - k}

2^{b_{k + 1}^{l}} = 2^{l - k}

, we have

2^{l - k} (x_{l}^{1, l} + 1) = 3^{l - k} (x_{k}^{1, l} + 1)

. Thus,

x_{k}^{1, l} = 2^{l - k} w - 1

for some

1 ⩽ w

. Hence,

x_{k}^{1, l} = \frac{3^{k} x_{0}^{1, l} + B_{1}^{k - 1}}{2^{b_{k}}} = 2^{l - k} w - 1

. Therefore,

x_{0}^{1, l} = \frac{2^{l - k} 2^{b_{k}} w - 2^{b_{k}} - B_{1}^{k - 1}}{3^{k}} ⩾ \frac{2^{l}}{3^{k}} 2^{b_{k} - k} - 1 - k ⩾ {(\frac{2^{c}}{3})}^{k} 2^{b_{k} - k} - 1 - k

. If there are only finitely many distinct k in all pairs

(k, l)

x_{0}^{1, l} ⩾ \frac{2^{l}}{3^{k}} 2^{b_{k} - k} - 1 - k \to \infty

, as

l \to \infty

; otherwise,

x_{0}^{1, l} ⩾ {(\frac{2^{c}}{3})}^{k} 2^{b_{k} - k} - 1 - k \to \infty

, as

k \to \infty

. Then,

Ω - lim a_{n} = \infty

. □

Corollary 2.

Let

{(a_{n})}_{n ⩾ 1}

be the E-sequence

12121112 \dots

, where

a_{n} = 2

n \in {2^{1}, 2^{2}, 2^{3}, \dots}

and

a_{n} = 1

otherwise. Then,

Ω - lim a_{n} = \infty

Proof.

Take

c = \frac{7}{4} > {log}_{2} 3

k = 2^{m}

, and

l = 2^{m + 1} - 1

. Then,

a_{k + 1} = \dots = a_{l} = 1

l > k c

for all

m ⩾ 3 .

Thus,

Ω - lim a_{n} = \infty

by Theorem 7. □

Theorem 8.

Let

{(a_{n})}_{n ⩾ 1}

be an E-sequence such that (i)

3^{n} > 2^{b_{n}}

for all

n \in N

; (ii) there is a constant

c > {log}_{2} 3

such that there are infinitely many distinct pairs

(r, l)

of positive integers such that

l > r

b_{l + r} > l c

a_{l + k} = a_{k}

for all

1 ⩽ k ⩽ r

, i.e.,

(a_{1} \dots a_{r}) a_{r + 1} \dots a_{l} (a_{l + 1} \dots a_{l + r})

is contained in

{(a_{n})}_{n ⩾ 1}

. Then,

Ω - lim a_{n} = \infty

Proof.

Let

x_{l + r}^{1, l + r} = \frac{3^{l + r} x_{0}^{1, l + r} + B_{1}^{l + r - 1}}{2^{b_{1}^{l + r}}}

1 ⩽ x_{0}^{1, l + r} < 2^{b_{1}^{l + r}}

1 ⩽ x_{l + r}^{1, l + r} < 3^{l + r}

. Then,

x_{l}^{1, l + r} = \frac{3^{l} x_{0}^{1, l + r} + B_{1}^{l - 1}}{2^{b_{1}^{l}}}

x_{l + r}^{1, l + r} = \frac{3^{r} x_{l}^{1, l + r} + B_{l + 1}^{l + r - 1}}{2^{b_{l + 1}^{l + r}}} = \frac{3^{r} x_{l}^{1, l + r} + B_{1}^{r - 1}}{2^{b_{1}^{r}}}

by Proposition 5(ii). By

3^{l} > 2^{b_{1}^{l}}

, we have

x_{l}^{1, l + r} > x_{0}^{1, l + r}

Let

x_{r}^{1, r} = \frac{3^{r} x_{0}^{1, r} + B_{1}^{r - 1}}{2^{b_{1}^{r}}}

1 ⩽ x_{0}^{1, r} < 2^{b_{1}^{r}}

1 ⩽ x_{r}^{1, r} < 3^{r}

. Then,

x_{0}^{1, r} \equiv x_{l}^{1, l + r} (mod 2^{b_{1}^{r}})

. By Proposition 5(iii), we have

x_{0}^{1, l + r} ⩾ x_{0}^{1, r}

. Let

x_{l}^{1, l + r} = 2^{b_{1}^{r}} u + x_{0}^{1, r}

. Then,

u ⩾ 1

x_{l}^{1, l + r} > x_{0}^{1, l + r} ⩾ x_{0}^{1, r}

. Thus:

x_{0}^{1, l + r} = \frac{2^{b_{1}^{l}} 2^{b_{1}^{r}} u + 2^{b_{1}^{l}} x_{0}^{1, r} - B_{1}^{l - 1}}{3^{l}} ⩾ \frac{2^{b_{1}^{l + r}}}{3^{l}} - l ⩾ {(\frac{2^{c}}{3})}^{l} - l \to \infty, a s l \to \infty .

Hence,

Ω - lim a_{n} = \infty

. □

Theorem 9.

Let

1 ⩽ θ < {log}_{2} 3

, and define

a_{n} = [n θ] - [(n - 1) θ]

. Then,

Ω - lim a_{n} = \infty

Proof.

θ

is a rational number, then

{(a_{n})}_{n ⩾ 1}

is purely periodic, and the result follows from Theorem 1. Let

θ

be an irrational number in the following. By the Hurwitz theorem, there are infinite convergents

\frac{s}{r}

θ

such that

| θ - \frac{s}{r} | < \frac{1}{\sqrt{5} r^{2}}

. There are two cases to be considered.

Case 1. There are infinite convergents

\frac{s}{r}

θ

such that

0 < θ - \frac{s}{r} < \frac{1}{\sqrt{5} r^{2}}

. We prove that

[θ n] = [\frac{s}{r} n]

for all

1 ⩽ n ⩽ [\sqrt{5} r]

. By

1 ⩽ n ⩽ [\sqrt{5} r]

, we have

0 < θ n - \frac{s}{r} n < \frac{n}{\sqrt{5} r^{2}} < \frac{\sqrt{5} r}{\sqrt{5} r^{2}} = \frac{1}{r} .

Then,

0 ⩽ {\frac{s}{r} n} < θ n - [\frac{s}{r} n] < \frac{1}{r} + {\frac{s}{r} n} ⩽ 1 .

Thus,

0 < θ n - [\frac{s}{r} n] < 1 .

Hence,

[θ n] = [\frac{s}{r} n]

. Then, we have the following periodic table for

{(a_{n})}_{1 ⩽ n ⩽ [\sqrt{5} r]}

$a_{1}$	$a_{2}$	⋯	$a_{[\sqrt{5} r - 2 r]}$	⋯	$a_{r}$
$a_{r + 1}$	$a_{2 + r}$	⋯	$a_{[\sqrt{5} r - r]}$	⋯	$a_{2 r}$
$a_{2 r + 1}$	$a_{2 + 2 r}$	⋯	$a_{[\sqrt{5} r]}$

By Proposition 7(ii),

x_{0}^{1, 2 r} = \frac{2^{2 [r θ]} u_{2 r} - B_{r}}{3^{r} - 2^{[r θ]}}

for some

u_{2 r} ⩾ 1

B_{r} = \sum_{i = 0}^{r - 1} 3^{r - 1 - i} 2^{b_{i}} = 3^{r - 1} \sum_{i = 0}^{r - 1} \frac{2^{b_{i}}}{3^{i}} ⩽ 3^{r - 1} \sum_{i = 0}^{r - 1} \frac{2^{[i θ]}}{3^{i}} ⩽ 3^{r - 1} \sum_{i = 0}^{r - 1} \frac{2^{i θ}}{3^{i}} = \frac{3^{r}}{3} \frac{1 - {(\frac{2^{θ}}{3})}^{r}}{1 - \frac{2^{θ}}{3}} = \frac{3^{r} - 2^{r θ}}{3 - 2^{θ}} ⩽ \frac{3^{r}}{3 - 2^{θ}}

, we have:

x_{0}^{1, 2 r} ⩾ \frac{2^{2 [r θ]} - B_{r}}{3^{r} - 2^{[r θ]}} ⩾ \frac{4^{r θ - 1} - \frac{3^{r}}{3 - 2^{θ}}}{3^{r} - 2^{r θ - 1}} = \frac{\frac{1}{4} {(\frac{4^{θ}}{3})}^{r} - \frac{1}{3 - 2^{θ}}}{1 - \frac{1}{2} {(\frac{2^{θ}}{3})}^{r}} .

Thus,

x_{0}^{1, 2 r} \to \infty

, as

r \to \infty

. Hence,

Ω - lim a_{n} = \infty

Case 2. There are infinite convergents

\frac{s}{r}

θ

such that

0 < \frac{s}{r} - θ < \frac{1}{\sqrt{5} r^{2}}

Firstly, we prove

[θ n] = [\frac{s}{r} n]

for all

1 ⩽ n ⩽ [\sqrt{5} r]

n \notin {r, 2 r}

. By

0 < \frac{s}{r} - θ < \frac{1}{\sqrt{5} r^{2}}

, we have

\frac{s}{r} - \frac{1}{\sqrt{5} r^{2}} < θ < \frac{s}{r}

. Then,

\frac{s}{r} n - [\frac{s}{r} n] - \frac{n}{\sqrt{5} r^{2}} < θ n - [\frac{s}{r} n] < \frac{s}{r} n - [\frac{s}{r} n] < 1

. By

1 ⩽ n ⩽ [\sqrt{5} r]

n \notin {r, 2 r}

, we have

0 < \frac{1}{r} - \frac{n}{\sqrt{5} r^{2}} ⩽ \frac{s}{r} n - [\frac{s}{r} n] - \frac{n}{\sqrt{5} r^{2}}

. Then,

0 < θ n - [\frac{s}{r} n] < 1

. Thus,

[θ n] = [\frac{s}{r} n]

Secondly, we prove

[r θ] = s - 1

[2 r θ] = 2 s - 1

. By

1 ⩽ n

0 < \frac{s}{r} - θ < \frac{1}{\sqrt{5} r^{2}}

, we have

- \frac{n}{\sqrt{5} r^{2}} + \frac{s}{r} n < n θ < \frac{s}{r} n

. By

n < \sqrt{5} r

, we have

- 1 < - \frac{1}{r} < - \frac{n}{\sqrt{5} r^{2}}

. Then,

- 1 + \frac{s}{r} n < - \frac{n}{\sqrt{5} r^{2}} + \frac{s}{r} n < n θ < \frac{s}{r} n

. By taking

n = r, 2 r

, we have

[r θ] = s - 1

[2 r θ] = 2 s - 1

Let

2 ⩽ j ⩽ r - 1

, then

r + 2 ⩽ r + j ⩽ 2 r - 1

and

r + 1 ⩽ r + j - 1 ⩽ 2 r - 2

. Thus,

a_{r + j} = [θ (r + j)] - [θ (r + j - 1)] = [\frac{s}{r} (r + j)] - [\frac{s}{r} (r + j - 1)] = [s + \frac{s}{r} j] - [s + \frac{s}{r} (j - 1)] = [\frac{s}{r} j] - [\frac{s}{r} (j - 1)] = a_{j}

Let

2 ⩽ j ⩽ [\sqrt{5} r] - 2 r

. Then,

2 r + 2 ⩽ 2 r + j ⩽ [\sqrt{5} r]

and

2 r + 1 ⩽ 2 r + j - 1 ⩽ [\sqrt{5} r] - 1

. Thus,

a_{2 r + j} = [θ (2 r + j)] - [θ (2 r + j - 1)] = [\frac{s}{r} (2 r + j)] - [\frac{s}{r} (2 r + j - 1)] = [\frac{s}{r} j] - [\frac{s}{r} (j - 1)] = a_{j}

By easy calculation, we have

a_{r} = a_{2 r} = 1

a_{r + 1} = a_{2 r + 1} = 2

Then, we have the following periodic table for

{(a_{n})}_{1 ⩽ n ⩽ [\sqrt{5} r]}

$a_{1}$	$a_{2}$	$a_{3}$	⋯	$a_{[\sqrt{5} r] - 2 r}$	⋯	$a_{r}$	$a_{r + 1}$
	$a_{2 + r}$	$a_{3 + r}$	⋯	$a_{[\sqrt{5} r] - r}$	⋯	$a_{2 r}$	$a_{2 r + 1}$
	$a_{2 + 2 r}$	$a_{3 + 2 r}$	⋯	$a_{[\sqrt{5} r]}$

Since

θ < {log}_{2} 3

, we then take all convergents

\frac{s}{r}

θ

such that

\frac{s}{r} < {log}_{2} 3

, and thus,

2^{s} < 3^{r}

. By

a_{1} = 1

b_{2}^{r + 1} = [r θ] + 1 = s

and Proposition 7(ii), we have:

x_{0}^{1, 2 r + 1} = \frac{2^{2 s + 1} u_{2 r + 1} - (3^{r} - 2^{s}) - 2 B_{2}^{r}}{3 (3^{r} - 2^{s})}

for some

u_{2 r + 1} ⩾ 1

. By

B_{2}^{r} = \sum_{i = 0}^{r - 1} 3^{r - 1 - i} 2^{b_{2}^{i + 1}} = 3^{r - 1} \sum_{i = 0}^{r - 1} \frac{2^{[i θ + θ] - 1}}{3^{i}} ⩽ 3^{r - 1} 2^{θ - 1} \sum_{i = 0}^{r - 1} \frac{2^{i θ}}{3^{i}} = 2^{θ - 1} \frac{3^{r}}{3} \frac{1 - {(\frac{2^{θ}}{3})}^{r}}{1 - \frac{2^{θ}}{3}} = 2^{θ - 1} \frac{3^{r} - 2^{r θ}}{3 - 2^{θ}} ⩽ C 3^{r}

, where

C = \frac{2^{θ - 1}}{3 - 2^{θ}}

, we have:

x_{0}^{1, 2 r + 1} ⩾ \frac{2}{3} \frac{4^{[r θ] + 1} - C 3^{r}}{3^{r} - 2^{s}} - \frac{1}{3} ⩾ \frac{2}{3} \frac{4^{r θ} - C 3^{r}}{3^{r} - 2^{s}} - \frac{1}{3} ⩾ \frac{2}{3} \frac{4^{r θ} - C 3^{r}}{3^{r}} - \frac{1}{3} = \frac{2}{3} {(\frac{4^{θ}}{3})}^{r} - \frac{2}{3} C - \frac{1}{3} .

Thus,

{lim}_{r \to \infty} x_{0}^{1, 2 r + 1} = \infty

. Hence,

Ω - lim a_{n} = \infty

. □

5. Concluding Remarks and Open Problems

The results on non-periodic E-sequences in Section 4 were based on the theory of periodic E-sequences in Section 3 and the Matthews and Watts’ formula. Currently, we have no other way to tackle non-periodic E-sequences. We can obtain various generalizations and analogues of Theorems 4–8. However, we need good problems to make some progress.

One seemingly simple problem that we are not able to prove is whether

{(a_{n})}_{n ⩾ 1}

is divergent, where

a_{n} = 2

n \in {2^{2}, 3^{2}, 4^{2}, \dots}

and

a_{n} = 1

otherwise, i.e.,

{(a_{n})}_{n ⩾ 1}

111211112 \dots

Another interesting problem is whether

{(a_{n})}_{n ⩾ 1}

with infinitely many n satisfying

b_{n} > n {log}_{2} 3

Ω

-divergent. By virtue of Theorem 4, we only need to consider the case of

\underset{n \to \infty}{lim^{¯}} \frac{b_{n}}{n} = {log}_{2} 3

. Theorem 5 answers the problem if

\frac{B_{n}}{3^{n} (1.5 n^{\frac{1}{9}} - 1)} \to \infty

, as

n \to \infty

. Currently, we do not know how to tackle the other cases of the problem.

Conjecture 2(ii) is also important in some sense.

Funding

This work is supported by the National Foundation of Natural Sciences of China (Grant Nos. 61379018, 61662044, 11571013, and 11671358).

Acknowledgments

I am greatly indebted to Junde Miao for his constant encouragement while I was working on the problem.

Conflicts of Interest

The author declares no conflict of interest.

References

Lagarias, J.C. The 3x + 1 problem and its generalizations. Am. Math. Mon. 1985, 92, 3–23. [Google Scholar] [CrossRef]
Kadic, S.; Tomovic, S. Computer-Based Validation of 3n + 1 Hypothesis for Numbers 3ⁿ − 1. Teh. Vjesn. 2019, 26, 289–293. [Google Scholar] [CrossRef]
Thomas, A. A non-uniform distribution property of most orbits, in case the 3x + 1 conjecture is true. Acta Arith. 2017, 178, 125–134. [Google Scholar] [CrossRef]
Colussi, L. The convergence classes of Collatz function. Theor. Comput. Sci. 2011, 412, 5409–5419. [Google Scholar] [CrossRef]
Tao, T. Almost all orbits of the Collatz map attain almost bounded values. arXiv 2019, arXiv:1909.03562. [Google Scholar]
Kari, J. Universal pattern generation by cellular automata. Theor. Comput. Sci. 2012, 429, 180–184. [Google Scholar] [CrossRef]
Javaheri, M. A Collatz-type conjecture on the set of rational numbers. J. Number Theory 2012, 132, 2582–2594. [Google Scholar] [CrossRef]
Crandall, R.E. On the 3x + 1 Problem. Math. Com. 1978, 32, 1281–1292. [Google Scholar] [CrossRef]
Sander, J.W. On the (3N + 1)-conjecture. Acta Arith. 1990, 55, 241–248. [Google Scholar] [CrossRef]
Everett, C.J. Iteration of the number-theoretic function f(2n) = n, f(2n + 1) = 3n + 2. Adv. Math. 1977, 25, 42–45. [Google Scholar] [CrossRef]
Terras, R. A stopping time problem on the positive integers. Acta Arith. 1976, 30, 241–252. [Google Scholar] [CrossRef]
Möller, H. Über Hasses Verallgemeinerung des Syracuse -Algorithmus (Kakutanis Problem). Acta Arith. 1978, 34, 219–226. [Google Scholar] [CrossRef]
Matthews, K.R.; Watts, A.M. A generalization of Hasse’s generalization of the Syracuse algorithm. Acta Arith. 1984, 43, 167–175. [Google Scholar] [CrossRef]
Simons, J.L. On the (non-)existence of m-cycles for generalized Syracuse sequences. Acta Arith. 2008, 131, 217–254. [Google Scholar] [CrossRef]
Wendel, J.G. Note on the Gamma Function. Am. Math. Mon. 1948, 55, 563–564. [Google Scholar] [CrossRef]

© 2019 by the author. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Wang, S. An E-Sequence Approach to the 3x + 1 Problem. Symmetry 2019, 11, 1415. https://doi.org/10.3390/sym11111415

AMA Style

Wang S. An E-Sequence Approach to the 3x + 1 Problem. Symmetry. 2019; 11(11):1415. https://doi.org/10.3390/sym11111415

Chicago/Turabian Style

Wang, Sanmin. 2019. "An E-Sequence Approach to the 3x + 1 Problem" Symmetry 11, no. 11: 1415. https://doi.org/10.3390/sym11111415

APA Style

Wang, S. (2019). An E-Sequence Approach to the 3x + 1 Problem. Symmetry, 11(11), 1415. https://doi.org/10.3390/sym11111415

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

An E-Sequence Approach to the 3x + 1 Problem

Abstract

1. Introduction

2. Preliminaries

3. Periodic E-Sequences

4. Non-Periodic E-Sequences

5. Concluding Remarks and Open Problems

Funding

Acknowledgments

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI