# An elementary proof of the Syracuse conjecture

Hassan Douzi*

*Ibn Zohr University, Faculty of Science, Department of Mathematics, BP8106 Agadir, Morocco.

Tel: 212 6 61224366, Mail: h.douzi @ uiz.ac.ma

## Abstract

Syracuse conjecture stated that all positive integer sequences $(T_n)_{n \ge 0}$, defined by $T_{n+1} = \frac{T_n}{2}$ if $T_n$ is even and $T_{n+1} = \frac{3T_n+1}{2}$ if $T_n$ is odd for $n \ge 0$, finishes always by taking successively the value 1 and 2. A formal proof of the conjecture is lacking so far in spite of various approaches to the problem. In this paper, we establish an elementary proof, based on two complementary approaches: The first is an arithmetic formulation which allows identifying Syracuse sequences to perturbations of rational powers sequences and, equivalently, to modifications of Sturmian words associated to them. The second is a visualization of Syracuse sequences as binary cellular automata, which when expressed in gray code, leads to the appearance of a “tree” structure with coalescing “branches”. We prove that the modification of the Sturmian words provoked by Syracuse sequences imposes the fusion of all the branches and this establishes the famous conjecture.

**Keywords:** Collatz problem, 3x+1 problem, Sturmian words, Cellular automata, Gray code.

## 1. Introduction

The Syracuse problem (also called the Collatz problem or 3x±1 problem) may be stated in a variety of ways [1]. For example Syracuse $(T_n)_{n \ge 0}$ sequences, corresponding respectively to the so called 3x+1 or to the 3x-1 problem, can be constructed iteratively by:

* The initial term $T_0$ is a given positive integer

* for $n \ge 0$ we have:

$$ \begin{cases} T_{n+1} = \frac{3T_n+1}{2} & \text{if } T_n \equiv 1 \mod(2) \\ T_{n+1} = \frac{T_n}{2} & \text{if } T_n \equiv 0 \mod(2) \end{cases} \qquad (1.1) $$

The 3x-1 problem corresponds exactly to the 3x+1 problem (up to the sign) when $T_0$ is a negative integer.

**Conjecture 1.1 (3x±1 problem)** For any positive integer number $T_0$, the (3x+1)sequence ends with the trivial cycle (1,2) and the (3x-1) sequence ends with one of the three cycles: (1), (5,7) or (17,25,37,55,41,61,91).

A formal proof is lacking so far in spite of various approaches to the problem [2] [3] [4] [5] [6] [7] [8] [9]. In this paper we will restrict ourselves to the treatment of the 3x+1 conjecture.

### 1.1. Arithmetic formulation

Another Arithmetic formulation for the Syracuse sequence 3x+1, which is more appropriate for our purpose and is reduced to only odd numbers, is defined by:
• $S_0$ is a given odd positive integer.

• for $n \ge 0$,

$$S_{n+1} = \frac{3S_n+1}{2^{1+g_n}} \text{ with } g_n = v_2\left(\frac{3S_n+1}{2}\right) \qquad (1.2)$$
(with $v_2$ the 2-adique valuation)

This gives a direct expression of $(S_n)_{n \ge 0}$, (for a given initial term $S_0$):

