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

HAL
open science

# A Small Collatz Rule without the Plus One

Knight Kevin

► To cite this version:

Knight Kevin. A Small Collatz Rule without the Plus One. 2023. hal-04080486

HAL Id: hal-04080486

https://hal.science/hal-04080486

Preprint submitted on 10 May 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
# A Small Collatz Rule without the Plus One

Kevin Knight<fnref n="1" />

The Collatz rule takes odd $n$ to $(3n+1)/2$ and even $n$ to $n/2$. Understanding the dynamics of the iterated Collatz rule is a longstanding challenge. A generalized Collatz rule consists of $d$ conditions instead of two, taking each integer of the form $n \equiv i \pmod d$ to new value $(a_i n + b_i)/d$. In 1972, Conway showed that the trajectories of certain such rules, even without the “+b,” can simulate arbitrary computations. In 2002, Monks constructed a 1,021,020-condition rule (also without the “+b”) to simulate the behavior of the Collatz rule. The current paper presents and analyzes a smaller construction with only 30 conditions.

**Keywords:** number theory

## 1 Introduction

The famous Collatz rule has two frequently-used variations.

$$C(n) = \begin{cases} n/2, & \text{if } n \text{ is even;} \\ 3n + 1, & \text{if } n \text{ is odd.} \end{cases} \qquad T(n) = \begin{cases} n/2, & \text{if } n \text{ is even;} \\ (3n + 1)/2, & \text{if } n \text{ is odd.} \end{cases}$$

Iterating these rules yields interesting sequences, for example:

$$C(n): \begin{array}{l} 7 \to 11 \to 34 \to 17 \to 52 \to 26 \to 13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \\ \to 4 \to 2 \to 1 \to 4 \to 2 \to 1 \dots \end{array}$$

$$T(n): \begin{array}{l} 7 \to 11 \to 17 \to 26 \to 13 \to 20 \to 10 \to 5 \to 8 \to 4 \to 2 \to 1 \to 2 \to 1 \dots \end{array}$$

The Collatz conjecture posits that every positive integer eventually reaches 1 under either rule. The conjecture has been verified for all $1 \le n \le 10^{20}$ (Barina, 2021) but has not yet been proven or refuted.

## 2 Main Result

The following rule $K(n)$ simulates the Collatz $C(n)$ rule. We present it in the spirit of other simple devices that compute Collatz trajectories, such as de Mol's tag system (de Mol, 2008), Korec's cellular automaton (Korec, 1992), and Yolcu's rewrite system (Yolcu et al., 2021).

<footnote n="1">¹ Threeven Labs</footnote>
$$K(n) = \begin{cases} (375/2)n, & \text{if } n \equiv 2 \text{ or } 8 \pmod{30}; \\ (125/2)n, & \text{if } n \equiv 0 \pmod{30}; \\ (5/3)n, & \text{if } n \equiv 3, 9, 15, 21 \text{ or } 27 \pmod{30}; \\ (2/5)n, & \text{if } n \equiv 5, 10, 20 \text{ or } 25 \pmod{30}; \\ (3/4)n, & \text{if } n \equiv 4, 6, 12, 16, 18 \text{ or } 24 \pmod{30}. \end{cases}$$

Like rules by Conway (1972) and Monks (2002), $K(n)$ simplifies Collatz trajectories by eliminating the “+1,” which is a source of difficulties for analyzing Collatz dynamics. $K(n)$ works on trajectory terms coded as powers of two. Here, it simulates the $C(n)$ trajectory $3 \to 10$:

$$ \boxed{2^3 = 8} \rightarrow 1500 \rightarrow 93750 \rightarrow 5859375 \rightarrow 9765625 \rightarrow 3906250 \rightarrow 1562500 \\ \rightarrow 625000 \rightarrow 250000 \rightarrow 100000 \rightarrow 40000 \rightarrow 16000 \rightarrow 6400 \rightarrow 2560 \rightarrow \boxed{2^{10} = 1024} $$

## 3 Background

Conway (1972) situated the Collatz rule within a class of generalized Collatz rules that take the form

$$G(n) = \begin{cases} (a_0n + b_0)/d, & \text{if } n \equiv 0 \pmod{d}; \\ (a_1n + b_1)/d, & \text{if } n \equiv 1 \pmod{d}; \\ \vdots & \\ (a_{d-1}n + b_{d-1})/d, & \text{if } n \equiv d-1 \pmod{d}. \end{cases}$$

