The Collatz Map in Binary · Sam Schlesinger

The Collatz map is defined by

c(x) = \begin{cases} x/2 & x \text{ even} \\ 3x + 1 & x \text{ odd,} \end{cases}

and the Collatz problem asks: does every positive integer, iterated under $c$ , eventually reach the trivial cycle $4 \to 2 \to 1$ ?

Nobody knows. But the problem changes texture if you stop thinking of $c$ as arithmetic on numbers and start thinking of it as an operation on binary strings. Division by two, the part that feels dynamical, becomes trivial, and everything interesting concentrates in a single carry chain.

Seven

Start with seven. In binary it is $111$ : three ones, nothing else. Everything that follows is an operation on this string.

The odd branch

Seven is odd, so the map adds the string to a copy of itself shifted up one place, with a carry seeded at the bottom. The sum always ends in a zero, which falls off immediately. That takes $111$ to $1011$ , then $1011$ to $10001$ . The string is getting longer.

Stripping zeros

One more odd step takes $17$ to $26$ , an even number at last. The even branch does no arithmetic at all: the trailing zero, marked in red, is simply deleted, and what remains is $1101$ , thirteen. In binary, halving is not dynamics, it is deletion.

Shrinking

From $13$ the odd branch gives $20$ , which is $10100$ : two zeros at the bottom this time. Both vanish at once and the string collapses to $101$ , five. The string only shrinks when zeros reach the bottom edge.

Reaching one

Five is odd, and one more carry chain produces $8$ , which is $1000$ . Three trailing zeros, three deletions, and we land on $1$ . The deletions win, this time.

The open question

That is the whole game: the odd branch grows the string and stirs it with carries, while the even branch deletes zeros off the bottom. For seven, the deletions won after five odd steps. Nobody has ever found a starting value that escapes, and nobody has proved that none does.

An accelerated map

First, compress the boring steps. Let $\nu_2(x)$ be the exponent of the largest power of two dividing $x$ , and define

d(x) = \begin{cases} x / 2^{\nu_2(x)} & x \text{ even} \\ (3x+1)/2 & x \text{ odd.} \end{cases}

This is the standard “accelerated” Collatz map: it does all consecutive halvings at once (note $3x + 1$ is always even when $x$ is odd, so the odd branch can safely include one halving).

In binary, the even branch is not arithmetic at all. Dividing by $2^{\nu_2(x)}$ just deletes the trailing zeros from the representation. Writing bits least-significant first, the even case is “strip leading 0s”: pure string surgery.

So all the depth of the Collatz problem lives in the odd branch. What does $(3x+1)/2$ do to a bit-string?

Unpacking the odd branch

Write an odd $x$ as a list of bits, least significant first, so $x = 1 : x_1 : x_2 : x_3 : \cdots$ (the first bit is 1 because $x$ is odd). Since $3x + 1 = (2x + 1) + x$ , and $2x + 1$ in this representation is just 1 : x (shift left, set the low bit), we have

(3x+1)/2 \;=\; \mathrm{tail}\,\big(\mathrm{add}(x,\; 1 : x)\big),

where add is ordinary binary addition. Here is the addition algorithm, bits-first, with an explicit carry; maj is the majority function that decides when a carry propagates:

add :: [Bool] -> [Bool] -> [Bool]
add xs ys = adder xs ys False
  where
    adder (x : xs) (y : ys) c = (x ⊕ y ⊕ c) : adder xs ys (maj x y c)
    adder []       (y : ys) c = (y ⊕ c)     : adder [] ys (y && c)
    adder (x : xs) []       c = (x ⊕ c)     : adder xs [] (x && c)
    adder []       []       True  = [True]
    adder []       []       False = []

    maj x y z = fromEnum x + fromEnum y + fromEnum z >= 2
    x ⊕ y     = x /= y

Now run adder on $x$ and $1 : x$ by hand. The two inputs are the same string, offset by one position, so bit $k$ of the sum combines $x_k$ , $x_{k-1}$ , and the incoming carry. The first additions look like:

\begin{aligned} \text{bit } 0 &: \; 1 \oplus 1 \oplus 0 = 0, && \text{carry } 1 \\ \text{bit } 1 &: \; x_1 \oplus 1 \oplus 1 = x_1, && \text{carry } \mathrm{maj}(x_1, 1, 1) = 1 \\ \text{bit } 2 &: \; x_2 \oplus x_1 \oplus 1, && \text{carry } c_2 = \mathrm{maj}(x_2, x_1, 1) \\ \text{bit } k &: \; x_k \oplus x_{k-1} \oplus c_{k-1}, && \text{carry } c_k = \mathrm{maj}(x_k, x_{k-1}, c_{k-1}). \end{aligned}

Bit 0 of the sum is 0; that is the guaranteed factor of two, and the $\mathrm{tail}$ deletes it. What remains is the new odd-branch output:

d(x)_k \;=\; x_{k+1} \oplus x_k \oplus c_k, \qquad c_{k+1} = \mathrm{maj}(x_{k+1}, x_k, c_k), \qquad c_0 = 1.

What this buys you

Seen this way, one step of the accelerated Collatz map is:

XOR the string with itself shifted by one, perturbed by a carry that ripples from the bottom, then
strip the trailing zeros that the XOR produced.

The $3x+1$ mystery is gone; in its place is a question about how a self-similar carry chain interacts with zero-stripping. An output bit is 0 exactly where $x_{k+1} \oplus x_k = c_k$ : where the string’s disagreement with its own shift matches the incoming carry. Zeros at the bottom of the string get deleted and the number shrinks; everywhere the carry chain and the shift pattern fail to cancel, ones survive and the number stays large.

That is the Collatz problem restated: does this carry process always eventually manufacture enough cancellation at the bottom of the string that the deletions win? Phrased over bit-strings it looks less like dynamics and more like a problem about a one-dimensional cellular automaton. No closer to solved, but a much stranger and more concrete thing to stare at.