u/jonseymourau

I know that this video is not directly related to Collatz but I thought I'd post a link to it anyway because it is about mod 4 and mod 8 arithmetic and mod 8 arithmetic does have a lot of relevance to Collatz (without claiming that it is the whole story - it is not)

Of relevance is the key result that numbers of the form 4^a.(8b+7) cannot be expressed as a sum of three squares. If we restrict ourselves to odd numbers, then all odd numbers that can be expressed as (8b+7) cannot be expressed as a sum of 3 squares and all other odd numbers can be.

So, these odd numbers that admit a partitioning as a sum of 3 squares can expressed generically as:

8t+r = 8t+2s+3 = a^2+b^2+c^2 , where r=3+2s and s is in {-1,0,1}

If we subtract 3 from each side we get:

8t+2s = 2(4t+s) = (a-1)(a+1) + (b-1)(b+1) + (c-1)(c+1)

The LHS is divisible by 8 iff s = 0 and also (I think) iff a,b,c are all odd

Now, I haven't found any implications of this identity that is useful for Collatz, but I thought I would throw it out there anyway, just in case it piques someone else's interest or curiosity.

I did some "thinking in public" in comments of an earlier post and I wanted to consolidate what my current thinking is with this post.

The insight detailed below is that you can always represent an individual Collatz path as a state machine with M states, provided M=2^k is greater than the odd peak of the path - this is simply because in this case the odd residues mod M are simply the Collatz terms themselves and they will never wrap.

You can even use fewer states, provided you resync at each 5 mod 8 node and provided the modulus, M, you chose doesn't induce any obstructions (here denoted H) which imply that M is too small.

I should make clear that FSM result here isn't particularly useful for solving Collatz. The reasons are multiple:

- to derive the sufficient FSM, you need to have calculated the odd peak of the full Collatz orbit
- to derive the reduced FSM, you then need to test each term according to a proposed reduced M to see if reduction is possible

Another way of thinking of it is as N deterministic state machines, driven only by source residues, connected by the 5 mod 8 nodes that join them.

This work doesn't help to show that every 5 mod 8 node is connected to another 5 mod 8 node that indirectly connects to 1 which is ultimately what is required to prove Collatz.

But, i think it does help to illustrate how far you can get with FSM models of Collatz and where the limitations are. For a path that reaches 1 you can construct an FSM that models that path exactly. In some cases, you can even create a more compact FSM, provided you are willing to do resyncing at each 5 mod 8 node, but you can't do either without assuming the orbit converges to 1 in the first place, so it is certainly no substitute for a proof.

I also more clearly describe "the tape machine model" where the state machine is not calculating Collatz but acting as a verifier of a tape that has a sequence printed on it using a small log₂(M) bit register to track the mod M states as they pass under the tape head. The machine halts and catches fire if it detects a variation from the expected state.

---
The tape machine model

The machine we have in mind is not computing the Collatz sequence — it is verifying it. Imagine the sequence is already printed on a read-only tape. The machine has a single register of log₂(M) bits, holding the current odd term mod M, and a precomputed transition table of size M.

The table maps each source residue r mod M to a predicted destination residue (the next odd term mod M). The machine knows nothing else — it does not compute 3n+1, it does not calculate valuations, it does not inspect anything beyond the current register value and the next symbol on the tape.

At each step:

1. Look up the current register value r in the table to get the predicted next odd residue r'.
2. Read the next odd term from the tape and take its residue mod M.
3. If the residue matches r', update the register and continue.
4. If it doesn't match — the machine halts and catches fire.

That's the entire machine: a log₂(M)-bit register, a fixed lookup table, and a read-only tape. A run that completes without fire — reaching the terminal state 1 mod M — is a verification that the table correctly describes the path. The machine is non-trivial precisely because it can catch fire, and catching fire is meaningful.

When does the table make a wrong prediction?

Some source residues mod M uniquely determine the next odd residue mod M; others don't. The size of the table M is what determines which residues are predictive and which aren't.

• At mod 8: residue 3 mod 8 always predicts next odd = 1 mod 8 (unique). Residue 7 mod 8 predicts next odd is 3 or 7 mod 8 (two options — not unique at mod 8 but deterministic at mod 32). Residue 1 mod 8 and 5 mod 8 are wide open at mod 8.
• At mod 32: every 1 mod 8 source residue now uniquely predicts its destination mod-8 class. Most 5 mod 8 residues also narrow down considerably. But one residue — 21 mod 32 — remains a wildcard: it cannot predict its destination at this scale.

The wildcard residue is always the exceptional state r_k = (M²−1)/3 mod M. As M grows it migrates: 5 → 21 → 85 → 341 → … Only 1 in 4 of the 5 mod 8 residues at each scale remains a wildcard; the rest become fully predictive.

The high-edge condition

