Collatz Sequences and Characteristic Zero-One Strings: Progress on the 3x + 1 Problem

David C. Kay^*

Asheville, USA.

DOI: 10.4236/ajcm.2021.113015                

Abstract

The unsolved number theory problem known as the 3x + 1 problem involves sequences of positive integers generated more or less at random that seem to always converge to 1. Here the connection between the first integer (n) and the last (m) of a 3x + 1 sequence is analyzed by means of characteristic zero-one strings. This method is used to achieve some progress on the 3x + 1 problem. In particular, the long-standing conjecture that nontrivial cycles do not exist is virtually proved using probability theory.

Keywords

Generator, Resultant, 3x + 1 Cycle

1. Introduction

Everett [1] (Iteration of the number-theoretic function f(2n) = n, f(2n + 1) = 3n + 2) introduced the concept of parity vectors to obtain early results concerning the 3x + 1 problem. A different aspect of that approach is to focus mainly on the elements of such vectors (zeros and ones) and to index them differently. The 3x + 1 problem involves using the following number theory algorithm: starting with any positive integer n, if n is even divided by 2, or ifn is odd multiply by 3, add 1, then divided by 2. This generates the Collatz sequence $\left\{n=n_1,n_2,\cdots \right\}$ (named after Lothar Collatz who introduced the problem). Experimentation suggests that such sequences always end in the trivial cycle {1, 2, 1, 2, …}. The 3x + 1 problem is to prove this for all Collatz sequences C(n). Alternatively, one must prove that every Collatz sequence C_k(n) of finite length k converges to 1 for all positive integers n, k large enough. This has been numerically verified for all $n<n^{\ast }=20\times 2^{58}=5.7646\times {10}^{18}$ (Lagarias [2] ), and more recently to $n^{\ast }=8.7\times {10}^{18}$.

A parity vector corresponding to a finite Collatz sequence is defined as $v=\left(x_1,x_2,\cdots x_k\right)$ where $x_i=n_i\left(\mathrm{mod}2\right)$, $\text{1}\le i\le k$. The characteristic zero-one string of C_k(n) is the set of zeros and ones in v, written as:

$L=0^{s_0}{1}^{r_1}{0}^{s_1}{1}^{r_2}{0}^{s_2}{1}^{r_q}{0}^{s_q}$

where r_i is the number of ones occurring in a group of consecutive ones in v, and s_i is the number of zeros in a following consecutive group of zeros, 0 ≤ i ≤ q. Here, r_i ≥ 1 and s_i ≥ 1 for all i, except for s₀ and s_q which can individually be zero.

For example, consider:

$C_8\left(67\right)=\left\{67,101,152,76,38,19,29,44\right\}$

Its parity vector is $v=\left(1,1,0,0,0,1,1,0\right)$ and its characteristic zero-one string is $l=1^2{0}^3{1}^2{0}^1$.

The total number of ones in a finite string will always be denoted r and the total number of zeros by s. Thus, in general:

$r=r_1+r_2+\cdots +r_q$ and $s=s_0+s_1+\cdots +s_q$

The length of a string is denoted l(L) = r + s = k, and its norm by $\Vert L\Vert =\frac{3^r}{2^k}$. If

L is the characteristic string of C_k(n), n = n₁ is called a generator of L,n_k a pre-resultant, and n_k+1 a resultant. If n is a generator of L and m a resultant, this relationship will be denoted nLm. A cycle, if it exists, will be denoted nLn (where L is an appropriate finite string). At first we consider only finite strings (corresponding to finite Collatz sequences).

At this point, it is clear that each positive integer is a generator of a string, but not so clear that a given (finite) string will have a generator. Note that a string can have more than one generator; for example, the string 1¹0¹1³ is generated by $C_5\left(9\right)=\left\{9,14,7,11,17\right\}$ and $C_5\left(41\right)=\left\{41,62,31,47,71\right\}$.

Much work has been done on what is called the stopping time function, σ(n) (see Terras [3] ). This function is defined to be the least positive integer k such that n_k < n, or = ∞ otherwise. Terras proved that almost all integers have a finite stopping time; that is, ${\lim }_{n\to \infty }\#\left\{\sigma \left(n\right)<\infty \right\}/n=1$.

It is useful to represent the 3x + 1 problem graphically. Figure 1 shows the graph of the Collatz sequence C(11), while Figure 2 illustrates such a convergent sequence with a large generator: C₂₀(11, 111).

2. Existence of Generators

The existence of a generator for a given zero-one string depends on the following result.

