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

David C. Kay^{*}

Show more

1. Introduction

Everett [1] (Iteration of the number-theoretic function *f*(2*n*) = *n*, *f*(2*n* + 1) = 3*n* + 2) introduced the concept of parity vectors to obtain early results concerning the 3*x* + 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 if*n* 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 3*x* + 1 problem is to prove this for all Collatz sequences *C*(*n*). Alternatively, one must prove that every Collatz sequence *C _{k}*(

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}*(

$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

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}*(

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^{1}0^{1}1^{3} 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}* <

It is useful to represent the 3*x* + 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*_{20}(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)}*(

Figure 1. Collatz graph for *C*(11).

Figure 2. Graph of *C*_{20}(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)$,

${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

An example will show how this procedure works. Suppose we want to find the smallest generator of *L* = 101^{3}0^{4}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} + 3^{2}

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

+ 2^{6} + 3^{4}

[4]*C*(73) → 73 94 47

+ 2^{7} + 3^{4}

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

+ 2^{9} + 3^{4}

[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* ^{r}*0

$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

$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}*(

${m}_{i}={\lambda}_{i}{m}_{i-1}+{d}_{i}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\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

$m=\Vert L\Vert n+{\displaystyle \sum {\left(\frac{3}{2}\right)}^{{u}_{i}}{\left(\frac{1}{2}\right)}^{{v}_{i}}{d}_{i}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\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^{3}0^{4}1 and it was determined that *n* = 713 and *m* = 170. In this case, *q* = 3, *s*_{0} = *s _{q}* = 0. First, compute

${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* ^{k}m* and 3

${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

$n={m}_{0}+{2}^{k}t$,

$m={n}_{0}+{3}^{r}t\text{\hspace{0.17em}}\text{\hspace{0.17em}}\left(t=0,1,2,\cdots \right)$

where *n*_{0} and *m*_{0} 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
$\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 2*q* then *n* = 1 and
${3}^{r}-{2}^{k}$ divides

$\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 3*x* + 1 problem in 1977-78. There are clearly 2* ^{k}* possible zero-one strings of length

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

Suppose the strings of length *k* are *L*_{1}, *L*_{2}, *L*_{3}, …, *L _{p}*,

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}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\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>r{\mathrm{log}}_{2}3$ (6.2)

Define the constants
${\omega}_{1}={\mathrm{log}}_{2}3\approx 1.584962501$ and:
${\omega}_{0}={\mathrm{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 ≤

${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* ≥ 3*p*, *n* has a finite stopping time. The number 3 is the least integer possible.

Proof: Set
$\epsilon ={2}^{-63}$. Let *C _{k}*(

$\frac{3{n}_{i}+1}{2}<\frac{3{n}_{i}+\epsilon {n}_{i}}{2}=\frac{3+\epsilon}{2}{n}_{i}$

Define *v _{i}* as follows: If

$\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* ≥ 3*p*. 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}*(

${\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}{3{n}_{i}}\right)={u}_{i}\left(1+\frac{1}{3{n}_{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{3{n}_{i}+1}{2}={u}_{i}\left(1+\frac{1}{3{n}_{i}}\right){n}_{i}={v}_{i}{n}_{i}$ if

$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}{3{n}_{i}}$ appears only when

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

where the product is taken over all the odd members *n _{j}* of the sequence, 1 ≤

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}{3{n}_{j}}\right)}\right]}^{-1}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\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^{3}0^{1}1^{1}0^{2}1^{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}* <

$\prod \left(1+\frac{1}{3{n}_{j}}\right)}>{\displaystyle \prod \left(1+\frac{1}{3{n}_{j}}\right)}={\left(1+\frac{1}{3p}\right)}^{r}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\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/3*p*, 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}{3{n}_{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 ≤

$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 3*x* + 1 Cycles Conjecture

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

$\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 2*r*. 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}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\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}*)

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

${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 3*x* + 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

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
${\mathrm{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*_{0} is a positive integer, *k* is an arbitrarily large integer, and {*t _{i}*} is an increasing sequence. Suppose

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

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*_{0} 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*_{1} 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 {

The resultants of these repeating strings must have the form
${m}_{0}+{3}^{r}{t}_{i}$ Thus If *n _{i}* and

${\mathrm{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* ^{r}c* is not a power of 2. Hence, from (7.1):

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

where, since *n*_{0} 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 3*x* + 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.

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 3*x* + 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 3*x* + 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 3*x* + 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