For source residues 3 and 7 mod 8, the next odd is (3n+1)/2. If the source residue mod M is ≥ 2M/3, the destination wraps above M — two different true successors can share the same destination residue mod M but diverge at the next step. The table cannot distinguish them, so it makes the wrong prediction and the machine catches fire.

This is the only failure mode for 1, 3, 7 mod 8 source residues at large enough M. High edges from 1 mod 8 and 5 mod 8 source residues don't cause fires — those nodes always map their successors to smaller values, staying within the same realm.

Collatz is then equivalent to: for every odd n, there exists a finite M such that the path n→1 never takes a high edge from a 3 or 7 mod 8 node at modulus M.

Two kinds of source-residue determinism

At each odd node on the tape, the table makes two predictions from the source residue alone:

1. What is the destination residue mod M? (fully determined, partially determined, or wildcard)
2. What mod-8 class does the next odd land in? (may be determined by a coarser residue)

At mod 8:

• 3 mod 8: destination mod-8 class = 1, uniquely. Fully determined.
• 7 mod 8: destination mod-8 class = {3, 7}. Partially determined.
• 1 mod 8: destination mod-8 class fully open.
• 5 mod 8: destination mod-8 class and distance both open.

At mod 32, every 1 mod 8 source residue uniquely determines its destination mod-8 class. For 5 mod 8:

• 5 mod 32, 13 mod 32, 29 mod 32: destination constrained to 1 or 2 classes.
• 21 mod 32: wildcard — destination and distance both unresolved at this scale.

5 mod 8 nodes as sync points

The wildcard residue at each scale is always 5 mod 8. Rather than treating this as a blocker, we use 5 mod 8 nodes as synchronisation points: when the machine encounters a 5 mod 8 source residue, it reads the tape until the next odd term appears and re-initialises the register with that term's residue mod M directly from the tape. No table lookup, no prediction, no fire risk — just a register reload.

Since 8 | M always, the machine identifies 5 mod 8 nodes from the register alone. The table only needs to make correct predictions for 1, 3, 7 mod 8 source residues between consecutive sync points, and the only failure mode there is the high-edge condition.

Theorem — M > peak(n) is sufficient

The odd peak must be 1 or 5 mod 8 — 3 and 7 mod 8 nodes always map strictly upward and can never be the peak.

When M > peak(n), every 3 or 7 mod 8 node x on the path has its successor also on the path, hence ≤ peak(n) < M. Therefore (3x+1)/2 < M, giving x < (2M−1)/3 < 2M/3. No high edges. No fires. QED.

Empirically verified (n = 3..499): in every case where the sync criterion permits a smaller M than the peak-based bound, the two-level machine completes without fire and matches the true path exactly. No fires observed.

Correction to the earlier conjecture

I previously conjectured M = 2^(2m−1) where m is the number of 5 mod 8 nodes. This is false — only ~10% of tested paths satisfy it. That n=761 case does match for the reduced m=4, M=2*4-1 is coincidental.

What is actually true

M > peak(n) is provably sufficient. The two-level machine can often do better: start from M > peak(n), then reduce M while no 1, 3, or 7 mod 8 node takes a high edge.

The fundamental limitation

None of this proves Collatz from scratch — you need to traverse the trajectory to find the peak first. But the tape-verification model gives a clean characterisation of the minimal machine for any known path.

This paper explains why all the odd mod-8 residues, except 5 mod 8 have deterministic edge transition functions - that is, they depend only on the residue of the source state. 5 mod 8 states are unique because the next state is is determined by v2(3n+1)%8

It also shows how as you raise the nodulus to 32 or 64, the exception residue transitions from 5 to 21.

In fact, in general, a residue is determined by the source residue r iff 2^(v2(3r+1)+1)|M wnere M is the modulus in question.

Ultimately this is because 1,5,21,85,341 etc are approximations of the p-adic integer -1/3 (that is all integers who end with trailing bit sequence ...(01)^k)

What this means that is that Collatz graph has quite a unique structure - each 16 md 24 node has predecessors all of which are 5 mod 8. The edges between.5 mod 8 nodes are completely determined by the 5 mod 8 residue of S(a) where a is the source 5 mod 8 node and b is the next 5 mod 8 node - all the "randomness" of the Collatz graph is located entirely in the 2-adic valuation of the (3b+1) where b is the target node of a 5 mod 8 -> 5 mod 8 edge.

One practical implication of this is that each such edge can be represented by an affine function that maps a to b. Many different node pairs (a,b) will share the affine function that depends only on the pairty sequence that maps a to b, what makes it unique is S(a), which depends on the valuation 3a+1. The result of applying that function is b, e.g b = edge(S(a))

It likely that this work isn't completely novel and may be duplicative of G. J. Wirsching's work but I need to do more research to check.