When $d = 2$, $a_0 = 1$, $b_0 = 0$, $a_1 = 3$, and $b_1 = 1$, $G(n)$ implements the Collatz rule $T(n)$. Conway also constructed a generalized Collatz rule that can mimic the computation of a universal Turing machine. The strong computational power of certain generalized rules may explain why the Collatz conjecture is so difficult to resolve.

Conway's universal rule did not require the “+b,” being of the simpler form

$$G'(n) = \begin{cases} (a_0n)/d, & \text{if } n \equiv 0 \pmod{d}; \\ (a_1n)/d, & \text{if } n \equiv 1 \pmod{d}; \\ \vdots & \\ (a_{d-1}n)/d, & \text{if } n \equiv d-1 \pmod{d}. \end{cases}$$

Monks (2002) constructed an ingenious generalized Collatz rule—also without “+b”—that simulates the Collatz rule itself. Monks proposed to study the Collatz dynamics in this simpler setting.

Both Conway and Monks presented their generalized Collatz rules in a more compact rule format called Fractran (Conway, 1987). Monks' rule is

$$(\frac{1}{11}, \frac{136}{15}, \frac{5}{17}, \frac{4}{5}, \frac{26}{21}, \frac{7}{13}, \frac{1}{7}, \frac{33}{4}, \frac{5}{2}, \frac{7}{1}).$$
The rule is interpreted as follows: if $n$ is divisible by 11, replace $n$ by $(1/11)n$; otherwise, if $n$ is divisible by 15, replace $n$ by $(136/15)n$, and so on.

To simulate the Collatz rule, each number in a Collatz $T(n)$ trajectory (e.g., $7 \to 11$) is coded as a power of 2 (e.g., $2^7 \to \dots \to 2^{11}$). Monks' Fractran rule is then applied to numbers of this form; other prime factors serve as registers for intermediate computations.

$$ \begin{align*} \boxed{2^7} & \to 2^5 3^1 11^1 \to 2^5 3^1 \to 2^3 3^2 11^1 \to 2^3 3^2 \to 2^1 3^3 11^1 \to 2^1 3^3 \to 3^3 5^1 \to 2^3 3^2 17^1 \\ & \to 2^3 3^2 5^1 \to 2^6 3^1 17^1 \to 2^6 3^1 5^1 \to 2^9 17^1 \to 2^9 5^1 \to \boxed{2^{11}} \to 2^9 3^1 11^1 \to 2^9 3^1 \\ & \to \dots \to \boxed{2^{17}} \to \dots \to \boxed{2^{26}} \to \dots \to \boxed{2^1} \end{align*} $$

The Collatz conjecture is equivalent to the proposition that every integer $2^m$ ($m \in \mathbb{N}$) eventually reaches $2^1$ under Monks' rule.

The “if-then-otherwise” action of any Fractran rule can be expanded into a generalized Collatz rule. Monks sets

$$ d = \text{lcm}(11, 15, 17, 5, 21, 13, 7, 4, 2) = 1021020 $$

which implies conditions like

$$ M(n) = \begin{cases} 92820n/1021020, & \text{if } n \equiv 0 \pmod{1021020}; \\ 7147140n/1021020, & \text{if } n \equiv 1 \pmod{1021020}; \\ \dots & \\ 7147140n/1021020, & \text{if } n \equiv 1021019 \pmod{1021020}. \end{cases} $$

Simplifying reveals the correspondence with Monks' Fractran rule:

$$ M'(n) = \begin{cases} (1/11)n, & \text{if } n \equiv 0 \pmod{1021020}; \\ (7/1)n, & \text{if } n \equiv 1 \pmod{1021020}; \\ \dots & \\ (7/1)n, & \text{if } n \equiv 1021019 \pmod{1021020}. \end{cases} $$

# 4 Simulating Collatz Trajectories

The new rule $K(n)$ from Section 2 is much smaller, with only 30 conditions. This section explains its action.

**Theorem 4.1.** *The rule $K(n)$ simulates the Collatz rule $C(n)$.*

