The original Collatz function is very simple, consisting of only two branches, odd and even branches:
C(n) = 3n + 1 | if n is odd
C(n) = n/2 | if n is even
Since we know that 3n + 1 is always even when n is odd, we can just divide by 2 on the first branch. That's what Terras does:
T(n) = (3n + 1)/2 | when n is odd
T(n) = n/2 | when n is even
What I'll show next is the further reducing circuit like Terras did. However, since v₂ isn't independent, we can't manipulate it through parametrization.
Here is what Syracuse does:
S(n) = (3n + 1)/2ᵛ
where v = v₂(3n + 1)
And then Steiner comes in. If 3n + 1 can be divided by 2 once and repeated for an amount h times (Steiner uses the letter k, but I prefer h, which means the height of the 2-adic valuation), then the result will be partially in the form of a geometric series:
F(n) = [3ʰn + (3⁽ʰ⁻¹⁾ + 3⁽ʰ⁻²⁾2 + ... + 3·2⁽ʰ⁻²⁾ + 2⁽ʰ⁻¹⁾)] / 2ʰ
By the geometric series formula:
F(n) = [3ʰ(n + 1) - 2ʰ] / 2ʰ
F(n) = 3ʰ((n + 1)/2ʰ) - 1
F(n) = (3/2)ʰ(n + 1) - 1
where h = v₂(n + 1)
Since n + 1 needs to have v₂ = h, then n + 1 must be in the form 2ʰc, which gives us
n = 2ʰc - 1
with some odd c that fulfills this condition.
This form captures how many rising steps occur before it falls by division by 2ᵛ, where
v = v₂(3ʰc - 1).
We can manipulate this to find a number with the "height" larger and larger by choosing the value of h in n = 2ʰc - 1 through parametrization.
A Generalized version was already discovered and written by u/gonzomath in this post.
Suppose we have a set D, C, and N of sequences of the Collatz function:
Divergent, Cycle, and Normal (where Normal means that the sequence eventually collapses to another cycle).
To prove the conjecture, we need to prove (all of this is in terms of natural-number inputs):
C is impossible to exist except for 1 → 2 → 1
D is impossible to exist
Every N collapses to C = {1, 2}
Since N depends on D and C, it doesn't affect our proof whether N is infinite (well, it can easily be proven) or not.
To prove whether D exists or is impossible to exist, we need to guarantee that there is always a method for reducing the sequences of a number n ∈ D, like Terras, Syracuse, and Steiner did.
To guarantee C, we have Steiner's method using Baker's Theorem. And again, it was already posted by u/gonzomath here and it also has great progress.
My idea is: assume there exist D and C.
D = {n₀, n₁, .....} which has infinitely many members.
C = {n₀, ..., nₛ}, where s is the size of the set, and when we apply the Collatz function, it goes back to n₀.
Since D exists:
When we use the Terras function, what we do is simply reduce the sequences to be like this:
D = (T₀, T₁, T₂, ....)
where T = {a, b} and b = a/2.
When we use the Steiner function, we reduce D to a collection of subsets R, where
R = {odd, even, odd, even, ..., odd, even}
followed by several even numbers, so:
D = {R₀, e₀, e₁, ..., R₁, ......}
Suppose we have a general formula for reducing its own result. Then the general formula should be:
G(n) = G(R, e₀, e₁, ..., eᵢ)
The problem is that each Steiner block also needs to be passed through the Syracuse reduction. In particular, after applying the Steiner reduction with height h, we obtain something of the form n = 2ʰc - 1
and the result of the corresponding block is F(n) = 3ʰc - 1.
Syracuse then requires us to determine how many factors of 2 this result contains: v = v₂(3ʰc - 1).
Therefore, the recursion has to handle both the Steiner parameter h and the resulting Syracuse valuation v. In other words, G must not only describe how the sequence is grouped into Steiner blocks, but also determine the amount of 2-adic reduction that follows each block.
So I am looking for a general reduction:
G(n) = G(h, v) or, more explicitly, a function that takes a Steiner block and automatically determines the corresponding Syracuse step.
G²(n) = G(G(n))
...
Gⁱⁿᶠⁱⁿⁱᵗʸ = G(...G(n))
If the set is a cycle, then there exists some i where Gⁱ·ᵏ(n) goes back to the first element.
If it is divergent, then for every i, Gⁱ(n) always produces a new number.
If there is no D and no C (other than 1 → 2 → 1), then
Gⁱⁿᶠⁱⁿⁱᵗʸ = 1.
Any idea how to find this recursion?