Theorem A: suppose that n is the smallest generator of a string L of length k with r odd members, and it is required to find the generator n’ for the string Lx of length k + 1, where x = either 0 or 1. If the resultant of L matches x (that is, T^(k)(n) (mod 2) = x), then n’ = n is the solution. But if T^(k)(n) and x are mismatched (that is, T^(k)(n)(mod 2) ≠ x), then n’ = n + 2^k is the solution. Furthermore, if m = T^(k)(n) is the resultant of L, then m' = m + 3^r is the pre-resultant of Lx.

Figure 1. Collatz graph for C(11).

Figure 2. Graph of C₂₀(11,111).

Proof: We need only prove this when the first mismatch occurs at n_k. Consider $T^{\left(i\right)}\left(n+2^k\right)$, i ≥ 1. By induction:

$T^{\left(1\right)}\left(n+2^k\right)=T^{\left(1\right)}\left(n\right)+u_1{2}^{k-1}$

where $u_1$ is either 1 or 3 according as n is even or odd:

$T^{\left(2\right)}\left(n+2^k\right)=T^{\left(2\right)}\left(n\right)+u_1{u}_2{2}^{k-2}$

where $u_2$ is either 1 or 3 according as $T^{\left(1\right)}\left(n\right)$ is even or odd,

…

$T^{\left(k\right)}\left(n+2^k\right)=T^{\left(k\right)}\left(n\right)+u_1{u}_2\cdots u_k$

where $u_k$ is either 1 or 3 according as $T^{\left(k-1\right)}\left(n\right)$ is even odd.

But $u_1{u}_2\cdots u_k=3^r$, and $T^{\left(k\right)}\left(n\right)=m$ is the resultant of L, while: $T^{\left(k\right)}\left(n+2^k\right)=m+3^r$ is the pre-resultant of Lx.

To apply Theorem A in a specific situation, suppose n is the smallest generator of L (length k) and the resultant of L is m = T^(k)(n). Consider the string Lx. If the next member of the Collatz sequence T(m) matches x, then n is the generator of Lx. If not, then add 2^k to n which (by Theorem A) will generate Lx with pre-resultant T(m) = m + 3^r where r is the number of ones in L.

An example will show how this procedure works. Suppose we want to find the smallest generator of L = 101³0⁴1 = 1011100001. Start with n = 1 (2 if the leading element of L is zero). Then:

[9]L → 1 0 1 1 1 0 0 0 0 1

[6] C(1) → 1 2 1 2

+ 2³ + 3²

[5]C(9) → 9 11 17 26 13

+ 2⁶ + 3⁴

[4]C(73) → 73 94 47

+ 2⁷ + 3⁴

[3] C(201) → 201 128 64 32

+ 2⁹ + 3⁴

[3]C(713) → 713 113

Thus, 713 is the smallest generator of L, 113 is its pre-resultant, and (3 × 113 + 1)/2 = 170 is its resultant.

Corollary: every finite string has a generator.

3. A Formula for the Resultant

One starts with the special case L = 1^r0^s, with n a generator of L Induction on r, starting with s = 0, shows that:

$m=\frac{3^{r}n+3^r-2^r}{2^{r+s}}$ (3.1)

which can be put in the form m = λn + d where λ = 3^r/2^r+s and $d=\left[{\left(\frac{3}{2}\right)}^r-1\right]/2^s$. In general, if:

$L=0^{s_0}{1}^{r_1}{0}^{s_1}{1}^{r_2}{0}^{s_2}{1}^{r_q}{0}^{s_q}$

with C_k(n) the Collatz sequence corresponding to L, let m_i be the member of the sequence that generates the substring of L beginning with $1^{r_i}$. Then for each i, 1 ≤ i ≤ q:

$m_i={\lambda }_i{m}_{i-1}+d_i\left(\text{1}\le i\le q\right)$

where $m_0=n$, ${\lambda }_i=3^{r_i}/2^{r_i+s_i}$, and $d_i=\left[{\left(\frac{3}{2}\right)}^{r_i}-1\right]/2^{s_i}$. Thus, performing the indicated substitutions, each m_i can be determined, and it follows that:

$m_q={\lambda }_q{\lambda }_{q-1}{\lambda }_{q-2}\cdots {\lambda }_{1}n+{\lambda }_q{\lambda }_{q-1}{\lambda }_{q-2}\cdots {\lambda }_2{d}_1+{\lambda }_q{\lambda }_{q-1}{\lambda }_{q-2}\cdots {\lambda }_3{d}_2+\cdots +{\lambda }_q{d}_{q-1}+d_q$