I just had an insight in a comment that I think is worth highlighting in caps.

The reason why Steiner sentence analysis is an extremely powerful technique for Collatz Graph analysis is simply this - it puts the problematic 5 mod 8 at the end of the sentence where it can't cause any trouble (because you are never evaluating it!)

Analysis of a Steiner sentence is exact - the transition probabilities are exact. All the randomness of the Collatz graph arises entirely in v2(8t+5) - everything else is just arithmetic.

In a recent paper I proposed that Steiner sentence lengths vary according to 1/2^k but found that empiracally they very by 1/3.(3/4)^k This paper used the mod-8 state machine to derive the emprically observed frequency from first principles.

Proves that Steiner sentences in the Syracuse graph have length distribution P(sentence length=k)=3k−1/4k for all k≥1. A Steiner sentence is the maximal sequence of Steiner circuits between consecutive nodes ≡5(mod8); each circuit in the sentence is a Steiner word.

The proof requires no ergodic theory and no appeal to the Collatz conjecture. It rests on two classical arithmetic facts: the exact Syracuse transition matrix mod 8 (rows 1 and 5 are uniform via gcd(3,2j)=1; rows 3 and 7 have forbidden transitions forced by mod-16 arithmetic), and a structural invariant d3=d7 (equal weight on residue classes 3 and 7 in the surviving distribution) that is preserved unconditionally by the matrix. Given d3=d7, the surviving mass decays by exactly 3/4 per step, yielding the formula.

Appendix A provides complete empirical validation: 10^5 sentences sampled uniformly over [1,10^15], chi-squared tests (naive (1/2)k: χ2≈106, rejected; theory: χ2=12.9, p=0.61, consistent), and figures on both linear and log scales. Supersedes Paper 65.

ps: u/Successful-Owl1778 - this is a more complete answer to why bother with mod-8 state machines :-)

Proves that the 2-adic valuation v2(3n+1) under the Syracuse map is exactly determined — or has an exactly determined expectation — by nmod8: classes 1, 3, 7 have constant valuations 2, 1, 1 (pointwise, for every n); class 5 has exact expected valuation 4 (under natural density), proved via gcd(3,2j)=1 and the tail-sum formula.

A corollary is the balance identity c1+c3+c5+c7=8, whose multiplicative form 34/28=(3/4)4 shows the geometric mean of the four asymptotic contraction ratios 3/2cr equals 3/4 — the same 3/4 that governs the sentence length distribution of Paper 67.

Also proved: the full distribution P(v2(3n+1)=j∣n≡5(mod8))=1/2j−2 for j≥3 (Proposition 4.1). All results machine-verified in Lean 4/Mathlib by the Aristotle automated proof assistant.

This paper goes a long way to explaining the asymmetry noted in this recent post that generated a lot of discussion.

Following on from recent posts about the mod-8 state machine and the single-circuit transition diagram, this paper presents a full empirical investigation of branch length statistics in the Steiner circuit graph, along with a structural explanation of the result.

---

Setup

A Steiner circuit branch is a maximal sequence of consecutive Steiner circuits along an orbit, terminating at the first circuit whose exit value is ≡ 5 (mod 8). The branch length k is the total number of circuits, including the terminal one.

Branches match the regular language: one or more repetitions of (7*3)?1, followed by a terminal (7*3)?5.

Sampling: 100,000 branches were drawn by choosing random t uniformly in [1, 10^15], setting n = 8t+5, and following the orbit until the next 5 mod 8 exit. The starting point n itself is not counted.

---

What the paper shows

The naive geometric prediction fails decisively. The 1 and 5 exits look superficially symmetric in the mod-8 state machine, suggesting P(k) = (1/2)^k. A chi-squared test rejects this with chi-squared ≈ 454,000.

The data fit P(k) = (1/3)(3/4)^k with high precision. A chi-squared test is consistent with this distribution.

What the fitted coefficients tell us:

• Proved (Lemma 2.2): The 3-node splits 50/50. For n = 8a+3, S(n) ≡ 1 (mod 8) iff a is odd iff n ≡ 11 (mod 16). Exactly half of all 3 mod 8 values satisfy this.

• Observed: The decay rate 3/4 implies each circuit terminates the branch with effective probability 1/4. The within-branch entry state distribution is measured empirically: entry via 1, 3, 7 mod 8 each ~31%; entry via 5 mod 8 ~6% (structurally suppressed — 5-exits terminate branches by definition).

• Open problem: Why does the measured within-branch entry distribution produce an effective termination probability of exactly 1/4? This is the structural question that a first-principles proof would need to answer.

• Conjectured (Conjecture 5.1): The distribution P(k) = (1/3)(3/4)^k is exact.

---

What the paper does NOT prove

