For the sequence
\begin{align}
a_0&\in\mathbb{N}+1=\{1,2,3,\dots\}\\
a_{k+1}&= \left\{
\begin{array}{rl}
a_k \div 2 & \quad2\mid a_k \\
3a_k+1 & \quad2\nmid a_k
\end{array}
\right.
\end{align}
the Collatz conjecture states that
\begin{equation}
\forall\,a_0\,\exists\,k\ \text{such that}\ a_k=1
\end{equation}
The goal of this page is to make the Collatz sequence's mapping easier to think about. The lowest-context, longhand formulation is in binary. Repeatedly:
- Remove trailing 0s (removes factors of 2 until odd)
- Append 1 to the end of the number (\(=2a_k+1\))
- Add the result to the previous number (\(=3a_k+1\))
111 7
1111
10110 11
10111
100010 17
100011
110100 13
11011
101000 5
1011
10000 1
The rows in this method correspond to steps on odds, with evens grouped
into removed columns. The process can also be rephrased in order to be
convenient for a state-machine instead of manual computation. Above, the
result depends on the (hidden) carry from the previous digit, the digit
from step 1, and the digit from step 2. In an adder, the carry is the
result's overflow from modulo 2, but step 2 can be hidden by changing the
carry to mean the overflow plus the input digit. In this case, only the
number and carry are being added and the carry is 0, 1, or 2, starting
with 1 from the 1 appended in step 2.
While base 2 simplifies division, base 3 simplifies the addition. Dividing by 2 in base 3 is most familiar as long division, where the remainder switches between 0 and 1 at each 1 digit in the input. If the input ends with a remainder, appending a 1 to the input accounts for \(3a_k + 1\) and appends a 2 to the output. Below, in the text format for the base 3 process, digits with an incoming remainder are denoted by an underline. In contrast to base 2, the rows in this version correspond to steps on evens, with steps on odds adding columns.
Using \(a_0=\) \(=\) \(_2=\) \(_3\)
collatz(-new)*.