Structure of 3n+1 — The Collatz Map via Pair Decomposition

Readable with high-school math + binary arithmetic

§0 Background: The Collatz Conjecture

For any positive integer n, repeat the following:

• If n is even → n ÷ 2
• If n is odd → 3n + 1

"Every starting number eventually reaches 1." This is the Collatz conjecture. Posed in 1937, it remains unsolved after nearly 90 years.

The paper asks: What is the internal structure of 3n+1? Why is x=3 special?

§1 Zipper Structure: Splitting Numbers into 2-Bit Pairs

Every positive integer can be written in binary, then split into consecutive 2-bit pairs.

The key idea is the zipper structure. Interleave m4 and m6 to reconstruct the original number:

A simpler illustration:

Any number can be split into two bit-strings m4 and m6, and zipped back together. This is the foundation of pair decomposition.

§2 Four Pair Types and GPK

A 2-bit pair has exactly 4 possible values. Each one gets a name:

This G/P/K classification comes from carry-lookahead adder design, standard in computer science since the 1960s.

§3 Inside 3n+1: Table Lookup Instead of Multiplication

3n+1 = 2n + n + 1. Here 2n is just n shifted left by 1 bit. So:

This addition can be broken down pair by pair. At each pair position, "which bits are added" is fixed, and the result is one of only 16 possibilities.

Why 16?

• Input pair type: 4 options (K, P, P, G)
• State: 4 options (see below)
• Total: 4 × 4 = 16

What is "state"?

To look up the table, you need the input pair plus a state. The state is a pair of two values:

c_in = carry coming in from the previous pair (carry in). a_i-1 = the "a" of the previous input pair (a, b). c_out = carry going out from this pair (carry out) → becomes the next pair's c_in.

Initial state = S2 (+1 provides carry in; no previous pair so upper bit = 0).
Next state is determined by the carry out and the current input pair's upper bit. The table gives it automatically.

Writing out all 16 cases gives Table 5.1 — the core of the paper.

Table 5.1: Complete scan transition table for 3n+1

This is the entire table. Every claim in this summary can be verified by reading it.

Read directly from this table:
■ Cases 13–16: G input → c_out=1 in all 4 cases (unconditional carry generation)
■ Cases 1–4: K input → c_out=0 in all 4 cases, output is never G (K→G impossible)
■ Cases 5, 10, 11: P→G — but c_out=0 in all 3 (creation does not chain)

§4 Complete Flow: n → n'

※ The flow diagram shows "n" and "n'" as integers, but the computation never needs to reconstruct the integer. The scan takes pairs in and puts pairs out. Division removes pairs and shifts boundaries. Re-pairing maps pairs to pairs. The next scan reads pairs again. The entire trajectory runs in pair form until it reaches 1. Zipping back to a number is a display operation for human readability, not part of the computation.

§5 3n+1 Is Completely "Closed"

Throughout the entire flow, pair types never leave these 4 kinds:

"Closed" does not mean all 4 types appear every time. Each step may use a different subset. But a 5th type never appears. Feed n' back into the same table → get n''. Feed n'' in again → same table. The same 4 types and the same 16-row table, forever. That is closure.

Moreover, the following properties hold without exception:

"Always" and "never" are not figurative. All 16 table entries were checked: zero exceptions.

§6 How Does 5n+1 Differ?

The same procedure builds a table for 5n+1 (= 4n + n + 1, shift = 2 bits). Comparing the two:

Both tables constructed and verified against 500 odd numbers each

§7 Why "Closed" Means "No Escape"

What growth requires

For 3n+1 to make a number larger, division by 2 must happen only once (d=1). This occurs only when the lowest pair is G(1,1).

Why only G(1,1)? — The Syracuse function maps odd → odd, so the input n is always odd. The lowest bit is always 1, which means the lowest pair can only be P(0,1) or G(1,1) (K(0,0) and P(1,0) require the lowest bit to be 0, so they never appear as the lowest pair). With P(0,1), the result 3n+1 has at least two trailing zeros (d≥2, shrinks). With G(1,1), it has exactly one trailing zero (d=1, grows).

What happens when it grows

When the lowest pair is G(1,1), the table lookup (Case 15) produces:

• Output becomes P(1,0) → the G is destroyed
• Carry c_out = 1 is generated → neighbors are affected

The cause of growth (G) always produces the carry that destroys it. There is no table entry that avoids this.

Can destroyed G come back?

Asymmetry between creation and destruction

Destruction cascades, but creation does not. This asymmetry is an algebraic fact read directly from the 16-row table.

Structural upper bound combining scan + re-pairing (net ≤ 0)

Reading Table 5.1 and Table 5.2 together, the net change of the leftmost G-block per step has a strict upper bound:

This is a worst-case bound, not an average. max(X) ≤ 0, not E[X] < 0. No configuration yields net +1.

§7.5 Why Convergence to 1 Is Structurally Inevitable

§7 showed what happens within a single scan. But can re-pairing (Table 5.2) undo everything? Three points settle the question.

1. Re-pairing does not break closure

