Interactive Companion · Collatz Map · August 2026
A finite quotient of the Collatz dynamics, drawn in its own metric. Every node below is an odd residue class modulo 2M; every edge is a step of the map that some integer in the class can take. Laid out 2-adically, the graph's coset structure becomes visible geometry — and so does the reason no such finite graph can rule out cycles.
Collapse the even steps of the Collatz iteration and the dynamics live on odd integers under the accelerated map
U(x) = (3x+1) / 2a(x), a(x) = v2(3x+1),
where v2 is the 2-adic valuation. The exponent a(x) is
determined by x mod 8, which partitions the odd integers into three families:
D = {4n+3} with a = 1,
B = {8n+1} with a = 2, and
C = {8n+5} with a ≥ 3 — the spikes,
where deep powers of two divide out at once. These three colors are the only colors on this page.
Fix a modulus 2M and an exponent cap max_a = K+3. The graph
GK,M has a node for each odd residue r mod 2M and
an edge r → s whenever some integer x ≡ r with
a(x) ≤ max_a has U(x) ≡ s. The key point is that this graph is
nondeterministic: knowing x mod 2M determines
U(x) only modulo 2M−a, because the division by
2a consumes a bits. So each node has not one successor but a
full coset of 2a of them — the top a bits of the target
are free, fixed by bits of x the residue never saw. Any genuine cycle of integers
with exponents ≤ max_a projects to a directed cycle here; that is the sense in
which the graph could, in principle, exclude cycles — if it were acyclic.
GK,M with K = 7
(max_a = 10). Each node's out-edges land on one 2-adic coset; in bit-reversed
ordering a coset is a contiguous arc, so fan width is the exponent. Switch to natural
ordering to see the same graph without its metric.Hover over any node. A teal node (family D, a = 1) throws a
tight fan of 2 targets; a violet node (B, a = 2) a fan of
4; a coral spike sprays 8, 16, 32 or more. The inspector under the
circle shows why: the target residues agree in their low M−a bits and differ
freely in the top a — one congruence class, drawn as one arc. This works
because the nodes are placed in bit-reversed order, which makes 2-adically close
residues neighbors on the circle: distance on the circle approximates distance in
ℤ2. In the natural (archimedean) ordering, the identical edge set
collapses into an undifferentiated chord tangle. The comparison is the point: this object has a
geometry, and it is not the geometry of the number line.
There is a second picture, complementary to the circle: plot the exponent
a(x) = v2(3x+1) over consecutive odd x. Families
D and B lay down a baseline of 1s and 2s;
family C contributes the isolated tall excursions — a spike
train. Its shape is the most familiar object in elementary number theory, the division-by-two
(“ruler”) pattern: since x ↦ 3x+1 is a 2-adic isometry, the
valuation landscape it produces is the classical one, merely shifted in phase. Heights
≥ k occupy a single residue class mod 2k and thin out
dyadically.
≥ 5 and the
inspector prints its tower decomposition
Lc(n) = 4j·Lσ−j(c)(m).
The marked spike at x = 53 (height 5) is the same object as a 32-edge fan of the
node 53 in the circle of §2–3 at M = 7: spike height there is fan
width here.The correspondence between the two pictures is exact. A spike of height a in
this train is, reduced mod 2M, a node of out-degree
2a in the graph — one coset, one arc. Height in one
representation is width in the other; and the fans are precisely what the deterministic
shortcut of §5 throws away.
If GK,M were acyclic away from the fixed point at 1, bounded-exponent
Collatz cycles would be excluded. It is nowhere near acyclic. At every modulus tested the graph
has one giant strongly connected component containing all but a vanishing sliver of nodes
— the gray stragglers, which are exactly the residue classes whose exponent exceeds
max_a (they emit no edges under the cap) together with the nodes stranded behind
them, (M−9)·2M−12 in all for K = 7:
| M | nodes | giant SCC | outside |
|---|---|---|---|
| 11 | 1,024 | 1,023 | 1 |
| 12 | 2,048 | 2,045 | 3 |
| 13 | 4,096 | 4,088 | 8 |
| 14 | 8,192 | 8,172 | 20 |
| 15 | 16,384 | 16,336 | 48 |
| 16 | 32,768 | 32,656 | 112 |
| 17 | 65,536 | 65,280 | 256 |
| 18 | 131,072 | 130,496 | 576 |
| 19 | 262,144 | 260,864 | 1,280 |
| 20 | 524,288 | 521,472 | 2,816 |
There is a tempting shortcut here, and it is wrong. Treat each residue as an integer, give it
the single successor U(r) mod 2M, and the resulting deterministic
graph really is acyclic at these parameters. But that graph omits edges a genuine cycle would
use: an actual integer's successor residue is only pinned down modulo
2M−a, and the deterministic quotient silently picks one of the
2a candidates. Its acyclicity is an artifact of thrown-away fan width
— each fan above is exactly what it discards. The sound graph is the nondeterministic one,
and the sound graph is recurrent. Full statements, proofs, and the wider program are in the
paper [1].
Everything on this page is computed in your browser from the definitions above — the
graph, the strongly connected components, the layout. The same construction as a standalone
script, residue_graph.py, lives in the repository [3]. Generate the table
with: python3 residue_graph.py --sweep 7 11 20