**Proof:** The logic of $K(n)$ is straightforward. $K(n)$ uses three registers (2, 3, 5) to keep track of the computational state. To simulate $C(n)$ on start term 1, $K(n)$ uses 6 steps.
$$2^1 \xrightarrow[\frac{375}{2}]{\frac{375}{2}} 3^1 5^3 \xrightarrow[\frac{5}{3}]{\frac{5}{3}} 5^4 \xrightarrow[\frac{2}{5}]{\frac{2}{5}} 2^1 5^3 \xrightarrow[\frac{2}{5}]{\frac{2}{5}} 2^2 5^2 \xrightarrow[\frac{2}{5}]{\frac{2}{5}} 2^3 5^1 \xrightarrow[\frac{2}{5}]{\frac{2}{5}} 2^4$$

To simulate $C(n)$ on any odd term $2m + 1$ ($m \ge 1$), $K(n)$ uses $8m + 6$ steps. It starts by repeatedly decrementing the exponent of 2 by one while incrementing the exponent of 5 by three:

$$ \begin{array}{l@{\hspace{2em}}r} 2^{2m+1} \rightarrow 2^{2m+1-1}3^15^3 & 1 \text{ step of } (375/2) \\[1ex] \rightarrow 2^{2m+1-2}3^15^6 \rightarrow \dots \rightarrow 3^15^{6m+3} & 2m \text{ steps of } (125/2) \\[1ex] \rightarrow 5^{6m+4} & 1 \text{ step of } (5/3) \\[1ex] \rightarrow 2^15^{6m+4-1} \rightarrow 2^25^{6m+4-2} \rightarrow \dots \rightarrow 2^{6m+4} & 6m+4 \text{ steps of } (2/5) \end{array} $$

Finally, $K(n)$ uses $3m$ steps to simulate $C(n)$ on any even term $2m$ ($m \ge 1$). It begins by decrementing the exponent of 2 by two while incrementing the exponent of 3 by one.

$$ \begin{array}{l@{\hspace{2em}}r} 2^{2m} \rightarrow 2^{2m-2}3^1 \rightarrow 2^{2m-4}3^2 \rightarrow \dots \rightarrow 3^m & m \text{ steps of } (3/4) \\[1ex] \rightarrow 3^{m-1}5^1 \rightarrow 3^{m-2}5^2 \rightarrow \dots \rightarrow 5^m & m \text{ steps of } (5/3) \\[1ex] \rightarrow 5^{m-1}2^1 \rightarrow 5^{m-2}2^2 \rightarrow \dots \rightarrow 2^m & m \text{ steps of } (2/5) \end{array} $$

Here, $K(n)$ uses $5^m$ as a stopover, instead of transiting directly from $3^m$ to $2^m$—under the latter approach, upon encountering $2^a3^b$, $K(n)$ would not know whether to decrement the exponent of 2 or increment it. Also, it is fortuitous that the $(5/3)$ condition can be reused for different purposes. When processing odd terms, it puts the $+1$ in $3n + 1$; for even terms, it transits from $3^m$ to $5^m$.

Now we must show that the $K(n)$ classes modulo 30 encode the correct computational state. From the above trajectories, we see eight expressions that must be distinguished from one another: $2^{2a+1}$, $2^a3^b5^c$, $3^b$, $2^a3^b$, $2^a5^c$, $2^a$, $3^b5^c$, and $5^c$. Using tables for $2^n$, $3^n$, and $5^n$ mod 30, we calculate possible classes (modulo 30) for these expressions.

$$ \left| \begin{array}{ccccc|cc|cc} 2^{2a+1} & 2, 8 & 2^a 3^b 5^c & 0 & 3^b & 3, 9, 21, 27 & 2^a 3^b & 6, 12, 18, 24 \\ 2^a 5^c & 10, 20 & 2^{2a} & 4, 16 & 3^b 5^c & 15 & 5^c & 5, 25 \end{array} \right| $$

Because the classes are distinct, $K(n)$ can specify the correct action to take in each case. $\square$

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

# 5 Matthews-Watts Conjecture