Re-pairing outputs the same 4 pair types (all 16 cases verifiable in Table 5.2). Scan → division → re-pairing → next scan: no 5th type ever appears. The table properties from §7 (G→c_out=1, K→G impossible, P→G has c_out=0) apply equally to n' after re-pairing.

2. Consecutive d=1 has an arithmetic ceiling (Corollary 5.3)

Independent of the tables, a purely arithmetic fact:

Growth (d=1) always stops after finitely many steps. This is an arithmetic fact, independent of GPK or the tables.

3. No escape inside a finite box

Since d=1 cannot persist, the trajectory cannot diverge (it is bounded). Closure ensures that the same tables and constraints apply wherever the trajectory goes (scale invariance). The only possible terminal behavior for a bounded trajectory in a closed, scale-invariant system is a cycle. For x=3, the only structurally admissible cycle is the fixed point n=1 (§8.4).

The paper's Proposition 5.4 provides a detailed derivation from table properties: leftmost G-block consumption (net ≤ 0), dimensional separation, episode structure. The three points above are the core of that conclusion.

Observed data: trajectory of n = 670,617,279

Below is an excerpt of the full 370-step trajectory (83 episodes) for n = 670,617,279. Red rows = pair₀ is G (d=1, growth). Blue rows = pair₀ ≠ G (d≥2, collapse). Horizontal lines mark episode boundaries.

Every red band (d=1 growth burst) terminates after finitely many steps, followed by a blue band (d≥2 collapse). This pattern repeats across all 83 episodes. The leading G is born, consumed, and collapses — while GPK strings shorten toward n=1. This is §7.5's argument made visible.

§8 Big Picture: Closure → Self-Destruction → No Escape

3n+1 = 2n + n + 1 (shift = 1 bit < pair width = 2 bits)
  └→ GPK classification determined by reading the pair alone (closure)
      └→ Carry behavior is state-independent
          ├→ G unconditionally generates carry
          │   └→ That carry destroys the G itself
          ├→ K unconditionally kills carry
          │   └→ K can never become G again
          └→ The engine of growth = the agent of its own destruction. No escape.

n=1 has pair (0,1)=P, d=2, n'=1. Fixed point. All other n are structurally unable to sustain any other cycle under these constraints.

§9 This Is Not a Probabilistic Argument

A common argument: "3n+1 shrinks on average because E[d] > log₂3." But that's probabilistic, so "maybe a trajectory gets unlucky and diverges" is a valid counter.

The paper's argument operates on a different level entirely:

• G → c_out=1 is not a "tendency" — it is an identity
• K → G impossible is not "rare" — it is zero
• P → G producing c_out=0 is not "usually" — it is all cases

Net ≤ 0: structural bound vs. probabilistic tendency

The distinction is especially clear for the G-block net change (§7):

Net ≤ 0 does not mean total G decreases monotonically. New G-blocks can be born (P→G), and ÷2^d can remove non-G pairs, raising G density — even back to 100%. What net ≤ 0 guarantees is that each individual leftmost G-block has a finite lifetime: each d=1 run (growth burst) must end, and every burst is followed by d≥2 collapse.

Computational verification and structural description

Computational verification of the Collatz conjecture (e.g., confirming all trajectories up to 2⁶⁸) has made indispensable contributions — building confidence in the conjecture and confirming the absence of counterexamples. By its nature, however, each trajectory check is inductive verification within a finite space bounded by 1 on both ends, and extending it to all n faces an inherent barrier.

• Each trajectory is a finite path: n → (finitely many ups and downs) → 1
• But GPK sequences of length k have 4^k possibilities, and k has no upper bound
• Deriving "holds for all n" from finitely many checks requires a different layer of argument

Table 5.1 sits at that layer. In just 16 rows it covers every pair position of every GPK sequence, depending on neither the length nor the content of the sequence. Where computational verification "confirms the fact for each individual n," the table "describes the structure common to all n." The two are not in opposition — they illuminate the same object from different layers.

§10 Once the Table Is Built, the Conclusion Is Already Inside It

Once the scan table (Table 5.1, 16 rows) and re-pairing table (Table 5.2, 16 rows) are constructed:

The paper's Lemmas and Propositions are just verbalizations of what the tables already contain.

† Afterword

In the process of drafting this summary, the moment I asked myself whether the generational turnover of G-blocks continues infinitely, I found myself slipping directly back into the quagmire of the Collatz conjecture. My lingering feeling that the structural explanation was "not yet sufficient" was, in fact, a sign that my framework of perception had already shifted.

I realized there is a cognitive tendency in humans to revert to "individual trajectories" even when presented with a structurally closed argument. This very process of trying to verify "if it's truly so" may actually be what fuels the complexity of the problem. For those with a strong mathematical intuition, this is an irresistible trap — the ability to verify leads to the desire to do so, which reveals the trajectory, which in turn compels one to follow it. The ability itself becomes the snare. Even as I wrote this summary, my mind was repeatedly pulled back into the depths of these trajectories.

Verification scripts: dfst_final.py, dfst_properties.py
Structural comparison data: dfst_comparison_record.md
Source paper: "Pair Predicate Decomposition of Collatz-type Maps (xn+1)/2^d" v5.1 (February 2026)