$$\left\{
\begin{array}{l}
S_n = \left(\frac{3^n}{2^{n+e_n}}\right) (S_0 + \Sigma_n) \\
\text{with } \Sigma_n = \sum_{j=0}^{n-1} \frac{2^{j+e_j}}{3^{j+1}}, \quad e_n = \sum_{j=0}^{n-1} g_j \\
g_0 = e_0 = 0 \text{ and } g_j = v_2\left(\frac{3S_j+1}{2}\right)
\end{array}
\right.
\qquad (1.3)$$

If replaced by $g_n = v_2(\frac{3S_n-1}{2})$ and $S_n = (\frac{3^n}{2^{n+e_n}})(S_0 - \Sigma_n)$, we have exactly the same formulation for the 3x-1 problem. In this formulation we see, that the Syracuse sequence $(S_n)_{n \ge 0}$ is a perturbation, by the introduction of $(e_n, \Sigma_n)$, of the rational powers sequence $(S_0(3/2)^n)_{n \ge 0}$. Rational powers sequences (of the form $(\xi(p/q)^n)_{n \ge 0}$) have been extensively studied [10] and have connections with many famous combinatorics and number theory problems such as Z-numbers problem and warring problem [11][12] [13] [14][15]. So the Syracuse problem is a part of this family of inextricable problems that makes Paul Erdos stated that: "Mathematics may not be ready for such problems" [20][23][24].

## 1.2. (3/2) Cellular Automaton Formulation

Let's consider now the binary expansions of the Syracuse sequence $(S_n)_{n \ge 0}$:

$$S_n = \sum_{j \in N} b_{(n,j+e_n)} 2^j = (\cdots b_{(n,2+e_n)} b_{(n,1+e_n)} b_{(n,0+e_n)})_2, \quad \text{for } n \ge 0,$$

The binary coefficients $(b_{(n,j+e_n)})_{n,j \ge 0}$ form, by their indexes, a subset of the lattice $Z^2$ and $e_n$ fixes the beginning position of $S_n$ in the lattice (the lattice is completed by zero values). Then $(b_{(n,j)})_{n,j \ge 0}$ can be seen as a dynamical system, more precisely as a binary one dimensional cellular automaton (CA) evolving with the index $n$ [25]; the automaton is initialized with the binary expansion of $S_0$, and iteratively when the line $n$ is calculated we use the next transition rules to generate the line $(n+1)$:

$$\left\{
\begin{array}{l}
b_{(n+1,j)} = (b_{(n,j+1)} + b_{(n,j)} + r_{(n,j)}) \mod 2 \\
r_{(n,j+1)} = \left\lfloor \frac{(b_{(n,j+1)} + b_{(n,j)} + r_{(n,j)})}{2} \right\rfloor
\end{array}
\right.
\qquad (\text{mod}2 \text{ is the modular function and } \lfloor \rfloor \text{ the integer part function})$$

Each cell, at position $(n, j)$ is represented by the couple $(b_{(n,j)}, r_{(n,j)})$ with $(r_{(n,j)})_{n \ge 0}$ the carry digits of the binary arithmetic addition: $2 * S_n + (S_n + 1) = 2^{1+g_n} S_{n+1}$
<figure><img src="image_1.png" /></figure>

So we have, for $j \ge e_n$ and with $r_{(n,e_n)} = 1$, the next transition equation from line n to line (n+1):

$$b_{(n,j+1)} + b_{(n,j)} + r_{(n,j)} = b_{(n+1,j)} + 2 * r_{(n,j+1)} \quad (1.5)$$

To generate the Syracuse automaton line (n+1), we begin arithmetic calculations at position $e_n$ of line n and $r_{(n,e_n)}$ is initialized to 1. Note that divisions by 2 correspond to position shifts in the cellular automata lines. We can, by the same transition rules, generate a cellular automata associated to the rational powers sequence $(S_0(3/2)^n)_{n \ge 0}$ but this time without any carry digits initializations. Here too, we see that the Syracuse automaton is a sort of perturbation (by the initialization of carry digits) of the $(3/2)$ rational powers automaton (Figure 1.1).

<figure><img src="image_2.png" /><figcaption>**Figure 1.1:** (left) Cellular automaton associated to rational powers sequence $(S_0(3/2)^n)_{n \ge 0}$; (right) Cellular automaton associated to Syracuse sequence $(S_n)_{n \ge 0}$. The two automata are generated with the same initialization $S_0$. The Syracuse Automaton can be seen as a perturbation of the rational powers sequence automaton by carry digit initialization at each line; we can see also the convergence of the Syracuse cellular automaton, to the cycle (1,2)</figcaption></figure>

**Remark 1.1:** Reciprocally every cellular automata using transition rules of (1.4) can be associated to an arithmetic sequence $(A_n)_{n \ge 0}$ where the binary expansion of $A_n$ is the nth line of the cellular automata. We will call such automata “(3/2) cellular automata”.

### 1.3. Gray code Cellular automaton

Another exotic way of expressing binary expansions is to use the binary gray coding [21] [22]. It is mainly used in electronics, because it allows the modification of only one bit at a time when a number is increased by one. If we express each line of a $(3/2)$ cellular automaton in the binary gray code instead of the standard binary expansion, we obtain a new cellular automaton composed of the cells $(g_{(n,j)})_{n,j \ge 0} \subset \mathbb{Z}^2$. Switching from standard binary coding $(b_{(n,j)})_{n,j \ge 0}$ to gray coding is done very easily by:

$$g_{(n,j)} = b_{(n,j+1)} \oplus b_{(n,j)} \quad (1.6)$$

where $\oplus$ is the exclusive disjunction (XOR operator) (Figure 1.2). Here as the XOR operator is not arithmetic, it is difficult to identify transition arithmetic rules for the new gray code
cellular automaton. In (Table 1.1) we list all the possible cases of transition between line n and (n+1) cells for Binary automaton and for gray code automaton.

<table><caption>**Table 1.1:** Syracuse CA: switching from standard binary expansion to Gray coding for all possible transition cases from n line to (n+1) line. Some configurations are forbidden in the Gray coding CA (Remark1.2).</caption><thead><tr><th>Binary automaton transition cases</th><th>Gray code automaton transition cases</th></tr></thead><tbody><tr><td>...</td><td>...</td></tr><tr><td>b<sub>(n,j+2)</sub> r<sub>(n,j+2)</sub> b<sub>(n,j+1)</sub> r<sub>(n,j+1)</sub> b<sub>(n,j)</sub> r<sub>(n,j)</sub>...</td><td>g<sub>(n,j+1)</sub> r<sub>(n,j+1)</sub> g<sub>(n,j)</sub> r<sub>(n,j)</sub>...</td></tr><tr><td>...</td><td>...</td></tr><tr><td>b<sub>(n+1,j+1)</sub> r<sub>(n+1,j+1)</sub> b<sub>(n+1,j)</sub> r<sub>(n+1,j)</sub>...</td><td>g<sub>(n+1,j)</sub> r<sub>(n+1,j)</sub>...</td></tr><tr><td>0<sup>0</sup> 0<sup>0</sup> 0<sup>r<sub>(n,j)</sub></sup></td><td>0<sup>0</sup> 0<sup>r<sub>(n,j)</sub></sup></td></tr><tr><td>0 r<sub>(n,j)</sub></td><td>r<sub>(n,j)</sub></td></tr><tr><td>0<sup>0</sup> 0<sup>r<sub>(n,j)</sub></sup> 1<sup>r<sub>(n,j)</sub></sup></td><td>0<sup>r<sub>(n,j)</sub></sup> 1<sup>r<sub>(n,j)</sub></sup></td></tr><tr><td>r<sub>(n,j)</sub> (1 - r<sub>(n,j)</sub>)</td><td>1</td></tr><tr><td>0<sup>r<sub>(n,j)</sub></sup> 1<sup>r<sub>(n,j)</sub></sup> 0<sup>r<sub>(n,j)</sub></sup></td><td>1<sup>r<sub>(n,j)</sub></sup> 1<sup>r<sub>(n,j)</sub></sup></td></tr><tr><td>(1 - r<sub>(n,j)</sub>) (1 - r<sub>(n,j)</sub>)</td><td>0</td></tr><tr><td>0<sup>1</sup> 1<sup>1</sup> 1<sup>r<sub>(n,j)</sub></sup></td><td>1<sup>1</sup> 0<sup>r<sub>(n,j)</sub></sup></td></tr><tr><td>0 (1 - r<sub>(n,j)</sub>)</td><td>(1 - r<sub>(n,j)</sub>)</td></tr><tr><td>1<sup>0</sup> 0<sup>0</sup> 0<sup>r<sub>(n,j)</sub></sup></td><td>1<sup>0</sup> 0<sup>r<sub>(n,j)</sub></sup></td></tr><tr><td>1 r<sub>(n,j)</sub></td><td>(1 - r<sub>(n,j)</sub>)</td></tr><tr><td>1<sup>r<sub>(n,j)</sub></sup> 0<sup>r<sub>(n,j)</sub></sup> 1<sup>r<sub>(n,j)</sub></sup></td><td>1<sup>r<sub>(n,j)</sub></sup> 1<sup>r<sub>(n,j)</sub></sup></td></tr><tr><td>(1 - r<sub>(n,j)</sub>) (1 - r<sub>(n,j)</sub>)</td><td>0</td></tr><tr><td>1<sup>1</sup> 1<sup>r<sub>(n,j)</sub></sup> 0<sup>r<sub>(n,j)</sub></sup></td><td>0<sup>r<sub>(n,j)</sub></sup> 1<sup>r<sub>(n,j)</sub></sup></td></tr><tr><td>r<sub>(n,j)</sub> (1 - r<sub>(n,j)</sub>)</td><td>1</td></tr><tr><td>1<sup>1</sup> 1<sup>1</sup> 1<sup>r<sub>(n,j)</sub></sup></td><td>1<sup>0</sup> 0<sup>r<sub>(n,j)</sub></sup></td></tr><tr><td>1 r<sub>(n,j)</sub></td><td>(1 - r<sub>(n,j)</sub>)</td></tr></tbody></table>

<figure><img src="image_3.png" /><figcaption>**Figure 1.2:** Cellular automaton associated to Syracuse sequence $(2*S_n)_{n \ge 0}$ expressed (left) in binary expansion and (right) in gray code. The multiplication by two allows visualizing the right border of the automaton. The automaton in gray code brings out an interesting tree structure.</figcaption></figure>

**Remark 1.2** In (Table 1.1), In the Gray code CA, when $g_{(n,j)} = 1$ we have either:

$$g_{(n,j+1)} = 0 \text{ and } g_{(n+1,j)} = 1 \text{ or } g_{(n,j+1)} = 1 \text{ and } g_{(n+1,j)} = 0$$

<table><thead><tr><th>Forbidden case when g<sub>(n,j)</sub> = 1</th><th>Authorized cases when g<sub>(n,j)</sub> = 1</th></tr></thead><tbody><tr><td>■ ■</td><td>□ ■ or ■ ■</td></tr><tr><td>■</td><td>■ ■</td></tr></tbody></table>

So when Gray code cellular automata are traversed from top to bottom the cells with values 1 extend only either to the left or to the bottom. This clearly explains why these automata have a tree structure with branches bifurcating only upwards. More over all the branches seem to converge towards the left edge of the automaton to form a single trunk. This is exactly what the Syracuse conjecture states and this is our main result:
**Theorem 1.1 (Main result)** For all (3x+1) Syracuse sequences $(S_n)_{n \ge 0}$, all "branches" of its associated Gray code CA, end up merging after a finite number of iterations. As a consequence, the Syracuse Conjecture is true.

In section 2 we explore links between Syracuse sequences and the Sturmian properties of their associated (3/2) powers sequences. We establish that Syracuse sequences are perturbations of (3/2) powers sequences which always modifies their associated Sturmian words. In section 3, we define Branch sequences. We show that each of them can be associated to a "branch" in the "tree" of a (3/2) cellular automata and vice versa. Finally we prove that Syracuse sequences 3x+1 (but not (3x-1) sequences) are Branch sequences and we show that the left and the right borders, of their associated CA, are "branches". In section 4, we consider two "branches" of the same Branch sequence and we show, by using section 2 results about Sturmian words, that the two "branches" can't be infinitely disjoint. Applied to the Syracuse sequence this establishes the Syracuse Conjecture.

## 2. Sturmian words, (3/2) Powers sequences and Syracuse sequences

Let $(A_n)_{n \ge 0}$ be a (3/2) powers sequence $(A_n = S_0(3/2)^n)_{n \ge 0}$, initialized by a given odd positive integer $S_0$. If we pass to logarithm in base 2 we obtain for any $n \ge 0$:

$$ \log_2(A_n) = n \cdot \log_2\left(\frac{3}{2}\right) + \log_2(S_0) $$

This constitutes what is called "a non-homogeneous Beatty sequence" [16][19]

The difference sequence $(a_n)_{n \ge 0}$ defined by:

$$ \begin{aligned} a_n &= [\log_2(A_{n+1})] - [\log_2(A_n)] \\ &= [(n+1) \cdot \log_2\left(\frac{3}{2}\right) + \log_2(S_0)] - [n \cdot \log_2\left(\frac{3}{2}\right) + \log_2(S_0)] \quad (2.1) \\ &= [(n+1) \cdot \log_2\left(\frac{3}{2}\right) + \{\log_2(S_0)\}] - [n \cdot \log_2\left(\frac{3}{2}\right) + \{\log_2(S_0)\}] \quad ({x}) \text{ is the fractional part of x and } [x] \text{ its integer part}) \end{aligned} $$

Forms a binary word and, and more interesting, a Sturmian word with irrational slope $\log_2(\frac{3}{2})$ and intercept $\log_2(S_0)$ [16][17] (the intercept can be restricted to its value modulo 1). Sturmian words with irrational slope form a family of non-periodic infinite words with the lowest complexity; they have been extensively studied in Number theory, Combinatorics, and Symbolic dynamics [16][17][18][19][20]. They have many equivalents definitions, for example it can be obtained by coding the sequence of cuts in an integer lattice over the positive quadrant of $\mathbb{R}^2$ made by a line of irrational slope [16].

In our case the sturmian word $(a_n)_{n \ge 0}$ will be identified to the left edge of the (3/2) powers automaton associated to $(A_n)_{n \ge 0}$ (Theorem 2.1).

Now consider $(S_n)_{n \ge 0}$ to be the sy@cuse sequence defined by the arithmetic formulation (1.2), (1.3) and initialized with the same $S_0$:

$$ \left\{ \begin{array}{l} S_n = \left( \frac{3^n}{2^{n+e_n}} \right) (S_0 + \Sigma_n) \\ \Sigma_n = \sum_{j=0}^{n-1} \frac{2^{j+e_j}}{3^{j+1}}, e_n = \sum_{j=0}^{n-1} g_j \\ g_0 = e_0 = 0 \text{ and } g_n = v_2 \left( \frac{3S_n + 1}{2} \right) \end{array} \right. $$

Incidentally we note that $(\Sigma_n)_{n \ge 0}$ is a positive strictly growing sequence. Again, If we pass to logarithm in base 2, we obtain, for any $n \ge 0$:
$$ \log_2(2^{e_n}S_n) = n \cdot \log_2\left(\frac{3}{2}\right) + \log_2(S_0) + \log_2\left(1 + \frac{\Sigma_n}{S_0}\right) $$

We define the sequence of difference $(b_n)_{n \ge 0}$:

$$ \begin{aligned} b_n &= \left|\log_2(2^{e_{n+1}}S_{n+1})\right| - \left|\log_2(2^{e_n}S_n)\right| \\ &= \left|\left(n+1\right)\log_2\left(\frac{3}{2}\right) + \log_2(S_0 + \Sigma_{n+1})\right| - \left|\left[n\log_2\left(\frac{3}{2}\right) + \log_2(S_0 + \Sigma_n)\right]\right| \end{aligned} \quad (2,2) $$

Again $(b_n)_{n \ge 0}$ is binary word because:

$$ \begin{aligned} \log_2(S_0 + \Sigma_{n+1}) - \log_2(S_0 + \Sigma_n) &= \log_2\left(1 + \frac{\Sigma_{n+1}}{S_0}\right) - \log_2\left(1 + \frac{\Sigma_n}{S_0}\right) = \log_2\left(1 + \frac{1}{3S_n}\right) \\ &\le 1 - \log_2\left(\frac{3}{2}\right) \quad (\text{because } S_n \ge 1 \ \forall n \ge 0) \end{aligned} $$

so

$$ \begin{aligned} 0 \le b_n \le & \left| \left(n + 1\right)\log_2\left(\frac{3}{2}\right) + \log_2(S_0 + \Sigma_n) + 1 - \log_2\left(\frac{3}{2}\right) \right| - \left| n\log_2\left(\frac{3}{2}\right) + \log_2(S_0 + \Sigma_n) \right| \\ \text{and } 0 \le b_n \le & \left| n\log_2\left(\frac{3}{2}\right) + \log_2(S_0 + \Sigma_n) + 1 \right| - \left| n\log_2\left(\frac{3}{2}\right) + \log_2(S_0 + \Sigma_n) \right| = 1 \end{aligned} $$

$(b_n)_{n \ge 0}$ is a continual perturbation of the Strumian word $(a_n)_{n \ge 0}$ as, at each step $n$, the intercept $\log_2(S_0)$ is modified to $\log_2(S_0 + \Sigma_n)$ and $\log_2(S_0 + \Sigma_{n+1})$ $(b_n)_{n \ge 0}$ will be called Perturbed Sturmian word). As explained below in (Lemma 2.1) (and with more details in [16]), this implies that, even with the same $S_0$, the two infinite binary words $(a_n)_{n \ge 0}$ and $(b_n)_{n \ge 0}$ are necessarily different (Theorem 2.1).

**Lemma 2.1** *Any change modulo 1 in the intercept of a non-periodic Sturmian word will necessarily affects the infinite word.*

**Proof.** This is a known result of Sturmian sequences, see for example (Proposition 2.1.20) [16]: if $S_{(\alpha, \rho_1)}$ and $S_{(\alpha, \rho_2)}$ are two sturmian words with the same slope $0 < \alpha < 1$, and intercepts $\rho_1$ and $\rho_2$ then:

$$ \begin{gathered} \rho_1 < \rho_2 \Leftrightarrow S_{(\alpha, \rho_1)} < S_{(\alpha, \rho_2)} \\ \text{(With } S_{(\alpha, \rho_1)} < S_{(\alpha, \rho_2)} \text{ in the sense of lexicographical order)} \end{gathered} $$

<figure><img src="image_4.png" /></figure>

**Corollary 2.1** *With the same notations from above; we have always $(a_n)_{n \ge 0} \ne (b_n)_{n \ge 0}$. More precisely $(a_n)_{n \ge 0} < (b_n)_{n \ge 0}$ for lexicographical order.*

**Proof** it's a special case of (Lemma 2.1) but we will detail the proof.

Suppose we had: $(a_n)_{n \ge 0} = (b_n)_{n \ge 0}$ i.e. $\forall n \ge 0$:

$$ \left| \left(n + 1\right)\log_2\left(\frac{3}{2}\right) + \log_2(S_0) \right| - \left| n\log_2\left(\frac{3}{2}\right) + \log_2(S_0) \right| = \left| \left(n + 1\right)\log_2\left(\frac{3}{2}\right) + \log_2(S_0 + \Sigma_{n+1}) \right| - \left| n\log_2\left(\frac{3}{2}\right) + \log_2(S_0 + \Sigma_n) \right| $$

Since the two sequences have the same initialization (as $\Sigma_0 = 0$), we can say:
$$ \forall n \ge 0 \left[ n\log_2\left(\frac{3}{2}\right) + \log_2(S_0) \right] = \left[ n\log_2\left(\frac{3}{2}\right) + \log_2(S_0 + \Sigma_n) \right] \quad (2.3) $$

We have also:

$$ 0 < \log_2(S_0 + \Sigma_n) - \log_2(S_0) < 1 \quad (2.4) $$

Indeed otherwise then:

$$ \left[ n\log_2\left(\frac{3}{2}\right) + \log_2(S_0) \right] < \left[ n\log_2\left(\frac{3}{2}\right) + \log_2(S_0 + \Sigma_n) \right] $$

which contradict (2.3). From (2.4) we can deduce that $(\Sigma_n)_{n \ge 0}$ is convergent, as it is a growing sequence, and:

$$ \lim_{n \to \infty} \Sigma_n = \Sigma < S_0 \quad (2.5) $$

We have then, according to (2.3) and (2.4): $\forall n \ge 0$

$$ \begin{aligned} \left[ n\log_2\left(\frac{3}{2}\right) + \{\log_2(S_0 + \Sigma_n)\} \right] - \left[ n\log_2\left(\frac{3}{2}\right) + \{\log_2(S_0)\} \right] &= \\ & \quad [\log_2(S_0)] - [\log_2(S_0 + \Sigma_n)] = 0 \quad \text{or} \quad -1 \end{aligned} \quad (2.6) $$

If we suppose we have for some $n \ge 0$:

$$ \begin{aligned} \left[ n\log_2\left(\frac{3}{2}\right) + \{\log_2(S_0 + \Sigma_n)\} \right] - \left[ n\log_2\left(\frac{3}{2}\right) + \{\log_2(S_0)\} \right] &= \\ & \quad [\log_2(S_0)] - [\log_2(S_0 + \Sigma_n)] = -1 \end{aligned} \quad (2.7) $$

then perforce:

$$ \{\log_2(S_0 + \Sigma_n)\} < \{\log_2(S_0)\} $$

because otherwise it will contradict (2.4):

$$ \begin{cases} \{\log_2(S_0 + \Sigma_n)\} \ge \{\log_2(S_0)\} \\ [\log_2(S_0 + \Sigma_n)] - [\log_2(S_0)] = 1 \end{cases} \Rightarrow \log_2(S_0 + \Sigma_n) - \log_2(S_0) \ge 1 $$

we notice that we have (2.7) is verified for all indexes $m \ge n$:

$$ \forall m \ge n: \quad \left[ m\log_2\left(\frac{3}{2}\right) + \{\log_2(S_0 + \Sigma_m)\} \right] - \left[ m\log_2\left(\frac{3}{2}\right) + \{\log_2(S_0)\} \right] = -1 \quad (2.8) $$

because of (2.6) and :

$$ [\log_2(S_0)] - [\log_2(S_0 + \Sigma_m)] \le [\log_2(S_0)] - [\log_2(S_0 + \Sigma_n)] = -1 $$

equation (2.8) involve:

$$ \forall m \ge n: \quad 1 - \{\log_2(S_0 + \Sigma_m)\} \le \{m\log_2\left(\frac{3}{2}\right)\} < 1 - \{\log_2(S_0)\} $$

And according to (2.5) we can deduce that:

$$ \exists N \ge 0, \forall m \ge N: 0 < 1 - \{\log_2(S_0 + \Sigma)\} \le \{m\log_2\left(\frac{3}{2}\right)\} < 1 - \{\log_2(S_0)\} < 1 $$
This is absurd because it contradict a fundamental result of rational powers sequences [16][12][10] :

$$ \left( \left\{ n \log_2 \left( \frac{3}{2} \right) \right\} \right)_{n \ge 0} \text{ is dense in the interval } [0,1[. \qquad (2.9) $$

So in conclusion (2.3) imply that $\forall n \ge 0$:

$$ \left[ n \log_2 \left( \frac{3}{2} \right) + \{\log_2(S_0)\} \right] = \left[ n \log_2 \left( \frac{3}{2} \right) + \{\log_2(S_0 + \Sigma_n)\} \right] \quad (2.10) $$

Now from (2.10) and, again, by using (2.9), we have $\forall k \ge 0, \exists n_k \ge k$ such that:

$$ 1 - \{\log_2(S_0 + \Sigma_k)\} \le \{n_k \log_2\left(\frac{3}{2}\right)\} < 1 - \{\log_2(S_0)\} $$

(there exists $n_k \ge k$ because the interval $]1 - \{\log_2(S_0 + \Sigma_k)\}, 1 - \{\log_2(S_0)\}$] have infinite possible values for $\{n_k \log_2\left(\frac{3}{2}\right)\}$)

Then:

$$ \{n_k \log_2 \left( \frac{3}{2} \right)\} + \{\log_2(S_0)\} \le 1 \le \{n_k \log_2 \left( \frac{3}{2} \right)\} + \{\log_2(S_0 + \Sigma_k)\} $$

Which means that $\forall k \ge 0$, there exists $n_k \ge k$ such that:

$$ \left[ n_k \log_2 \left( \frac{3}{2} \right) + \log_2(S_0 + \Sigma_k) \right] = \left[ n_k \log_2 \left( \frac{3}{2} \right) + \log_2(S_0) \right] + 1 $$

We observe that $\forall k' \ge k$ we have $\Sigma_{k'} \ge \Sigma_k$ and of course:

$$ \left[ n_k \log_2 \left( \frac{3}{2} \right) + \log_2(S_0 + \Sigma_{k'}) \right] > \left[ n_k \log_2 \left( \frac{3}{2} \right) + \log_2(S_0) \right] $$

in particular we have for $k' = n_k$:

$$ \left[ n_k \log_2 \left( \frac{3}{2} \right) + \log_2(S_0 + \Sigma_{n_k}) \right] > \left[ n_k \log_2 \left( \frac{3}{2} \right) + \log_2(S_0) \right] $$

Which contradicts (2.3) and we have always : $(a_n)_{n \ge 0} \ne (b_n)_{n \ge 0}$

Suppose now n the smallest integer for which $(a_n)_{n \ge 0} \ne (b_n)_{n \ge 0}$ then

$$ \forall k \le n, \left[ k \log_2 \left( \frac{3}{2} \right) + \log_2(S_0) \right] = \left[ k \log_2 \left( \frac{3}{2} \right) + \log_2(S_0 + \Sigma_k) \right] $$

and we have :

$$ \begin{align*} b_n &= \left[ (n+1)\log_2\left(\frac{3}{2}\right) + \log_2(S_0 + \Sigma_{n+1}) \right] - \left[ n\log_2\left(\frac{3}{2}\right) + \log_2(S_0 + \Sigma_n) \right] \\ &= \left[ (n+1)\log_2\left(\frac{3}{2}\right) + \log_2(S_0 + \Sigma_{n+1}) \right] - \left[ n\log_2\left(\frac{3}{2}\right) + \log_2(S_0) \right] \\ &\ge \left[ (n+1)\log_2\left(\frac{3}{2}\right) + \log_2(S_0) \right] - \left[ n\log_2\left(\frac{3}{2}\right) + \log_2(S_0) \right] = a_n \end{align*} $$
Finally we have always: $(a_n)_{n \ge 0} < (b_n)_{n \ge 0}$

<figure><img src="image_5.png" /></figure>

**Lemma 2.2** The left border of the binary CA associated to the rational powers sequence $(A_n = S_0(3/2)^n)_{n \ge 0}$ can be identified to the sturmian word $(a_n)_{n \ge 0}$. The left border of the binary CA associated to Syracuse sequence $(S_n)_{n \ge 0}$ is identified to the perturbed Sturmian word $(b_n)_{n \ge 0}$.

**Proof.** In the CA associated to the rational powers sequence$(A_n = S_0(3/2)^n)_{n \ge 0}$ we have $a_n = [\log_2(A_{n+1})] - [\log_2(A_n)]$ is the difference of digit number between integer parts, of binary expansion of $A_{n+1}$ and $A_n$. So $a_n = 1$ corresponds to a shift to the left, at the nth line of the CA left-border because: $[\log_2(A_{n+1})] = [\log_2(A_n)] + 1$ and when $a_n = 0$ then $[\log_2(A_{n+1})] = [\log_2(A_n)]$ and $A_{n+1}$ and $A_n$ have the same number of digits in their integer part (no shift). In the same manner $b_n = [\log_2(2^{e_{n+1}}S_{n+1})] - [\log_2(2^{e_n}S_n)]$ correspond, when equal to 1, to a shift of the left-border of the Syracuse cellular automaton to the left.

<figure><img src="image_6.png" /></figure>

**Theorem 2.1** The left border of the CA associated to a Syracuse sequence $(S_n)_{n \ge 0}$ is always different to the left border associated to the rational power sequence $(S_0(3/2)^n)_{n \ge 0}$.

**Proof.** According to (Lemma 2.2): the first border is associated to a Perturbed Sturmian word $(b_n)_{n \ge 0}$ and the second border is associated to a Sturmian word $(a_n)_{n \ge 0}$. (Corollary 2.1) shows that the two infinite words are necessarily different.

<figure><img src="image_7.png" /></figure>

**3. Branch sequences and Gray code automaton “branches”**

One can consider generalizations for Syracuse sequences in several ways. We choose the next formulation: $(R_n)_{n \ge 0} = (R_n^1, R_n^2)_{n \ge 0}$, a pair of sequences called “Branch sequence”. They will be later associated to the gray code Syracuse cellular automaton “branches” (figure 1.2). It will also be shown that Syracuse sequences are special cases of Branch sequences.

**Definition 3.1 (Branch sequence)** $(R_n)_{n \ge 0} = (R_n^1, R_n^2)_{n \ge 0}$ is defined iteratively as follows: Let $R_0^1$ be a positive integer such that $R_0^1 \equiv 1 \text{ or } 2 \text{ mod } 4$ i.e. its binary expansion begin with $(\cdots 10)_2$ or $(\cdots 01)_2$. Then $R_0^1$ has one of the four next possible binary expansions:

$$ \left( \underbrace{\overbrace{R_0^2}^{\frac{4^{k_0-1}}{3}} \quad \overbrace{\overbrace{010 \cdots 101}^{\vdots \vdots \vdots}}^{\vdots \vdots \vdots}}_{R_0^1} \quad \right)_2 \quad \left( \underbrace{\overbrace{R_0^2}^{\frac{4^{k_0-1}}{3}} \quad \overbrace{\overbrace{010 \cdots 010}^{\vdots \vdots \vdots}}^{\vdots \vdots \vdots}}_{R_0^1} \quad \right)_2 \\ \left( \underbrace{\overbrace{R_0^2}^{\frac{4^{k_0-1}}{3}} \quad \overbrace{\overbrace{101 \cdots 101}^{\vdots \vdots \vdots}}^{\vdots \vdots \vdots}}_{R_0^1} \quad \right)_2 \quad \left( \underbrace{\overbrace{R_0^2}^{\frac{4^{k_0-1}}{3}} \quad \overbrace{\overbrace{101 \cdots 010}^{\vdots \vdots \vdots}}^{\vdots \vdots \vdots}}_{R_0^1} \quad \right)_2 $$

This determines $R_0^2$ and we have: $R_0^2 \equiv 1 \text{ or } 6 \text{ mod } 8$ with:
At each iteration, the choice of $\delta_n$ may be random. But we can obtain a Syracuse 3x+1 sequence, if we take $\delta_n = 1 \ \forall n \ge 0$ (lemme3.1).

**Lemma 3.1** In a Branch sequence $(R_n)_{n \ge 0} = (R_n^1, R_n^2)_{n \ge 0}$, if we take $\delta_n = 1 \ \forall n \ge 0$, then the sequence $(R_n^1)_{n \ge 0}$ is identified to the Syracuse sequence 3x+1(multiplied by 2):
$(2 \cdot S_n)_{n \ge 0}$ initialized with $R_0^1$ if $R_0^1 \equiv 1 \mod 4$ or $2 \cdot R_0^1$ if $R_0^1 \equiv 2 \mod 4$.

**Proof.** Let consider the branch sequence $(R_n)_{n \ge 0} = (R_n^1, R_n^2)_{n \ge 0}$ with $\delta_n = 1, \forall n \ge 0$, and the Syracuse sequence 3x+1 $(S_n)_{n \ge 0}$ as defined in (1.2) and initialized by:

$$S_0 = \frac{R_0^1}{2} \text{ if } R_0^1 \equiv 2 \mod 4 \text{ and } S_0 = R_0^1 \text{ if } R_0^1 \equiv 1 \mod 4.$$

Suppose that for:

$$n \ge 0, \quad \text{we have: } S_n = \frac{R_n^1}{2} \text{ and } R_n^1 \equiv 2 \mod 4$$

As $S_{n+1} = \frac{3S_n+1}{2^{1+g_n}}$ with $g_n = v_2(\frac{3S_n+1}{2})$, we had, (3.2), the two next possibilities for $S_{n+1}$:

$$S_{n+1} = \begin{cases} \frac{3R_n^1}{2} + 1 & = \frac{4^{k_n} 3R_n^2 + 1}{2g_n} = \frac{4^{k_n}}{2g_n} R_{n+1}^1 & \text{with } R_n^1 \equiv 2 \mod 4 \text{ and } R_n^2 \equiv 1 \mod 8 \\ \frac{3R_n^1}{2} + 1 & = \frac{4^{k_n} \frac{3R_n^2}{2} + 1}{2g_n} = \frac{4^{k_n}}{2g_{n+1}} R_{n+1}^1 & \text{with } R_n^1 \equiv 2 \mod 4 \text{ and } R_n^2 \equiv 6 \mod 8 \end{cases}$$

We note that since $\delta_n = 1 \ \forall n \ge 0$, for the two cases $R_{n+1}^1 \equiv 2 \mod 4$ (3.1):

Finally we have:

$$\left\{ \begin{array}{ll} S_{n+1} = \frac{R_{n+1}^1}{2} & \text{and } g_n = 2k_n + 1 \text{ if } R_n \equiv 1 \mod 8 \\ S_{n+1} = \frac{R_{n+1}^1}{2} & \text{and } g_n = 2k_n \text{ if } R_n \equiv 6 \mod 8 \end{array} \right.$$

<figure><img src="image_8.png" /></figure>

**Remark 3.2** Unfortunately, as we can see in (figure 3.1), the Syracuse sequence (3x-1) can't be identified, in the same manner, to a Branch sequence. This may explain why we find non trivial cycles in those sequences.

<figure><img src="image_9.png" /><figcaption>**Figure 3.1:** Branches in the binary cellular automaton (left) and its associated Gray code automaton associated to 3x-1 Syracuse sequence (multiplied by 2). Despite it contain Branches sequences it is not a Branch sequence.</figcaption></figure>
Branch sequences $(R_n)_{n \ge 0}$ can be associated to the “branches”, observed in the Gray code (3/2) CA (Figure 1.2) and vice-versa.

**Lemma 3.2** The right border of the CA associated to a Branch sequence $(R_n^1)_{n \ge 0}$ is a “branch” of its associated Gray code CA. Conversely, every “branch” in a Gray code CA (associated to a (3/2) cellular automata) is the right border of a Branch sequence.

**Proof**

Let $(R_n)_{n \ge 0}$ be a Branch sequence. It is more convenient to treat this in the binary expansion CA and Gray code CA associated to $(R_n^1)_{n \ge 0}$. We have four possible case for $R_n^1$:

<table><thead><tr><th>Binary expansion CA of the right border</th><th>Corresponding Gray code CA right border</th></tr></thead><tbody><tr><td>R<sup>2</sup><sub>n</sub>≡1mod8<br>↓<sub>δn</sub> <sup>4k<sub>n-1</sub></sup>&frasl;<sub>3</sub> ↓<sub>δn</sub><br><span style="text-decoration: overline;">... 001</span> <span style="text-decoration: overline;">0101 ... 01</span><br>R<sup>1</sup><sub>n</sub>≡1mo<br><span style="text-decoration: overline;">... δn(1 - δn)</span> (1 - δn) ... (1 - δn)<br>R<sup>1</sup><sub>n+1</sub>≡0 or 1mod4</td><td>R<sup>2</sup><sub>n</sub><br><span style="text-decoration: overline;">... □■</span> <span style="text-decoration: overline;">■ ... ■□</span><br>R<sup>1</sup><sub>n</sub><br><span style="text-decoration: overline;">... ■</span> □ ... □□</td></tr><tr><td>R<sup>2</sup><sub>n</sub>≡1mod8<br>↓<sub>δn</sub> 2<sup>4k<sub>n-1</sub></sup>&frasl;<sub>3</sub> ↓<sub>δn</sub><br><span style="text-decoration: overline;">... 001</span> <span style="text-decoration: overline;">0101 ... 10</span><br>R<sup>1</sup><sub>n</sub>≡2mod4<br><span style="text-decoration: overline;">... δn(1 - δn)</span> (1 - δn) ... (1 - δn)<br>R<sup>1</sup><sub>n+1</sub>≡0 or 1mod4</td><td>R<sup>2</sup><sub>n</sub><br><span style="text-decoration: overline;">... □■</span> <span style="text-decoration: overline;">■ ... ■□</span><br>R<sup>1</sup><sub>n</sub><br><span style="text-decoration: overline;">... ■</span> □ ... □□</td></tr><tr><td>R<sup>2</sup><sub>n</sub>≡6mod8<br>↓<sub>δn</sub> <sup>4k<sub>n-1</sub></sup>&frasl;<sub>3</sub> ↓<sub>δn</sub><br><span style="text-decoration: overline;">... 110</span> <span style="text-decoration: overline;">101 ... 01</span><br>R<sup>1</sup><sub>n</sub>≡1mod4<br><span style="text-decoration: overline;">... δn(1 - δn)</span> (1 - δn) ... (1 - δn)<br>R<sup>1</sup><sub>n+1</sub>≡0 or 1mod4</td><td>R<sup>2</sup><sub>n</sub><br><span style="text-decoration: overline;">... □■</span> <span style="text-decoration: overline;">■ ... ■□</span><br>R<sup>1</sup><sub>n</sub><br><span style="text-decoration: overline;">... ■</span> □ ... □□</td></tr><tr><td>R<sup>2</sup><sub>n</sub>≡6mod8<br>↓<sub>δn</sub> 2<sup>4k<sub>n-1</sub></sup>&frasl;<sub>3</sub> ↓<sub>δn</sub><br><span style="text-decoration: overline;">... 110</span> <span style="text-decoration: overline;">101 ... 10</span><br>R<sup>1</sup><sub>n</sub>≡2mod4<br><span style="text-decoration: overline;">... δn(1 - δn)</span> (1 - δn) ... (1 - δn)<br>R<sup>1</sup><sub>n+1</sub>≡0 or 1mod4</td><td>R<sup>2</sup><sub>n</sub><br><span style="text-decoration: overline;">... □■</span> <span style="text-decoration: overline;">■ ... ■□</span><br>R<sup>1</sup><sub>n</sub><br><span style="text-decoration: overline;">... ■</span> □ ... □□</td></tr></tbody></table>

For all cases we have the same situation for the right border associated to $(R_n^1)_{n \ge 0}$: a horizontal portion of a “branch” from the beginning of $R_n^1$ which end at the beginning of $R_n^2$ and go down to the beginning of $R_{n+1}^1$. If $k_n=0$ then the “Branch” goes simply down to $R_{n+1}^1$. So the right border of the Code gray automaton is a “Branch” (black squares) without downward bifurcations. Upward bifurcations are possible and are indicators of the fusion of two branches (figure 3.2).

Reciprocally if we consider a “branch” in the tree of the Gray code (3/2) cellular automata associated to an arithmetic sequence $(B_n)_{n \ge 0}$; and if we take the portion of this “Branch” in the n-line then it will always, due to transition rules (Remark 1.1), be of the form:

<figure><img src="image_10.png" /></figure>
And it, consequently, corresponds to one of the four possible binary expansions of $R_n^1$ and $R_n^2$. So $B_n$ and $B_{n+1}$ are consecutive terms of a Branch sequence and the branch is its right border. ■

**Lemma 3.3** The left border of a Gray code cellular automaton associated to a Branch sequence $(R_n^1)_{n \ge 0}$ is a “Branch” (figure3.2) and it is associated to the Branch sequence $(L_n)_{n \ge 0} = (L_n^1, L_n^2)_{n \ge 0}$ with:

$$ \begin{array}{l} \forall n \ge 0, L_n^2 = 1 \quad \text{and} \quad L_n^1 = 1 + \delta_n = 1 \quad \text{or} \quad 2. \\ (\delta_n \text{ is the carry digit associated to } (L_n)_{n \ge 0}) \end{array} $$

**Proof** Let $(R_n)_{n \ge 0} = (R_n^1, R_n^2)_{n \ge 0}$ be a branch sequence then the left border is initialized with $L_0^1 = L_1^1 = (001)_2$ we have then 2 cases according to the carry digit $\delta_0$ given by the sequence $(R_n)_{n \ge 0}$:

<table><thead><tr><th>Binary expansion automata</th><th>Gray code automata</th></tr></thead><tbody><tr><td>$L_0^1=L_0^2 \underset{\delta_0}{\overset{\downarrow}{\Box}}$<br>$\overbrace{\cdots 001}^{R_0^1} \cdots\cdots\cdots$<br>$L_1^1 \overbrace{\cdots 00 \delta_0 (1 - \delta_0)}^{R_1^1} \cdots\cdots\cdots}$</td><td>$L_0^1=L_0^2 \underset{\delta_0=0}{\overset{\downarrow}{\Box}}$<br>$\overbrace{\cdots \Box \cdots \Box}^{L_1^1=L_1^1=1}$<br>$\overbrace{\cdots \Box \cdots \Box}^{R_1^1}$<br>or<br>$L_0^1=L_0^2 \underset{\delta_0=1}{\overset{\downarrow}{\Box}}$<br>$\overbrace{\cdots \Box \cdots \Box}^{L_1^2=1}$<br>$\overbrace{\cdots \Box \cdots \Box}^{L_1^1=2}$<br>$\overbrace{\Box \cdots \Box}^{R_1^1}$</td></tr></tbody></table>

So in the two cases we have again:

$$L_1^2 = 1 \quad \text{and} \quad L_1^1 = 1 \quad \text{or} \quad 2$$

depending on $\delta_0$, iteratively we have then:

$$\forall n \ge 0, L_n^2 = 1 \quad \text{and} \quad L_n^1 = 1 + \delta_n.$$

In another way, arithmetically this time, if $L_n^2 = 1$ then:

$$L_{n+1}^1 = \frac{3L_n^2 - 1}{2} + \delta_n \quad \text{as} \quad R_n^2 \equiv 1 \mod 8$$

So:

$$L_{n+1}^1 = 1 + \delta_n = 1 \quad \text{or} \quad 2$$

and:

$$\left\{ \begin{array}{l} \frac{4^{k_{n+1}-1}}{3} + 4^{k_{n+1}} L_{n+1}^2 \quad \text{with} \quad L_{n+1}^1 = 1 \quad \text{and} \quad k_{n+1} = 0 \\ \frac{4^{k_{n+1}-1}}{3} + 4^{k_{n+1}} \frac{L_{n+1}^2}{2} \quad \text{with} \quad L_{n+1}^1 = 2 \quad \text{and} \quad k_{n+1} = 1 \end{array} \right.$$

and again in the two case $L_{n+1}^2 = 1$.

**Remark 3.3** If for some $n \ge 0$ we have:

$$L_n^1 = R_n^1$$

and we have $(R_n)_{n \ge 0}$ a Syracuse sequence (multiplied by 2) then:
$$ \delta_m = 1 \forall m \ge n $$

and

$$ R_m^1 = 2, R_m^2 = 2 \forall m \ge n. $$

This is exactly the trivial cycle of a Syracuse sequence.

**Corollary 3.1** In Gray code cellular automata associated to a Syracuse sequence, the left border as well as the right border are “branches” in the “tree” of the Syracuse Gray code automata (figure 3.2).

**Proof.** It comes simply from the fact that Syracuse sequence is a Branch sequence (Lemma 3.1) and we apply (Lemma 3.2) and (Lemma 3.3) ■

<figure><img src="image_11.png" /><figcaption>**Figure 3.2** : Branch sequence (Syracuse 3x+1): some “branches” are represented in color: in the binary cellular automaton (left) and in its associated Gray code automaton(right). (in blue) the left border “branch”, (in green) a middle “branche” and (in red) the right border “branch”. We see clearly that the « branches » have no downward bifurcations only upward bifurcations are possible and are indicators of the fusion of two branches. The three “branches” finished by coalescing.</figcaption></figure>

**4. Final step, proof of Syracuse conjecture**

According to all above results, it is clear now that if, for every Syracuse CA, the left border and the right border end up joining after a finite number of iterations, then the Syracuse conjecture is verified.

**Definition 4.1** Let $(R_n)_{n \ge 0} = (R_n^1, R_n^2)_{n \ge 0}$ be a Branch sequence and let's consider a “branch” in its Gray code automaton as different from the right edge “branch”. This “branch” can be associated (lemma 3.2) to the another Branch sequence $(L_n)_{n \ge 0} = (L_n^1, L_n^2)_{n \ge 0}$ with $R_0^2 \ne L_0^2$. As long as we have $R_m^2 \ne L_m^2$ we say that the two Branch sequences are disjoint up to order $m$. However if there exists $m \ge 0$ such that $R_m^2 = L_m^2$ then $(R_n)_{n \ge 0}$ and $(L_n)_{n \ge 0}$ are said to be coalescent and in this case we have of course $L_n^2 = R_n^2$ and $L_n^1 = R_n^1 \forall n \ge m$ (because the two sequences are part of the same CA so $\delta_m$ will be the same for $R_m^2$ and $L_m^2$) (Table 4.1).
<figure><img src="image_12.png" /><figcaption>**Table 4.1** Examples of Disjoint branches (in the left) and coalescent ones (in the right) at n and (n+1) lines</figcaption></figure>

**Lemma 4.1** With (Definition 4.1) notations, we consider $(R_n)_{n \ge 0}$ and $(L_n)_{n \ge 0}$ two disjoint Branch sequences up to order m. Let's $(\delta_n^R)_{n \ge 0}$ be the sequence of parameters (initializing carry digit in each line) used in the calculations of $R_{n+1}^1$ from $R_n^2$ (3.1). Then any change in the sequence of parameters $(\delta_n^R)_{n \le m}$, up to order m, change the sequence $(R_n)_{n \le m}$ but does not affect the sequence $(L_n)_{n \le m}$.

**Proof** Since the two “branches” are disjoint we have necessarily for $0 \le n \le m$:

$$ 
\begin{cases} 
R_n^1 = 2^{K_n^1} * R_n^2 + P_n^1 & \text{with } K_n^1 \ge 0, P_n^1 \ge 0 \\ 
R_n^2 = 2^{K_n^2} * L_n^1 + P_n^2 & \text{with } K_n^2 > 0, P_n^1 > 0 \\ 
L_n^1 = 2^{K_n^3} * L_n^2 + P_n^3 & \text{with } K_n^3 \ge 0, P_n^3 \ge 0 
\end{cases} 
$$

because $R_n^2 \equiv 1 \text{ or } 6 \text{ mod } 8$ and $L_n^1 \equiv 1 \text{ or } 2 \text{ mod } 4$

For $0 \le n < m$ we have (3.1):

$$ R_{n+1}^1 = \begin{cases} \frac{3R_n^2}{2} + \delta_n^R & \text{if } R_n^2 \equiv 6 \text{ mod } 8 \\ \frac{3R_n^2 - 1}{2} + \delta_n^R & \text{if } R_n^2 \equiv 1 \text{ mod } 8 \end{cases} $$

$$ L_{n+1}^1 = \begin{cases} \frac{3L_n^2}{2} + \delta_n^L & \text{if } R_n^2 \equiv 6 \text{ mod } 8 \\ \frac{3L_n^2 - 1}{2} + \delta_n^L & \text{if } R_n^2 \equiv 1 \text{ mod } 8 \end{cases} $$

Suppose now that we changed $\delta_n^R$ to $\delta_n^{R'} = (1 - \delta_n^R)$ (since $\delta_n^R = 0 \text{ or } 1$), then $R_{n+1}^1$ is modified to:

$$ R_{n+1}^{1} = \begin{cases} \frac{3R_n^2}{2} + (1 - \delta_n^R) & \text{if } R_n^2 \equiv 6 \text{ mod } 8 \\ \frac{3R_n^2 - 1}{2} + (1 - \delta_n^R) & \text{if } R_n^2 \equiv 1 \text{ mod } 8 \end{cases} $$

In the cellular automata we have the next two possible cases:
<figure><img src="image_13.png" /></figure>

So $\delta_n^L$ doesn't change because $R_n^2 = 1 \text{ or } 6 \text{ mod } 8$ which absorb the carry digit $\delta_n^R$ or $\delta_n^{R'}$ and replace it by 0 at the third digit of $R_n^2$

<figure><img src="image_14.png" /><figcaption>**Figure 4.1** (left) Gray code CA associated to $S_0(\frac{3}{2})^n$ and (right) its perturbation by Syracuse sequence $(S_n)_{n \ge 0}$. The two left border must be different which imply the coalescence of all Syracuse CA "branches" (Lemma 4.2).</figcaption></figure>

**Lemma 4.2** Let $(S_n)_{n \ge 0}$ be a Syracuse sequence $3x+1$, then the left border of its CA can't be disjoint to the right border up to infinity. This proves the main result Theorem 1.1.

**Proof** $(S_n)_{n \ge 0}$ is a Branch sequence with : $\delta_n = 1 \forall n \ge 0$ (Lemma 3.1). Suppose we had, for an infinite order, the left border and right border are disjoint, we propose to replace $(\delta_n)_{n \ge 0}$ by $(\delta'_n)_{n \ge 0}$ with: $\forall n \ge 0 \delta'_n = r_{(n,e_n)}$ where $r_{(n,e_n)}$ is the carry digit (defined in (1.4)) and positioned at the $e_n$th digit of the binary expansion of $S_0(\frac{3}{2})^n$. The new constructed Branch sequence (called $(R_n)_{n \ge 0} = (R_n^1, R_n^2)_{n \ge 0}$ ) is then a "branch" in the Gray code associated to $(S_0(\frac{3}{2})^n)_{n \ge 0}$ because at each line we have the same initializing carry digits at position $e_n$. $(R_n)_{n \ge 0}$ is then a truncation (operated at positions $(e_n)_{n \ge 0}$) of the rational powers $(S_0(\frac{3}{2})^n)_{n \ge 0}$. So $(R_n)_{n \ge 0}$ and $(S_0(\frac{3}{2})^n)_{n \ge 0}$ own the same left border. According to (Lemma 4.2) the left border is not affected by changes in the right border. So the left border associated to $(S_n)_{n \ge 0}$ is identical to the one associated to $(S_0(\frac{3}{2})^n)_{n \ge 0}$ which
contradicts the assertion of the (Theorem 2.1). In conclusion the left border and the right one,
in a Syracuse sequences CA finish always by coalescing after a finite number of iterations
(Figure 4.1). For any other intermediate “branch” between right and left border it will
obviously join them after a finite number of iterations too. After coalescence (at for example
order m), according to (lemma 3.3) we have: $\forall n \ge m$, $\delta_n = 1, R_n^1 = 2$ and $R_n^2 = 1$, this is
exactly what Syracuse conjecture stated: Syracuse sequences finish always by the cycle (1,2)
and this establish (Theorem 1.1).

<figure><img src="image_15.png" /></figure>

References

[1] J. Lagarias, *The $3x+1$ problem and its generalizations*, Amer. Math. Monthly 92, no. 1, 3–23 (1985).

[2] I. Korec, *A density estimate for the $3x+1$ problem*, Math. Slovaca, 44 no. 1, 85-89 (1994).

[3] G.J. Wirsching, *The Dynamical System Generated by the $3n + 1$ Function*, LectureNotes in Mathematics, Vol. 1681, Springer Verlag, Berlin, (1998).

[4] T. Oliveira e Silva, *Empirical verification of the $3x+1$ and related conjectures*, *The ultimate challenge: the $3x+1$ problem*, 189207, Amer. Math. Soc., Providence, RI, (2010).

[5] J.L. Simons and B.M.M. deWeger, *Theoretical and computational bounds for $m$-cycles of the $3n + 1$ problem*. Acta arithmetica 117 pp. 51–70 (2005).

[6] R.E. Crandall, *On the $3x + 1$ problem*, Mathematics of Computation 32, pp.1281–1292 (1978).

[7] J.-P. Allouche, *Sur la conjecture de "Syracuse-Kakutani-Collatz"*, Séminaire de Théorie des Nombres, 1978–1979, Exp. No. 9, 15 pp., CNRS, Talence, (1979).

[8] R. Terras, *A stopping time problem on the positive integers*, Acta Arith. 30, 241–252 (1976).

[9] T. Tao. *Almost all Orbits of the Collatz Map Attain Almost Bounded Values*. arXiv preprint arXiv:1909.03562, (2019).

[10] L.Kuipers and H. Niederreiter, Uniform Distribution of Sequences, J. Wiley and Sons, (1974).

[11] Y. Bugeaud, *Linear mod one transformations and the distribution of fractional parts {ξ(p/q)n}. Acta Arith. 114, 301–311 (2004).*

[12] L. Flatto, J.C. Lagarias, A.D. Pollington, *On the range of fractional parts {ξ(p/q)n}, Acta Arith. 70, 125–147 (1995)*

[13] K. Mahler, “*An unsolved problem on the powers of 3/2*”. J. Austral. Math. Soc. 8, 313–321 (1968)

[14] A. Dubickas, “*Powers of a rational number modulo 1 cannot lie in a small interval*”, ACTA ARITHMETICA 137.3 (2009)

[15] I.M. Niven, “*An unsolved case of the Waring problem*”. American Journal of Mathematics. The Johns Hopkins University Press. 66 (1): 137–143 (1944).

[16] M. Lothaire. “*Applied Combinatorics on Words*”, volume 105 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, (2005).

[17] J-P. Allouche, A. Glen, *Extremal properties of (epi)Sturmian sequences and distribution modulo 1*. Enseign. Math. 56, no. 3, pp. 365–401 (2010).

[18] M. Morse; G.A. Hedlund, "*Symbolic Dynamics II. Sturmian Trajectories*". American Journal of Mathematics. 62 (1): 1–42 (1940).

[19] Berstel, J.; Séébold, P., "*A remark on morphic Sturmian words*". RAIRO, Inform. Théor. Appl. 2. 8 (3–4): 255–263 (1994).

[20] K. Guy Richard (1983a) *Don't try to solve these problems!* , Amer. Math. Monthly 90 35–41 (1983),.

[21] M. Gardner, "*The curious properties of the Gray code and how it can be used to solve puzzles*". Scientific American. Mathematical Games. Vol. 227, no. 2. p. 106 August (1972)..

[22] H.M. Lucal,.. "*Arithmetic Operations for Digital Computers Using a Modified Reflected Binary*". IRE Transactions on Electronic Computers. EC-8 (4): 449–458 , December (1959).

[23] J.P. Delahaye, "La conjecture de Syracuse". Revue Pour la science. Vol. 247, p. 100-105, Mai (1998).

[24] P. Erdos. "Some unsolved problems". Michigan Mathematical Journal, 4(3) 291-300 (1957)

[25] S. Wolfram, “*A New Kind of Science*”, Wolfram Media, (2002).
<figure><img src="image_16.png" /></figure>

Hassan Douzi is a research professor in mathematics at Ibn Zohr University, Agadir, Morocco. He received his PhD in "Mathematics for decision" from the University of Paris IX Dauphine 1992. He published several research papers, essentially in Applied mathematics related to image processing, but also incidentally in Number theory and Combinatorics.