The Matthews-Watts conjecture (Matthews, 2010) provides another reason to study rules without “+b,” beyond their simplicity. A generalized Collatz rule is defined as *contracting* if $a_0a_1 \cdots a_{d-1} < d^d$, and *expanding* if $a_0a_1 \cdots a_{d-1} > d^d$. The conjecture states that under a contracting rule, all start integers reach one of a finite number of cycles. Since the rule $T(n)$ is contracting, the Matthews-Watts conjecture suggests that no start numbers diverge to infinity under the Collatz dynamics.
The intuition behind the Matthews-Watts conjecture is that if each branch of a contracting rule is taken with equal frequency, then trajectories will trend downward. Surprisingly, the conjecture does not refer at all to a rule's `+b` parameters, which are presumed irrelevant to the ultimate fate of start numbers.

The 30-condition rule $K(n)$ is not a true generalized Collatz rule, because $(3/4)n$ in the fifth condition cannot be rewritten as $(a_4n + b_4)/30$. A 60-condition variation suffices:

$$ K'(n) = \begin{cases} 11250n/60, & \text{if } n \equiv 2, 8, 32, 38 \pmod{60}; \\ 3750n/60, & \text{if } n \equiv 0, 30 \pmod{60}; \\ 100n/60, & \text{if } n \equiv 3, 9, 15, 21, 27, 33, 39, 45, 51, 57 \pmod{60}; \\ 24n/60, & \text{if } n \equiv 5, 10, 20, 25, 35, 40, 50, 55 \pmod{60}; \\ 45n/60, & \text{if } n \equiv 4, 6, 12, 16, 18, 24, 34, 36, 42, 46, 48, 54 \pmod{60}. \end{cases} $$

Is $K'(n)$ a contracting rule, according to the Matthews-Watts conjecture? This question turns out to be inapplicable, because the conjecture only applies when $a_0a_1 \cdots a_{d-1}$ is co-prime with $d$, which is not the case with $K'(n)$.

Ignoring the co-prime requirement allows us to engineer rules whose conditions are invoked with unequal frequencies. For example, the trajectories of $K'(n)$ contain very few numbers of the form $n \equiv 2 \pmod{30}$ compared to numbers of the form $n \equiv 15 \pmod{30}$, and possibly no numbers of the form $n \equiv 1 \pmod{30}$, depending on how the unspecified conditions are handled.

Conway (1987) exploits this unequal-frequency capability to create powerful rules with arbitrary looping and testing. Of course, not all such rules yield Turing-equivalent power. Even the simple $C(n)$ generates more even terms than odd terms and is thus not subject to the Matthews-Watts conjecture; $3n + 1 = (6n + 2)/2$ and $gcd(6, 2) > 1$. Of course, $C(n)$ could still turn out to have Turing power, in which case the Collatz conjecture and the Matthews-Watts conjecture would both be false.

# 6 Cycles

The trivial Collatz cycle 1-2-4-1 has a trajectory of length 15 under the $K(n)$ rule: $2^1 = 2 \rightarrow 375 \rightarrow 625 \rightarrow 250 \rightarrow 100 \rightarrow 40 \rightarrow 2^4 = 16 \rightarrow 12 \rightarrow 9 \rightarrow 15 \rightarrow 25 \rightarrow 10 \rightarrow 2^2 = 4 \rightarrow 3 \rightarrow 5 \rightarrow 2^1 = 2$. The rule's coefficients are used in this manner:

$$ 2^1 \cdot \frac{375}{2} \cdot \frac{5}{3} \cdot \frac{2}{5} \cdot \frac{2}{5} \cdot \frac{2}{5} \cdot \frac{2}{5} \cdot \frac{3}{4} \cdot \frac{3}{4} \cdot \frac{5}{3} \cdot \frac{5}{3} \cdot \frac{2}{5} \cdot \frac{2}{5} \cdot \frac{3}{4} \cdot \frac{5}{3} \cdot \frac{2}{5} = 2^1. $$

If a Collatz cycle starts at $n$, then $2^n \cdot p = 2^n$, where $p = 1$ is a product of fractions drawn from the set $\{\frac{375}{2}, \frac{125}{2}, \frac{5}{3}, \frac{2}{5}, \frac{3}{4}\}$, with repeats. The shortest list of such fractions is

$$ \frac{125}{2} \cdot \frac{5}{3} \cdot \frac{5}{3} \cdot \frac{2}{5} \cdot \frac{2}{5} \cdot \frac{2}{5} \cdot \frac{2}{5} \cdot \frac{3}{4} \cdot \frac{3}{4} = 1. $$