The distribution formula P(k) = (1/3)(3/4)^k is a conjecture, not a theorem. It depends on Conjecture 5.2 (uniform entry-state distribution), which remains unproved. No claim is made about convergence of the Collatz sequence.

---

Context

This is part of a speculative results stream (papers numbered 64+k) running alongside the main rigorous programme (papers 32+k). The speculative stream presents empirical observations and structural conjectures explicitly labelled as such. All claims are clearly marked as empirical or conjectural throughout.

This post picks up the thread from:

• The mod-8 state transition diagram for a single Steiner circuit — where the 2/3 exit bias and the naive (1/2)^k prediction were first discussed
• Empirical fit — frequency of Steiner circuit sentence length — where the (1/3)(3/4)^k result was first observed

---

Working paper notice

This is a working paper in the speculative stream. Results and conjectures are subject to revision. The empirical observations are reproducible; the conjectural status of the main formula is clearly stated.

PDF: https://wildducktheories.github.io/collatz/papers/65-branch-distribution/65-branch-distribution.pdf

This paper formalises and extends ideas I've posted here over the past week into a single coherent framework. It is the architectural foundation of a larger four-paper programme on the Collatz conjecture.

---

What the paper proves

The mod-8 step taxonomy. Every odd integer n falls into one of four residue classes mod 8, each with completely determined successor structure under the Syracuse map S(n) = (3n+1) / 2^v2(3n+1):

• n ≡ 1 (mod 8): exits to all odd residues mod 8
• n ≡ 3 (mod 8): exits only to 1 or 5 (mod 8), with a 50/50 split determined exactly by whether n ≡ 11 (mod 16)
• n ≡ 5 (mod 8): exits to all odd residues mod 8
• n ≡ 7 (mod 8): exits only to 3 (mod 8)

Steiner circuits. A Steiner circuit is a maximal run of the form (OE)^(α-1) OEE+ — one complete "excursion" through the Syracuse map. The paper proves that:

• Every Steiner circuit is described by exactly two parameters (α, β) where α = v2(n+1) and β = v2(3n+1)
• The 7-run length theorem: a run of consecutive 7 mod 8 terms has length exactly v2(n+1) - 2

The mod-24 adjacency table. For each of the 12 odd residues mod 24, the paper derives the exact parametric form of S(24a+r) and its residues mod 8 and mod 24. This fully characterises the arithmetic structure of the Syracuse map at mod-24 resolution.

Mod-24 parity-prefix completeness. The mod-24 stratum of n completely determines whether its Steiner circuit has a bare prefix or a 7*3 leader.

---

What the paper does NOT prove

The regular expression conjecture — that the language

((7*3)?(1|5))*

over the alphabet {1, 3, 5, 7} characterises all odd Collatz orbits — is stated as Conjecture 5.1. The structural argument is laid out in detail, but the proof is deferred to a later revision of this paper. No claim is made that this constitutes a proof of the Collatz conjecture.

The 5 mod 8 overlay tree structure is described but its full properties are deferred to revisions of this paper or later papers.

---

Context

This supersedes my earlier post A Regular-Language and Tree Representation of Odd Collatz Dynamics and incorporates the mod-24 universe diagram from this post, the compressed circuit notation from this post, and the regex itself first claimed in this post.

---

Working paper notice

This is a working paper. Results, notation, and structure are subject to revision. Proved results are clearly distinguished from conjectures throughout.

PDF: https://wildducktheories.github.io/collatz/papers/33-architecture/33-architecture.pdf

In a previous post I described a regex that could match Steiner circuits. That notation was:

(7*3)?(1|5)

With any odd Collatz path being a repetition of that basic pattern.

Here is a notation that captures the same thing, using an exponential notation that captures the precise identity of the Steiner circuit in its exponents.

7^{α-2}3^{α-1}1^{2-β}5^{β-1} 

where:

α = o
β = e-o

{ n^k } means k repeats of n, k >0
{ n^k } means {} when k <= 0

The cool thing about this is that it encodes the mod 8 character of each element of the Steiner circuit.

So:

OEE -> 1
OEOEE-> 31
OEEE -> 5
OEEEE -> 5^2
OEOEOEE -> 731

My claim is that you can describe a Collatz graph entirely where the (interesting*) nodes of in-degree 2 are 5 mod 8 and edges are strings of Steiner circuits expressed with this notation. This is the overlay graph described previously. The leaves of this graph are all 0 mod 3. If you delete the (1,1) edge and the Collatz conjecture is true, then the graph is a tree. If the Collatz conjecture is false the graph has multple disconnected components.

By interesting*, I mean fully recursive. Other nodes have branches, but one of them leads immediately to an 5 mod 8 node and the other leaves straight to a 0 mod 3 - extended recursion of the (reverse) walk in the Collatz graph only happens via 5 mod 8 nodes.

I am preparing a paper that describes this more fully, but that's the basic idea.