Since m_q is the resultant of the sequence corresponding to L and ${\lambda }_q{\lambda }_{q-1}{\lambda }_{q-2}\cdots {\lambda }_1=\Vert L\Vert$, the final result is:

$m=\Vert L\Vert n+{\displaystyle \sum {\left(\frac{3}{2}\right)}^{u_i}{\left(\frac{1}{2}\right)}^{v_i}{d}_i}\left(1\le i\le q\right)$ (3.2)

where $u_i=r_{i+1}+r_{i+2}+\cdots +r_q$ and $v_i=s_{i+1}+s_{i+2}+\cdots +s_q$ ( $u_q=v_q=0$ ). This formula is a special case of a similar one obtained by Bohm and Sontacchi in 1978.

The validity of (3.2) can be checked, using the example in Section 1, where L = 101³0⁴1 and it was determined that n = 713 and m = 170. In this case, q = 3, s₀ = s_q = 0. First, compute u_i, v_i, and d_i: for each i ≤ 3):

$u_{\text{1}}=\text{4}$, $v_{\text{1}}=\text{4}$, $u_2=1$, $v_{\text{2}}=0$, and $u_{\text{3}}=v_{\text{3}}=0$

$d_{\text{1}}=1/4$, $d_2=19/128$, and $d_{\text{3}}=1/2$.

Then:

$\begin{array}{c}m=\frac{3^5}{2^{10}}n+{\left(\frac{3}{2}\right)}^4{\left(\frac{1}{2}\right)}^4{d}_1+{\left(\frac{3}{2}\right)}^1{\left(\frac{1}{2}\right)}^0{d}_2+d_3\\ =\frac{3^5}{2^{10}}n+{\left(\frac{3}{2}\right)}^4{\left(\frac{1}{2}\right)}^4\frac{1}{2^2}+{\left(\frac{3}{2}\right)}^1{\left(\frac{1}{2}\right)}^0\frac{19}{2^7}+\frac{1}{2}\\ =\frac{3^5\left(713\right)+3^4+3\times 19\times 2^2+2^9}{2^{10}}\\ =\frac{173259+81+228+512}{1024}=\frac{174080}{1024}=170\end{array}$

4. The Diophantine Equation

The above Equation (3.2) is equivalent to:

$2^{k}m=3^{r}n+2^{k}Q$

where Q is the summation term in (3.2). Since both 2^km and 3^rn are positive integers, the term $2^{k}Q\equiv N$ is an integer and we obtain the well-known Diophantine equation for the 3x + 1 problem:

$2^{k}m-3^{r}n=N$ (4.1)

where N is the product of 2^k and the summation term in (3.2). Since 2^k and 3^r are relatively prime, (4.1) has infinitely many positive solutions of the form:

$n=m_0+2^{k}t$,

$m=n_0+3^{r}t\left(t=0,1,2,\cdots \right)$

where n₀ and m₀ are the smallest positive solutions of (4.1). Thus every zero-one string has infinitely many generators of the form listed above.

Moreover, by setting m = n, one obtains an explicit formula for the generator of a cycle:

$n=\frac{2^k{\displaystyle \sum {\left(\frac{3}{2}\right)}^{u_i}{\left(\frac{1}{2}\right)}^{v_i}{d}_i}}{3^r-2^k}$ (4.2)

In general, the numbers in this equation are incredibly large, but if it could be shown that for n ≥ 3 a prime divisor of $3^r-2^k$ does not divide ${\displaystyle \sum a^{u_i}{b}^{v_i}{d}_i}$ evenly, a proof that nontrivial cycles do not exist is obtained. Note that if n is a generator of 1010… 10 of length 2q then n = 1 and $3^r-2^k$ divides

${\displaystyle \sum {\left(\frac{3}{2}\right)}^{u_i}{\left(\frac{1}{2}\right)}^{v_i}{d}_i}$ evenly.

5. Result of Terras and Everett

Theorem A leads to a surprising relationship between all strings of length k and their least generators. It was discovered independently by Terras [3] and Everett [1] in their work on the 3x + 1 problem in 1977-78. There are clearly 2^k possible zero-one strings of length k, so starting with the 4 strings of length 2, we can easily deduce their least generators (and resultants):

4 (00) 1; 2 (01) 2; 1 (10) 1; 3 (11) 8

Suppose the strings of length k are L₁, L₂, L₃, …, L_p, p = 2^k, and we seek the generators of the strings of length k + 1, which are of the form 0L_i and 1L_i, 1 ≤ i ≤ 2^k. Those with leading term zero in L_i are obviously generated by the even integers 2, 4, 6, …, 2^k+1. The remaining strings with leading term one must have odd generators. Half of them correspond to strings ending in zero, the other half to strings ending in one.