However, no trajectory uses these particular fractions in any order; consider that $(125/2)$ is only employed directly after $(375/2)$. So $p = 1$ is a necessary condition for a cycle, but not a sufficient one.
We follow Monks by investigating the possible combinations of fractions used in a cycle. Suppose $(375/2)^a(125/2)^b(5/3)^c(2/5)^d(3/4)^e = 1$. Then $2^{d-a-b-2e} 3^{a+e-c} 5^{3a+3b+c-d} = 1$, which means

$$ 
\begin{aligned}
d & - a - b - 2e = 0 \\
a & + e - c = 0 \\
3a & + 3b + c - d = 0.
\end{aligned}
 $$

This system of equations is solved by

$$ 
\begin{aligned}
b &= e/2 - 3a/2 \\
c &= a + e \\
d &= 5e/2 - a/2.
\end{aligned}
 \qquad (1) $$

By inspecting the action of $K(n)$, we can assign interpretations to the variables. For example, $K(n)$ processes an even number $n$ by applying $(3/4)$ some $n/2$ times. Therefore, $e$ is half the sum of all even numbers in a Collatz cycle.

**Theorem 6.1.** The rule $K(n)$ takes $\frac{5}{2}m$ steps to simulate a $C(n)$ cycle, where $m$ is the sum of even terms in the cycle.

**Proof:** Because $e$ is half the sum of the even numbers in the cycle, $m = 2e$.

$$ 
\begin{aligned}
a + b + c + d + e &= a + (e/2 - 3a/2) + (a + e) + (5e/2 - a/2) + e \\
&= 5e = \frac{5}{2}m.
\end{aligned}
 $$

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

This implies that the length of every $K(n)$ cycle is a multiple of 5. Also, because $e = \frac{a+b+c+d+e}{5}$, the $(3/4)$ branch of $K(n)$ is taken 20% of the time during any cycle, neither more nor less than its “fair share.”

By further inspecting $K(n)$, we note that $a$ counts the number of odd terms in the cycle, while $b$ is the sum of odd terms minus the count of odd terms. Letting $m_1 \cdots m_k$ be the terms of any Collatz cycle, we rewrite Equation 1:

$$ 
\begin{aligned}
b &= e/2 - 3a/2 \\
2(a + b) + a &= e \\
2 \sum_{\text{odd } m_i} m_i + \sum_{\text{odd } m_i} 1 &= \frac{1}{2} \sum_{\text{even } m_i} m_i \\
\sum_{\text{odd } m_i} (2m_i + 1) &= \frac{1}{2} \sum_{\text{even } m_i} m_i.
\end{aligned}
 $$

This is a well-known property of $C(n)$ cycles. For the trivial $1-2-4-1$ cycle, we have $2(1)+1 = \frac{1}{2}(2+4)$.
References

D. Barina. Convergence verification of the Collatz problem. *The Journal of Supercomputing*, 77:2681-2688, 2021.

J. H. Conway. Unpredictable iterations. In *Proceedings of the 1972 Number Theory Conference Held at the University of Colorado, Boulder*, pages 14–18. University of Colorado, 1972.

J. H. Conway. Fractran: A simple universal programming language for arithmetic. In T. M. Cover and B. Gopinath, editors, *Open Problems in Communication and Computation*, pages 4–26. Springer, 1987.

L. de Mol. Tag systems and Collatz-like functions. *Theoretical Computer Science*, 390:92–101, 2008.

I. Korec. The $3x + 1$ problem, generalized Pascal triangles, and cellular automata. *Math. Slovaca*, (42): 547–563, 1992.

K. R. Matthews. Generalized $3x+1$ mappings: Markov chains and ergodic theory. In J. Lagarias, editor, *The $3x+1$ Problem: The Ultimate Challenge*, pages 79–104. American Mathematical Society, 2010.

K. Monks. $3x + 1$ minus the +. *Discrete Mathematics & Theoretical Computer Science*, 5:47–54, 2002.

E. Yolcu, S. Aaronson, and M. J. H. Heule. An automated approach to the Collatz conjecture. In *Proceedings of the International Conference on Automated Deduction*, pages 468–484, 2021.