Collatz Binary Residues (properties of n mod 2k)

Exploring the Collatz Conjecture on the Least Significant Bits

These notes follow three related computational projects. Walkback certificates is a method for eliminating numbers with particular binary residues from a convergence check. The other two are ways to store and calculate that process efficiently.

Frontier. At depth k, the residue classes modulo 2k not yet discharged by a sound sieve rule.

01 Walkback Certificates Remove uniformly covered residue classes. 02 Storing Residues Efficiencies over the raw storage. 03 Ternary Format Store endpoint states and share prefix work.
00Notation

Reviewing the Function

The shortcut Collatz function

T(n) = n / 2 if n is even
(3n + 1) / 2 if n is odd
Brief background on Wikipedia ↗

Affine residue endpoints

A fixed residue class has the form n₀ + 2ka. After k shortcut steps,

Tk(n₀ + 2ka) = m + 3fa

Here f counts odd steps. The endpoint is completely described by the affine pair (m, f).

Plate 1 · Refining one affine state
depth k = 2 · residue n₀ = 3 (m, f) = (8, 2) T²(3 + 4a) = 8 + 9a

Substitute a = 2a′ + b:

m + b3ᶠ = 8 + 0·9 = 8
residue 3 mod 8 · even branch (4, 2) T(8) = 8/2 = 4
even: ((m + b3f)/2, f) odd: ((3(m + b3f) + 1)/2, f + 1)
01Reduce the unresolved set

Walkback Certificates

A residue class can be removed in either of two ways: its path descends, or it merges with an already-covered path.

The two culls

01 / descent The class falls below itself.

If its affine endpoint is uniformly smaller than its starting family, earlier verification covers everything that follows. This is the familiar 2k residue sieve used by Oliveira e Silva, and Barina.

02 / merge The class joins a smaller source.

Alternatively, an affine pair could be a descendent of a uniformly smaller affine family. There are various methods to detect this situation.

Prior residue rules

Methods for finding class joins

  1. R

    Roosendaal’s deduplication removes an affine state when the same pair appeared at a shallower depth. The first collision found by this method is residue 15 at depth 6 (001111) producing the same pair (20, 4) that was produced by 7 at depth 5 (00111).

  2. A1

    Angeltveit’s path-merging sieve uses m ≡ 2 (mod 3) to detect merges. It can be extended more generally to many mod 3j where j < f in the affine pair. Though this has a cost of needing to do m mod 3j as well as pre-calculate which mod 3j values are admissible. It can detect merges earlier than the deduplication rule.

  3. A2

    Angeltveit’s odd-even-even sieve recognizes another fixed merge shape in the collatz tree. It also can detect merges earlier than the deduplication rule.

Reverse moves

Walkback searches the reverse tree

Start with (v, s) = (m, 3f). We can reverse the steps that Each admissible reverse word proposes another family v + sa that produces this affine pair.

E−1(v, s) = (2v, 2s) O−1(v, s) = ((2v − 1)/3, 2s/3) O−1 exists when v ≡ 2 (mod 3) and 3 divides s.
Plate 2 · A subset of the reverse tree and a walkback "hot path"
original class95 + 128a
shared endpointT7(95 + 27a) = 182 + 243a
selected predecessor 71 + 96a = 71 Both inequalities pass.
uniform certificate 71 < 9596 ≤ 128 71 < 95 for a = 0
The culling condition v < n₀ and s ≤ 2k

Then v + sa < n₀ + 2ka for all residues starting where least k bits = n₀.

Unification

Other merge rules are a subset of the walkback

Exhaustive walkback finds the same collisions that deduplication, mod 3j, and OEE merges find. Each asks whether an alternative branch exists and is that alternative branch smaller.

Heredity

One certificate passes to both binary children

Substitute a = 2a′ + b. The comparator becomes (v + sb) + 2sa′, preserving both inequalities for b = 0 and b = 1. Descendants remain certified, so exhaustive walkback is needed only at chosen checkpoints.

02Represent surviving residues

Surviving residues

Once a sieve has chosen the frontier, the next problem is physical: retain the survivor identities compactly enough to store, distribute, and refine them.

Storage at k = 34

A bitmap index can beat a packed residue list

An explicit list pays k bits per survivor. Barina divides the full 234-bit sieve into 64-bit words. Because only fifty words occur, each window can be a one-byte dictionary index.

Barina’s index array 234 / 64 = 228 bytes 268.4 MB, plus a 50 × 8-byte dictionary

At these approximate counts, the fixed index is 17.2 bits per deduplicated survivor. Divided by the smaller walkback frontier it would be 25.3 bits per survivor; that is a density comparison, not a claim that the fifty-word vocabulary survives the stronger cull.

Why only fifty words?

The repeated words inherit a shrinking set of positions

A sieve bit records whether a binary residue still needs to be checked. Refinement gives every surviving position two possible children. Subsequent culls only delete positions, so later 64-bit words are contained in a small collection of maximal observed words.

Plate 3 · Early survivor words
survivor removed at this refinement absent