Theorem B: The strings of length k + 1 are uniquely generated by the positive integers less than or equal to 2^k+1. Accordingly, there is a one-to-one correspondence between the strings of length k + 1 and their least generators.

Proof: A careful analysis of the previous discussion reveals that all the integers from 1 to 2^k+1 have been accounted for.

Table 1 illustrates Theorem B, showing all the possible characteristic strings of lengths 3, 4 and 5 and the corresponding generators and resultants. At this point we use the notation nLm only when n is the unique least generator of the string L and m is its resultant.

6. Inequalities

Suppose nLm with L of length k, and $\Vert L\Vert =3^r/2^k$. One obtains from (3.2):

$\begin{array}{c}m=\Vert L\Vert n+{\displaystyle \sum {\left(\frac{3}{2}\right)}^{u_i}{\left(\frac{1}{2}\right)}^{v_i}{d}_i}\left(1\le i\le q\right)\\ <\Vert L\Vert n+{\displaystyle \sum {\left(\frac{3}{2}\right)}^{u_i}{\left(\frac{1}{2}\right)}^{v_i}{\left(\frac{3}{2}\right)}^{r_i}{\left(\frac{1}{2}\right)}^{s_i}}<\Vert L\Vert n+{\left(\frac{3}{2}\right)}^r{\displaystyle \sum {\left(\frac{1}{2}\right)}^i}\\ <\Vert L\Vert n+{\left(\frac{3}{2}\right)}^r\left(\frac{1}{2}+\frac{1}{4}+\cdots +\frac{1}{2^q}\right)<\Vert L\Vert n+{\left(\frac{3}{2}\right)}^r\end{array}$

Table 1. List of Generators for Strings of Lengths 3, 4, and 5

Thus it follows that:

$\Vert L\Vert n<m<\Vert L\Vert n+{\left(\frac{3}{2}\right)}^r$ (6.1)

Due to the term ${\left(\frac{3}{2}\right)}^r$ one cannot conclude that m < n if $\Vert L\Vert <1$. However

this is true if $\Vert L\Vert$ is small enough, as one might expect. In fact, if L has as many zeros as ones, then m < n, as will be shown. A cyclic string with m = n must have $\Vert L\Vert <1$, due to (6.1). Thus 3^r < 2^k. Taking the logarithm to the base 2, we have:

$k>r{\log }_{2}3$ (6.2)

Define the constants ${\omega }_1={\log }_{2}3\approx 1.584962501$ and: ${\omega }_0={\log }_{2}3-1\approx 0.584962501$. Since k = r + s, we have for any string L such that $\Vert L\Vert <1$ :

$s>r{\omega }_0$ and $k>r{\omega }_1$ (6.3)

7. The Ratio s/r and Finite Stopping Time for Certain Collatz Sequences

The numerical order relationship between r and s sometimes determines whether the generator of a string has a finite stopping time.

Theorem C: Suppose that s ≥ r in the Collatz sequence mLn where m ≥ 3. Then m < n and n has a finite stopping time.

Proof: Define the sequence {v_i}, 1 ≤ i ≤ k, as follows: if n_i is even, set v_i = 1/2; if n_i is odd, set v_i = 2. Then for each i, if n_i is even $n_{i+1}=v_i{n}_i$, and if n_i is odd $n_{i+1}=\left(3n_i+1\right)/2<2n_i=v_i{n}_i$. It follows that:

$n_2\le v_1{n}_1$, $n_3\le v_2{n}_2\le v_2{v}_1{n}_1$, $n_4\le v_3{n}_3\le v_3{v}_2{v}_1{n}_1$, $\cdots$

and:

$m=n_{k+1}\le v_1{v}_2{v}_3\cdots v_k{n}_1<{\left(\frac{1}{2}\right)}^s{2}^{r}n\le {\left(\frac{1}{2}\right)}^s{2}^{s}n=n$

A more general result can be shown by substantially the same argument.

Theorem D: suppose that nLm, m > 1, and for some positive integer p, s = r – p. Then if r ≥ 3p, n has a finite stopping time. The number 3 is the least integer possible.

Proof: Set $\epsilon =2^{-63}$. Let C_k(n) be the Collatz sequence corresponding to the string L. If $n_i<\frac{1}{\epsilon }$ for at least one i, 1 ≤ i ≤ k, then $n_i<2^{63}<20\times 2^{58}=n^{\ast }$ and n has a finite stopping time. Thus it may be assumed that $n_i>\frac{1}{\epsilon }$ for all i, or 1 < εn_i. Thus:

