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 λ1(λλλ31(λλ2(421)))(λλ1)1(λλ1) 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...┬───────────────┬── │ ┬────────── ─ │ ─ │ ┼─────┬──── ┬ │ ┬ │ ┼─┬───┼──── │ │ │ │ └─┤ ┬─┼─┬── │ │ │ │ │ ┼─┼─┼─┬ │ │ │ │ │ │ └─┤ │ │ │ │ │ │ │ ├─┘ │ │ │ │ │ ├───┘ │ │ │ │ ├─┘ │ │ │ └───┤ │ │ │ └─────────┤ │ │ └─┤ │ └─┘Does it terminate for all n?
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
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.
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.
The paper (2019): https://arxiv.org/abs/1909.03562
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
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.
Do you have a source for that?
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.
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.
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
At that point, the conjecture's just numerology: 27 takes 5 bits, and 9232 takes 14 bits (two shy of 3×5+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.)
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
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.)
youtube link https://youtu.be/k-dtx8s2ehM
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.
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
Hailstone numbers has been a popular subject in computing circles since forever. Not much practical application, just a very simple, but curious construct.
Crazy how AI has infected every conversation these days.
> 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 ?
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
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?
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