Why residue 3 disappears at k = 4

The bitmap cull is the affine descent test from Section 00

T4(3 + 16a) = 2 + 9a

Its pair is (2, 2). Since 2 < 3 and 9 < 16, every member is below its starting value after four steps.

From one envelope to four maxima

The 64-bit survivor envelope has seven possible positions

Early refinement gives the envelope {7, 27, 31, 39, 47, 59, 63}. Aligned 64-bit windows occupy subsets of those slots. Four observed words are maximal under containment; every other observed word is contained in at least one of them.

Plate 4 · Four maximal observed survivor words
Founder A {27, 31, 47} Highlighted positions remain available in this local library.
original 64-bit envelope 1111111 four maximal descendants their contained words

Sieve-dependent vocabulary

Fifty is an observation, not a universal constant

A descent-only construction produces more words. Adding merge rules changes which descendants remain and therefore changes the vocabulary being compressed.

Local libraries

Each maximal word supplies smaller coordinates

A contained word needs presence bits only for positions in its maximal parent. The same deletion-only structure suggests a simpler representation: store child-survival edges directly.

Plate 5 · Two child-survival bits per parent
P · 11 P0 · 10 P1 · 01 P00 P01 P10 P11
00neither 10low only 01high only 11both
one refinement: 2Nk−1 bits history: Ak = 2 ∑k−1j=k₀ Nj bits
RetainedExact residue ancestry

Replay reconstructs the survivor bitmap.

Expansion costRecompute affine chains

Endpoint states must be regenerated along each surviving lineage.

03Represent endpoint states

Ternary frontier

Instead of retaining the originating residue bitmap, retain the distinct affine states (m, f). Writing m in exactly f trits reveals a local binary-to-ternary transducer and a prefix-sharing tree.

State representation

The affine intercept fits in f ternary digits

Since the endpoint is m + 3fa, 0 ≤ m < 3f. A fixed-width f-trit word stores m exactly, including meaningful leading zeroes.

state(13, 3)→word1113

Length-only cull

The coarse test needs only k and f

If verification has covered values below 2k, an f-trit endpoint is bounded by 3f. When even the largest such endpoint misses the new binary block, every state of that length is already covered.

worst-case comparison m < 3f ≤ 2k ≤ n Survivors require f ≥ ⌈k log3 2⌉.

The local rule

One token carries the next binary branch through the trits

Read most-significant trit first. Initialize token t with the new binary residue bit b. Each input trit d emits e and a new token t′.

d + 3t = 2e + t′

Digit transition · cell = (e, t′)
t \ d012
0(0,0)(0,1)(1,0)
1(1,1)(2,0)(2,1)
Across the complete word m + b3f = 2q + tf

tf = 0 → (q, f)   ·   tf = 1 → append 2 → (3q + 2, f + 1)

Worked branch

From (8, 2) to its b = 1 child

Write 8 as 223 and initialize the token at one.

  1. first 22 + 3·1 = 5 = 2·2 + 1emit 2; retain token 1
  2. second 22 + 3·1 = 5 = 2·2 + 1emit 2; retain token 1
  3. final token22 → 2223 = 26append 2; child state (26, 3)
Plate 6 · A most-significant-trit-first frontier trie
A = 2B = 1C = 0E = end
stored frontier words

Reading the state diagrams

Two tape descriptions of the shortcut process

A pass begins in S. States move right while rewriting digits; return moves left to the edge.

□ is blank. x → y, R means read x, write y, move right.

Plate 7 · Two tape-machine descriptions

Packed implementation

Five trits fit in one byte

Since 35 = 243 < 256, a byte can hold any five-trit chunk. Two incoming-token tables need 486 entries.

35 = 243five trits / byte
Plate 8 · A packed five-trit lookup
input chunk · most-significant first
incoming token
lookup address0 × 243 + 121121 of 486 entries
packed result02020₃ → byte 60outgoing token t′ = 1
Shared workProcess a prefix once for all descendants.

The next most-significant-trit-first tree can be built directly from the current tree.

ImplementationDirect digit arithmetic is currently faster.

Packed chunks remain useful for storage even when lookup is not the fastest transition method.

Trade-offThe state tree forgets its originating residues.

Recovering them requires reverse reconstruction or retained parent links.

ΣComparison

Three projects, two meanings of smaller

Only walkback changes the unresolved mathematical set. The other two projects deal with representation.

ProjectObject reducedResidue identityExpansion
WalkbackUnresolved classesPreservedReverse search at checkpoints
Word dictionariesRepeated survivor wordsPreserved in bitmapRegenerate endpoints
Child archiveRefinement-tree edgesPreserved directlyReplay lineages
Ternary frontierEndpoint-state representationLost unless linkedTransform shared prefixes

References

Tomás Oliveira e SilvaStopping-time computations

Eric Roosendaal archive ↗

Residue sieve and joined paths
David BarinaVerification through 2⁷¹ and compressed sieves Vigleik AngeltveitPath-merging and odd-even-even sieves Stérin & WoodsCollatz as binary-to-ternary conversion