$\frac{3n_i+1}{2}<\frac{3n_i+\epsilon n_i}{2}=\frac{3+\epsilon }{2}{n}_i$

Define v_i as follows: If n_i is even take v_i = 1/2; if n_i is odd, $v_i=\frac{3+\epsilon }{2}$. Then it follows that for 1 ≤ i ≤ k, $n_{i+1}\le v_i{n}_i$. Hence, as in Theorem C, $m=n_{k+1}<v_1{v}_2\cdots v_k{n}_1$ and we obtain:

$\begin{array}{c}m<{\left(\frac{1}{2}\right)}^s{\left(\frac{3+\epsilon }{2}\right)}^{r}n={\left(\frac{1}{2}\right)}^{r-p}{\left(\frac{3+\epsilon }{2}\right)}^{r}n=2^p{\left(\frac{3+\epsilon }{4}\right)}^{r}n\\ \le 2^{r/3}{\left(\frac{3+0.1}{4}\right)}^{r}n={\left[\sqrt[3]{2}\left(\frac{31}{40}\right)\right]}^{r}n<n\end{array}$

Corollary: suppose that nLm, m > 1, and s/r ≥ 2/3. Then n has finite stopping time.

Proof: If s ≥ r, then Theorem C applies and m < n. Otherwise, s < r and there exists a positive integer p such that s = r − p. By hypothesis:

$\frac{r-p}{r}\ge \frac{2}{3}$

$1-\frac{p}{r}\ge \frac{2}{3}$

from which it follows that r ≥ 3p. Therefore by Theorem D n has finite stopping time.

It might be imagined that if a cycle exists the effect of the odd members in the cycle essentially cancels that of the even members, and s is roughly equal to r. As a matter of fact, the number of even members is about 63% the number of odd members: if C_k(n) is a nontrivial cycle, then $\Vert L\Vert <1$ and $3^r<2^k$, which leads to $k<r{\log }_{2}3=r{\omega }_1$ where ${\omega }_1={\log }_{2}3=1.584962\cdots$. Also, the above corollary implies that s/r < 2/3, and k < 5/3. Thus:

${\omega }_1<\frac{k}{r}<\frac{5}{3}$ and $0.585\approx {\omega }_0<\frac{s}{r}<\frac{2}{3}\approx 0.667$ (7.1)

Using a theorem of Crandall [4] , Lagarias showed in [2] that a non1rivial cycle, if it exists, must have length at least k = 275,000. More recently a paper by Halbeisen and Hungerbühler [5] in 1997 showed that k > 102,225,496. The article by Eliahou [6] established k in terms of the minimum element of a cycle. Brox [7] showed that certain cycles occur only finitely many times.

8. Another Formula for the Resultant

Define:

$v_i=u_i=\frac{1}{2}$

if n_i is even:

$v_i=\frac{3}{2}\left(1+\frac{1}{3n_i}\right)=u_i\left(1+\frac{1}{3n_i}\right)$

if n_i is odd:

Then $n_{i+1}=u_i{n}_i$ if n_i is even, and $n_{i+1}=\frac{3n_i+1}{2}=u_i\left(1+\frac{1}{3n_i}\right)n_i=v_i{n}_i$ if n_i is odd. Thus:

$m=v_1{v}_2{v}_3\cdots v_{k}n$

The product of the factors u_i is $\Vert L\Vert$ and the factor $1+\frac{1}{3n_i}$ appears only when n_i is odd. Hence:

$m=\Vert L\Vert n{\displaystyle \prod \left(1+\frac{1}{3n_j}\right)}$ (8.1)

where the product is taken over all the odd members n_j of the sequence, 1 ≤ j ≤ r. (If there are no odd members, then we interpret (8.1) as simply $m=\Vert L\Vert n$, which is trivially true).

Solving for ||L|| in (6.1) produces an interesting formula for the norm:

$\Vert L\Vert =m{\left[n{\displaystyle \prod \left(1+\frac{1}{3n_j}\right)}\right]}^{-1}\left(1\le j\le r\right)$ (8.2)

where the product is taken over all the odd members of the sequence.

For a numerical test of (8.2), consider 7(1³0¹1¹0²1¹)8. The odd members of the designated Collatz sequence are 7, 11, 17, 13, and 5. The expression inside the brackets in (8.2) equals:

$\begin{array}{l}7\left(1+\frac{1}{21}\right)\left(1+\frac{1}{33}\right)\left(1+\frac{1}{51}\right)\left(1+\frac{1}{39}\right)\left(1+\frac{1}{15}\right)\\ =7\times \frac{22}{21}\times \frac{34}{33}\times \frac{52}{51}\times \frac{40}{39}\times \frac{16}{15}=\frac{2\times 2\times 4\times 8\times 16}{3\times 3\times 3\times 3\times 3}=\frac{2^{11}}{3^5}\end{array}$

from which it follows that $m\cdot \frac{3^5}{2^{11}}=8\cdot \frac{3^5}{2^{11}}=\frac{3^5}{2^8}$, the correct value for $\Vert L\Vert$.

An inequality can be established using (6.1). Suppose that p is an upper bound for the odd members of the Collatz sequence nLm. That is, n_j < p for all j. Then:

${\displaystyle \prod \left(1+\frac{1}{3n_j}\right)}>{\displaystyle \prod \left(1+\frac{1}{3n_j}\right)}={\left(1+\frac{1}{3p}\right)}^r\left(1\le j\le r\right)$

and it follows from (6.1) that:

$m>\Vert L\Vert n{\left(1+q\right)}^r$ (8.3)

where q = 1/3p, slightly stronger than (6.1).

9. Relation between k and n^*

A formula for the product term in (8.1) will be obtained for all Collatz sequences that do not have a finite stopping time. Starting with (8.1):

$m=\Vert L\Vert n{\displaystyle \prod \left(1+\frac{1}{3n_j}\right)}$.

which is equivalent to:

$\frac{2^{k}m}{n}={\displaystyle \prod \left(3+\frac{1}{n_j}\right)}$

Let c be the product term in the previous equation, and consider the continuous function:

$f\left(x\right)={\left(3+x\right)}^r$

for fixed r. Then:

$c>3^r=f\left(0\right)$.

Also, for Collatz sequences with no finite stopping time and having r odd members, n_j (1 ≤ j ≤ r), we must have $n_j\ge n^{\ast }$ for all j, and thus:

$c={\displaystyle \prod \left(3+\frac{1}{n_j}\right)}<{\displaystyle \prod \left(3+\frac{1}{n^{\ast }}\right)}=3+\frac{1}{n^{\ast }}=f\left(\frac{1}{n^{\ast }}\right)$

Accordingly, there exists $0<\epsilon <\frac{1}{n^{\ast }}$ such that $f\left(\epsilon \right)=c$. Or:

$3+\frac{1}{n^{\ast }}>{\left(3+\epsilon \right)}^r={\displaystyle \prod \left(3+\frac{1}{n_j}\right)}=\frac{2^{k}m}{n}>2^k$

and it follows that:

$2^k<{\left(3+\frac{1}{n^{\ast }}\right)}^r$ (9.1)

10. The 3x + 1 Cycles Conjecture

The result (8.1) with m = n yields the relation:

${\displaystyle \prod \left(3+\frac{1}{n_j}\right)}=2^k$ (10.1)

Since all the factors of the above product are fractional, it seems unlikely that the product is a power of 2.

It was proved in the preceding section that the product term equals ${\left(3+\epsilon \right)}^r$. Then for nontrivial cycles one obtains:

${\left(3+\epsilon \right)}^r=2^k$

It might be imagined that ${\left(3+\epsilon \right)}^r$ is not an integer since $\epsilon$ is a very small positive number, thus providing an immediate proof that cycles do not exist. But this is false in general, for the equation:

${\left(\text{3}+x\right)}^r={\text{2}}^u$

has a positive solution in x for certain values of u. Suppose u lies between $r{\omega }_1$ and 2r. Then:

${\left(3+x\right)}^r>2^{r{\omega }_1}=3^r$

$3+x>3$

$x>0$

Also:

${\left(3+x\right)}^r<2^{2r}$

$3+x<4$

$x<1$

If u = k then one observes that the above condition for u is satisfied for a nontrivial cycle and there is a solution for:

${\left(3+x\right)}^r=2^k\left(0<x<1\right)$

For example:

${\left(3.17480210389\cdots \right)}^9=2^{15}$

The question is whether $x=\epsilon$. In fact, the above analysis proves that $\epsilon$ must have the exact value:

$\epsilon =2^{k/r}-3$

and it remains to obtain a contradiction.

It is important in our analysis to show that $\epsilon$ is irrational. Note that for a nontrivial cycle:

$3+\epsilon =2^{k/r}$

where ${\omega }_1<k/r<5/3$. Thus:

$\omega <2^{k/r}<5/3$

