===================================== Collatz conjecture or 3n+1 Conjecture ===================================== Collatz conjecture or 3n+1 Conjecture ===================================== .. _collatz-conjecture-or-3n1-conjecture-1: Collatz conjecture or 3n+1 Conjecture ===================================== Also called Collatz conjecture, Syracuse problem, Ulam conjecture, Kakutani’s problem, Thwaites conjecture, hailstone problem. Statement --------- Pick any positive integer ``n``. Apply one rule: - If ``n`` even → divide by 2 - If ``n`` odd → multiply by 3, add 1 Each application produces a new integer. Feeding that integer through our same rule produces another. Step by step, our starting ``n`` traces a trajectory through natural numbers — each step carries our previous value forward into a new one. Our conjecture claims: every trajectory eventually lands on 1, regardless of which positive integer you picked. Example Trajectories -------------------- Starting at 6: ``6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1`` (8 steps) Starting at 7: ``7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1`` (16 steps) Starting at 27 — famous for wild behavior: ``27 → 82 → 41 → 124 → 62 → 31 → ... → 1`` (111 steps, peaks at 9,232 along our way before crashing to 1) Why “Hailstone” --------------- Plot a trajectory. Vertical axis shows value, horizontal axis shows step count. Values hop up & down wildly before crashing to 1. Resembles a hailstone rising inside a storm updraft until gravity wins. What Mathematicians Have Verified --------------------------------- Every positive integer up to 2^68 (approximately 2.95 × 10^20) has had its trajectory computed on modern hardware. Every single one lands on 1. No counterexample observed. Why No Proof Exists Yet ----------------------- Our odd-step multiplies by 3 & adds 1 — injects growth. Our even-step halves — injects shrinkage. Trajectories dance between growing & shrinking in ways nobody has yet tamed with formal proof. Paul Erdős offered $500 for a proof or disproof & commented that mathematics lacks tools strong enough for such problems. Terence Tao proved a weaker density statement in 2019 — see next section for unpacking. What Terence Tao Proved in 2019 ------------------------------- Tao’s result sounds close to our conjecture but stops short of proving it. Learning why reveals how mathematicians measure partial progress on a hard problem. **His theorem, informal:** for any function ``f(n)`` growing to infinity arbitrarily slowly (think ``log log log n`` — grows slower than molasses), almost all starting integers ``n`` have a Collatz trajectory that eventually dips below ``f(n)``. **What “almost all” means here** — a density-theoretic statement, not a universal one: - **Natural density 1** — as you scan positive integers up to ``N``, a fraction approaching 100% of them comply. Count how many integers ≤ ``N`` obey Tao’s theorem, divide by ``N``, take ``N → ∞``, get 1. - **Logarithmic density 1** — Tao’s actual formulation uses a weighted density where each ``n`` carries weight ``1/n`` (smaller integers count more). A set can hold logarithmic density 1 while still missing infinitely many integers. **Why this leaves our conjecture open:** - A set of density 0 can still contain infinitely many integers. Tao’s theorem permits an infinite sparse set of starting integers whose trajectories never reach 1 — as long as that set thins out fast enough to carry density 0. - Tao himself titled his result “almost all orbits of our Collatz map attain almost bounded values.” Two “almost”s. Neither one rules out a counterexample. - A real proof of 3n+1 must eliminate *every* potential outlier, not just show most integers comply. **Why Tao’s progress still matters:** Previous results proved weaker density bounds (e.g., natural density bounded below 1) or restricted which integers could escape. Tao’s method — borrowed from ergodic theory & probability — pushed density all our way up to 1. Going from “density 1” to “every single integer” remains our open frontier, & no one knows how wide that gap actually runs. Known Constraints on Possible Counterexamples --------------------------------------------- If some starting integer fails to reach 1, its trajectory must do one of two things: 1. Shoot off toward infinity, growing without bound 2. Fall into a cycle of length greater than our known trivial cycle ``4 → 2 → 1 → 4 → ...`` Any hypothetical non-trivial cycle must contain at least 186,265,759,595 odd terms. Nobody has ever observed such a cycle. Why 1 → 4 → 2 → 1 Doesn’t Break Our Rule ---------------------------------------- New learners spot an apparent paradox: if “reaching 1” ends our trajectory, why does our rule still produce a value when applied to 1? Applying 3n+1 to 1 gives ``3 × 1 + 1 = 4``, then ``4 → 2 → 1 → 4`` forever. Doesn’t that contradict “every trajectory halts at 1”? **Short answer:** our function stays defined on every positive integer. Our *convention* — not our *function* — declares victory when we hit 1. Mathematicians call ``4 → 2 → 1 → 4 → ...`` our **trivial cycle**. Every trajectory that ever reaches 1 enters this loop & cycles forever. By convention we stop counting steps at our first arrival at 1 because our conjecture asks “does every starting integer eventually reach 1?” — not “does our function halt?” Our function has no halt instruction. Our stopping rule sits outside our function, imposed by us, not built into our math. **What a “non-trivial cycle” would mean:** Imagine integers ``a → b → c → ... → a`` looping among themselves, never touching 1. A counterexample to 3n+1 could take exactly this shape — a set of numbers that all obey 3n+1 yet remain trapped in their own closed orbit, isolated from 1’s orbit. Example shape (purely hypothetical, none known): :: :: N → (3N+1)/2 → ... → N'' → ... → N Every single step obeys 3n+1. Every step produces another integer in our cycle. None of those integers ever equals 1. **What computer searches have ruled out:** Exhaustive computation has verified no such cycle exists with fewer than roughly 186 billion odd terms along its loop. Our trivial cycle (length 3) remains our only known cycle. But “ruled out below a huge number” ≠ “ruled out forever.” No proof eliminates non-trivial cycles at all sizes. **Putting our two options together:** If any counterexample to 3n+1 exists, it either (a) escapes to infinity or (b) lives inside a non-trivial cycle we haven’t found. Both remain mathematically possible; both remain empirically unobserved. Collapsing this gap from “unobserved” to “impossible” equals solving Collatz. Variants -------- - **5n+1 problem** — some trajectories appear to escape toward infinity. No universal funnel to 1. - **3n-1 problem** — contains multiple cycles, so no universal claim holds. - **Generalized Collatz maps** — a family of piecewise-linear integer maps with similar unresolved questions. Tiny rule changes produce wildly different landscapes. Only our specific 3n+1 rule (so far) seems to funnel every integer down to 1. Why It Matters -------------- Our conjecture crosses number theory, dynamical systems, & computational complexity. Jeffrey Lagarias called it “an extraordinarily difficult problem, completely out of reach of present day mathematics.” Simple rules produce behavior unpredictable from our rules alone — a signature of chaotic integer dynamics. John Conway showed in 1972 that certain Collatz-like generalizations land in undecidable territory — no algorithm can answer whether every trajectory terminates. Whether our plain 3n+1 itself sits in that undecidable zone remains unknown. Further Reading --------------- - Lagarias, Jeffrey C. — *The 3x+1 problem: An overview* (2010) - Tao, Terence — *Almost all orbits of the Collatz map attain almost bounded values* (2019) - Conway, John H. — *Unpredictable Iterations* (1972) License ------- Public domain. Copy, modify, redistribute freely.