[HN Gopher] Almost all Collatz orbits attain almost bounded values
___________________________________________________________________
Almost all Collatz orbits attain almost bounded values
Author : measurablefunc
Score : 91 points
Date : 2025-11-17 20:28 UTC (6 days ago)
(HTM) web link (mathvideos.org)
(TXT) w3m dump (mathvideos.org)
| throwaway81523 wrote:
| youtube link https://youtu.be/k-dtx8s2ehM
| tux3 wrote:
| The paper (2019): https://arxiv.org/abs/1909.03562
| noduerme wrote:
| Does this have some significance for back propagation or
| something, or is it just an interesting trick of arithmetic?
| //not that it needs to have a technical use, it's still neat.
| huhtenberg wrote:
| Hailstone numbers has been a popular subject in computing
| circles since forever. Not much practical application, just a
| very simple, but curious construct.
| robot-wrangler wrote:
| Collatz, busy-beavers, and algorithmic information theory are
| all related. To the extent they offer insight into the
| sparseness or density of irreducible complexity in the space of
| all computation.. this has many implications for what can be
| computed efficiently, what can be learned efficiently, program-
| synthesis, what can be analyzed "at a distance" without just
| trying it and potentially needing to wait forever, etc.
|
| Whether it will say anything very significant _practically_ or
| only philosophically is a different question. Maybe it is
| something like the discovery of transcendentals.. finding out
| that most of the number line won 't have a tidy algebraic
| closed-form isn't exactly a make-or-break deal for the program
| of mathematics itself, and it also doesn't matter much to
| people who are doing engineering
| ur-whale wrote:
| > Does this have some significance for back propagation or
| something
|
| You're right!
|
| What could darn possibly matter these days, in the whole
| entirety of the realm Mathematics, if it does now somehow have
| a measurable impact on backprop ?
| WhyOhWhyQ wrote:
| This guy's kid hits a homerun in the little league game and
| he bemoans that the kid is wasting his talents not working on
| backprop.
| phyzome wrote:
| Crazy how AI has infected every conversation these days.
| tromp wrote:
| The closely related function Col' which also divides 3n+1 by 2 in
| the odd case, is concisely represented by the 65-bit lambda
| calculus term l1(lll31(ll2(421)))(ll1)1(ll1) operating on Church
| numerals [1]. It starts from the pair of numbers n and 0 and then
| performs n iterations of swapping the numbers after incrementing
| the first. Its lambda diagram is
| +---------------+-- | +---------- - | - |
| +-----+---- + | + | +-+---+---- | | | | +-+
| +-+-+-- | | | | | +-+-+-+ | | | | | | +-+ | |
| | | | | | +-+ | | | | | +---+ | | |
| | +-+ | | | +---+ | | |
| +---------+ | | +-+ |
| +-+
|
| [1]
| https://github.com/tromp/AIT/blob/master/fast_growing_and_co...
| measurablefunc wrote:
| Does it terminate for all n?
| tromp wrote:
| Yes; the Col' function trivially terminates for all n, since
| Col n' is just (if odd n then 3*n+1 else n)
| `div` 2
| measurablefunc wrote:
| That's good then. It shouldn't difficult to bootstrap that
| to the full Collatz conjecture.
| tromp wrote:
| Since the Collatz conjecture is not (known to be)
| finitely refutable, we cannot encode it as a program
| whose termination decides the conjecture. If the
| existence of diverging orbits were disproven though, then
| we could.
| measurablefunc wrote:
| That's a good point & also surprising that such a simple
| dynamical process can not be proven one way or the other
| to be an instance of a terminating or non-terminating
| computation.
| im3w1l wrote:
| I thought that diagram was giving me crazy strong synaesthesia,
| but turns out it was subpixel rendering and it really did have
| color.
| anonymous2024 wrote:
| Someone has also noticed another curiosity: The number of bits of
| the biggest number (in binary notation) in a path is less than
| the number of bits of the initial number (in binary notation) * 3
| + 1
| tromp wrote:
| If that were true, then every number would lead to a cycle
| (possibly a different one from 1-4-2). It would make the
| decision problem (whether a given initial number leads to 1)
| decidable, and the Collatz conjecture finitely refutable.
| wizzwizz4 wrote:
| This isn't true. Take 9_A = 1001_2. 28_A = 11100_2, which is 5
| bits long (3 set). The biggest number in this path is 52_A =
| 110100_2, which is 6 bits long (3 set). 5 [?] 6, and 3 [?] 3:
| neither of my interpretations of your statement holds.
| taberiand wrote:
| Not to say their statement is true but I don't see any reason
| to count the initial zeroes.
|
| 11100 == 111 == 11100000000, in terms of the next odd
| iteration
|
| Even numbers don't really count in the process surely? All
| collatz does is essentially ignore those zeroes
| wizzwizz4 wrote:
| Valid point: it depends what invariants you're trying to
| construct. Considering only the odd elements of the
| sequence does yield a slightly different set of insights
| compared to other approaches. (9 / 28 / 52 still describe a
| counterexample to the proposed invariant, even in this
| scheme.)
| fhars wrote:
| There is another interpretation, reading "bits" as "set bits"
| and assuming that textual description (especially the
| operator "of the") has a higher precedence than
| multiplication, then your initial number is 9 with 2 bits
| set, and the largest number is 52 with 3 bits set, and 3 < 2
| * 3 + 1 = 7.
| anonymous2024 wrote:
| What I understood was: 9_A = 1001_2 needs 4 bits, set or not
| set as the minimum length of the binary representation. 52_A
| = 110100_2 needs 6 bits 6 bits is less than 4*3+1=13 bits
| wizzwizz4 wrote:
| At that point, the conjecture's just numerology: 27 takes 5
| bits, and 9232 takes 14 bits (two shy of 3x5+1 = 16). 27 is
| the peak of the _average_ ratio between start and maximum,
| because the +1s are so significant when the numbers are
| small: past that point, we 're relying on _extreme_ outlier
| behaviour to get each new high-score. Those only start
| showing up often enough to matter once we get into the
| thousands.
|
| Plugging in values from OEIS A006884, it looks like the
| maximum ratio between the maximum and starting values goes
| down until around 4255, then picks up again, gradually
| increasing from there. Eyeballing the growth rate, I
| suspect there's a counterexample to _this_ interpretation
| somewhere before 10^1000. (Does anyone have an element of
| A006884 greater than 2358909599867980429759? That 's 140
| bits maximum to 71 bits starting.)
| littlestymaar wrote:
| Do you have a source for that?
| exomonk wrote:
| In case people don't know the Collatz Conjecture, It's based on a
| simple rule: take any natural number n. If it is even, divide it
| by 2. If it is odd, multiply by 3 and add 1. The conjecture
| states that no matter what number you start with, you will
| eventually reach the number 1.
|
| It would seem simple, but many simple iterative calculations get
| us to Turing machine territory regarding computability.
| keepamovin wrote:
| It's like gravity, collisions, and interstellar objects. Some
| starting points escape and go on ... forever.
|
| Some kind of structure there that Collatz probing is sketching
| apetresc wrote:
| Except the Collatz Conjecture is almost certainly true, and
| there are no starting points that go on forever. Or did I miss
| the point of the analogy?
| keepamovin wrote:
| No you didn't misunderstand, I think. I thought there were
| some values that went on forever!
|
| _edit:_ however we could consider the weaker definition of
| "forever", and consider there are some outliers that go on
| "for a long time" per post title, probing structure with
| these loops and spokes. :D
| sfblah wrote:
| The conjecture is that there are no values that go on
| forever, but it's as yet unproven.
| madars wrote:
| Good background reading/watching - Terence Tao's "The Notorious
| Collatz conjecture" talk.
| https://www.youtube.com/watch?v=X2p5eMWyaFs Slides:
| https://terrytao.wordpress.com/wp-content/uploads/2020/02/co...
|
| I especially like how he highlights that Collatz conjecture shows
| that a simple dynamical system can have amazingly complex
| behavior; also 3n-1 variant has two known cycles - so "any proof
| of the Collatz conjecture must at some point use a property of
| the 3n+1 map that is not shared by the 3n-1 map." And this
| property can't be too general either - questions about FRACTRAN
| programs (of which Collatz conjecture is a special case) can
| encode the halting problem.
|
| If you haven't seen it, FRACTRAN itself is amazing -
| https://www.cs.unc.edu/~stotts/COMP210-s23/madMath/Conway87....
| and the paper is pure joy to read.
| Xcelerate wrote:
| As a non-mathematician, I'm confused why so many people think the
| conjecture (whether true or false) is provable within PA. To me,
| it seems like something that would be very nicely just right
| outside the boundary of PA's capability, sort of like how proving
| all Goodstein sequences terminate requires transfinite induction
| up to e_0. Add that to the fact that the Collatz Conjecture seems
| to fall in the same "category" of problem as the Turing machines
| that the Busy Beaver project is having a hard time proving non-
| halting behavior of, and the heuristic arguments all seem to
| point to: Collatz is independent of PA.
|
| But I'm interested in hearing the counterarguments that Collatz
| likely _is_ provable within PA and why this would be the case.
___________________________________________________________________
(page generated 2025-11-23 23:01 UTC)