so that (2^k)^1/r is not an integer. It is well known that, accordingly, (2^k)^1/r is irrational, proving that $3+\epsilon$ and $\epsilon$ are irrational.

11. Probabilistic Proof That Cycles Do Not Exist

Consider the product:

${\left(3+\epsilon \right)}^{r-1}\left(3+\epsilon \right)={\left(3+\epsilon \right)}^r$

(which equals 2^k if a nontrivial cycle exists). The decimal form of the left side is:

$\left(a+0.a_1{a}_2\cdots \right)\left(3+\mathrm{0.0.}{b}_1{b}_2\cdots \right)$

where a is a large positive integer and the first 18 decimals of $0.b_1{b}_2\cdots$ are zero. (It may be assumed that ${\left(3+\epsilon \right)}^{r-1}$ is irrational, for if not, then ${\left(3+\epsilon \right)}^r$ is irrational and ≠2^k, ending the proof). Multiplying out, one obtains:

$3a+3\left(0.a_1{a}_2\cdots \right)+a\left(\mathrm{0.0.}{b}_1{b}_2\cdots \right)+\left(0.c_1{c}_2\cdots \right)$

Let b be the integral part of $3\left(0.a_1{a}_2\cdots \right)$ and c the integral part of $a\left(\mathrm{0.0.}{b}_1{b}_2\cdots \right)$. Then we obtain for certain decimals:

$3a+b+\left(0.d_1{d}_2\cdots \right)+c+\left(0.e_1{e}_2\cdots \right)+\left(0.c_1{c}_2\cdots \right)$

The fractional part of the final result equals:

$\left(0.d_1{d}_2\cdots \right)+\left(0.e_1{e}_2\cdots \right)+\left(0.c_1{c}_2\cdots \right)=u_0.u_1{u}_2\cdots$

The final decimal $u_0.u_1{u}_2\cdots$ equals an integer only if u_i = 9 for all i ≥ 1 and, accordingly, equals:

$u_0.9999\cdots 9\cdots =u_0+1$

The probability that the first p decimals equal 9 is 1/10^p ≈ 0, and the probability that all the decimals equal 9 is virtually zero. The probability of the existence of a nontrivial cycle is thus virtually impossible.

12. Infinite Strings

The essence of the 3x + 1 problem involves infinite strings. Several elementary results concerning infinite strings can be established. First observe that not all infinite strings have generators; simple examples are:

$11111\cdots$, $00000\cdots$, $10101010\cdots$

In order for an infinite string to have a generator, it must at least have a mixture of zeros and ones that continues indefinitely. One somewhat surprising fact is:

Theorem E: if a generator of an infinite string exists, it is unique.

Proof: suppose L is an infinite string having n as a generator. There must at some point be an odd member of the sequence and there is no loss if it is assumed that n is odd. If a second generator n’ = n + p exists, let 2^q be the highest power of 2 that divides p. and perform the Collatz algorithm on n’ repeatedly: ${n^{\prime }}_1=n_1+2^q{p}^{\prime }$, ${n^{\prime }}_2=\left[3\left(n_1+2^q{p}^{\prime }\right)+1\right]/2=n_2+3\cdot 2^{q-1}{p}^{\prime }$, $\cdots$, ${n^{\prime }}_q=n_q+3^q{p}^{\prime }$. The next term will be a non-integer and n’ cannot be a generator.

Suppose that C is a Collats sequence with infinitely many terms different from 1. Its corresponding zero-one string is L, consisting of infinitely many zeros and ones. The generator of C is n, a finite positive integer. As we progress through the algorithm to obtain successive values of C, no discrepancy ever exists, an unlikely circumstance (see Section 4). But this has, as yet, resisted proof.

If we assume that no nontrivial cycles exist, there can be no upper bound for any Collatz sequence, hence ${\lim }_{i\to \infty }{n}_i=\infty$. As a matter of fact, it follows that every Collatz sequence that does not converge to 1 contains an increasing subsequence of the form $n_0+2^k{t}_i$ where n₀ is a positive integer, k is an arbitrarily large integer, and {t_i} is an increasing sequence. Suppose C is a collatz sequence that does not converge to 1, and let $L^{\ast }$ be its characteristic string, with odd generator n.

Theorem F: The string $L^{\ast }$ is of the form $K_{1}L{K}_2\cdots K_{i-1}L{K}_i\cdots$ where L is a finite substring repeated infinitely often of arbitrarily large length and with beginning element 1, and K_i is a finite substring of $L^{\ast }$ or the empty set if two substrings L juxtoposed.

Proof (by induction on k, the length of L): to obtain a string L of length k = 1, take the first element 1 of $L^{\ast }$ and observe that neither 000… 0… nor 111… 1… have generators. Thus a repeated element 1 must occur infinitely often, and we take L = 1. Assume that a finite string L of length k beginning with 1 occurs infinitely often. Let the element immediately following L be denoted x, which must be repeated infinitely often, producing the string Lx of length k + 1, where Lx must occur infinitely often.

Consider the string $L^{\ast }=K_{1}L{K}_2\cdots K_{i-1}L{K}_i\cdots$ with generator n. Let n₀ be the least generator of L From a previous result, the generator of the string from this point on must be of the form:

$n_0+2^k{t}_1$

where k is the length of L and t₁ is a positive integer. For the subsequent repeated strings which are identical to L, their generators must also be of the form $n_0+2^k{t}_i$, where t_i is a positive integer. We can assume that the sequence {t_i} is increasing since it must contain one that is. Thus, we have proved the previous claim made above.

The resultants of these repeating strings must have the form $m_0+3^r{t}_i$ Thus If n_i and m_i are the elements of C immediately preceding and following a string L, the limit of their quotients converges to the norm of L:

${\lim }_{i\to \infty }\frac{m_i}{n_i}=\frac{m_0+3^r{t}_i}{n_0+2^k{t}_i}=\frac{3^r}{2^k}=\Vert L\Vert$

The product Formula (8.1) leads to another relation involving the string $L^{\ast }$. Again, assuming nontrivial cycle exists, it was determined that 3^rc is not a power of 2. Hence, from (7.1):

$\frac{m}{n}\ne 2^p$

where, since n₀ is odd, then $n_0+2^k{t}_i$ is odd and both m and n may be assumed to be odd integers with m much larger than n. It may be possible to derive a contradiction here.

Another possibility derives from an inequality, also with m and n odd and m much larger than n.

Let the string corresponding to the Collatz sequence beginning with $n=n_0+2^{k^{\prime }}{t}_0$ and ending with $m=n_0+3^{r^{\prime }}{t}_i$ be K of, length k with r ones and s zeros. If $\Vert K\Vert <1$ (or $k>r{\omega }_{\text{1}}$ ), one obtains from the inequality (4.2):

$3^{r^{\prime }}{t}_i>3{\left(\frac{3}{2}\right)}^r+\Vert K\Vert 2^{k^{\prime }}{t}_0$ (12.1)

where r’ and k’ are the indices corresponding to L. This could lead to a contradiction.

13. Conclusion

The main goal of this article was to find an elementary proof involving zero-one strings to show that nontrivial cycles do not exist. A proof no doubt depends ultimately on advanced results in number theory, as yet not identified. As shown by many authors, such as the group here in the references, a proof must involve methods defined by multiple new or old results involving intricate details. Of course, the problem as a special case of the original 3x + 1 problem could be undecidable, not yet determined. It can only be hoped that untried methods of proof showing up in the literature can trigger the discovery of a connection to known results that finally provides a contradiction.

NOTES

*Formerly worked in the University of North Carolina at Asheville, Asheville, USA.

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1]	Everett, C.J. (1977) Iteration of the Number Theoretic Function f(2n) = n, f(2n + 1) = 3n + 2. Advances in Mathematics, 25, 42-45. https://doi.org/10.1016/0001-8708(77)90087-1
[2]	Lagarias, J.C. (2010) The Ultimate Challenge: The 3x + 1 Problem. American Mathematical Society, Providence. https://doi.org/10.1090/mbk/078
[3]	Terras, R. (1976) A Stopping Time Problem on the Positive Integers. Acta. Arithmetica, 30, 241-252. https://doi.org/10.4064/aa-30-3-241-252
[4]	Crandall, R.E. (1978) On the 3x + 1 Problem. Mathematics of Computation, 32, 1281-1292. https://doi.org/10.2307/2006353
[5]	Halbeisen, L. and Hungerbühler, N. (1997) Optimal Bounds for the Length of Rational Collatz Cycles. Acta Arithmetica, 78, 227-239. https://doi.org/10.4064/aa-78-3-227-239
[6]	Eliahon, S. (1993) The 3x + 1 Problem: New Lower Bounds on Nontrivial Cycle Lengths. Discrete Mathematics, 118, 45-56. https://doi.org/10.1016/0012-365X(93)90052-U
[7]	Brox, T. (2000) Collatz Cycles with Few Descents. Acta Arithmetica, 92, 181-188. https://doi.org/10.4064/aa-92-2-181-188