An odd to odd collatiz tree
Let us divide all odd integers into three classes (mod 6):
Class A: numbers of the form `6n + 1`
Class B: numbers of the form `6n + 3`
Class C: numbers of the form `6n + 5`
For each class, generate new odd numbers using the following rules.
*Forward tree rules*
- If the number is in Class A `6n + 1`, use two operations:
Rule A1: Multiply by 4, subtract 1, divide by 3, and keep the result. It is always an odd integer:
m \mapsto \frac{4m - 1}{3}
This produces numbers of the form `8k + 1`.
Rule A2 (common rule): Multiply by 4 and add 1:
m \mapsto 4m + 1
- If the number is in Class B `6n + 3`, use only one operation:
Rule B (common rule):
m \mapsto 4m + 1
- If the number is in Class C `6n + 5`, use two operations:
Rule C1: Multiply by 2, subtract 1, divide by 3, and keep the result. It is also an odd integer:
m \mapsto \frac{2m - 1}{3}
This produces numbers of the form `4k + 3`.
Rule C2 (common rule):
m \mapsto 4m + 1
*Why the “multiply by 4 and add 1” rule is common*
For any odd number `m = 2n + 1`,
4m + 1 = 4(2n + 1) + 1 = 8n + 5
So this rule always produces numbers of the form `8n + 5`. More specifically:
If `m = 6n + 1`, then `4m + 1 = 24n + 5`
If `m = 6n + 3`, then `4m + 1 = 24n + 13`
If `m = 6n + 5`, then `4m + 1 = 24n + 21`
Together, the sets `24n + 5`, `24n + 13`, and `24n + 21` cover all numbers of the form `8n + 5`.
Also, the other two rules generate:
numbers of the form `8n + 1` (from Rule A1)
numbers of the form `4n + 3` (from Rule C1)
And the three forms `8n + 5`, `8n + 1`, and `4n + 3` together cover all odd integers.
*Example: building the odd-number tree starting from 1*
Start with 1, which is in Class A `6n + 1`, so apply both Class A rules:
From 1: `4·1 + 1 = 5`, `(4·1 − 1)/3 = 1` → 5, 1
From 5 (Class C): `4·5 + 1 = 21`, `(2·5 − 1)/3 = 3` → 21, 3
From 21 (Class B): `4·21 + 1 = 85` → 85
From 3 (Class B): `4·3 + 1 = 13` → 13
From 85 (Class A): `4·85 + 1 = 341`, `(4·85 − 1)/3 = 113` → 341, 113
From 13 (Class A): `4·13 + 1 = 53`, `(4·13 − 1)/3 = 17` → 53, 17
From 341 (Class C): `4·341 + 1 = 1365`, `(2·341 − 1)/3 = 227` → 1365, 227
From 113 (Class C): `4·113 + 1 = 453`, `(2·113 − 1)/3 = 75` → 453, 75
From 53 (Class C): `4·53 + 1 = 213`, `(2·53 − 1)/3 = 35` → 213, 35
From 17 (Class C): `4·17 + 1 = 69`, `(2·17 − 1)/3 = 11` → 69, 11
All of these rules use only linear operations (multiply, add/subtract, divide by 3) and are applied based on which mod-6 class the current odd number belongs to.
*Inverse tree rules*
Any number produced by the tree is an output, so you must first classify it into one of these forms: `8n + 5`, `8n + 1`, and `4n + 3`. Each class has a valid inverse rule:
If the number is `8n + 5`, the inverse step is: `(x − 1) / 4`
If the number is `8n + 1`, the inverse step is: `(3x + 1) / 4`
If the number is `4n + 3`, the inverse step is: `(3x + 1) / 2`
What I mean is this: if you take any odd number that appears in the tree and repeatedly apply the correct inverse rule for its category, you must eventually reach 1 by following the same path, but in reverse.
Example with 9: A forward path in the tree from 1 to 9 is:
`1 → 5 → 3 → 13 → 17 → 11 → 7 → 9`
Now reverse it using the inverse rules:
9 is `8n + 1`, so according to inverse rules it will follow the path `9 → 7 → 11 → 17 → 13 → 3 → 5 → 1`
So, in short: every number that exists in the tree should return to 1 when you apply the inverse rules, and it should return by retracing the same sequence used to generate it from 1.
Starting from 1, you can “undo” the process at any time by applying the rules in reverse to get back to 1. For example, 1 produces 1 and 5. If you undo from 1 and from 5 by reversing the forward rules, both paths must lead back to 1. Also, 5 produces 21 and 3. If you undo from 21 and from 3, both paths must lead back to 5, and then 5 must lead back to 1. This continues the same way for every number you reach.
*I will prove how repetition is impossible; every odd number generated by this tree from 1 must be different*
Every odd number produced in this expanding tree is unique (no odd number appears twice).
- *No number appears twice*
Suppose `o1 = o2` but they appear in different branches. The inverse rules are functions: for any odd number `x`, there is only one rule that applies based on its form `8n + 1`, `8n + 5`, or `4n + 3`.
If `x = 8n + 5`, the only parent is `(x − 1) / 4`.
If `x = 8n + 1`, the only parent is `(3x + 1) / 4`.
If `x = 4n + 3`, the only parent is `(3x + 1) / 2`.
Because the inverse mapping is a *well-defined function*, if `o1 = o2`, their parents must be equal, their grandparents must be equal, and so on, all the way back to the root 1. Thus, they are not in different branches; they are the same node.
Second direct proof:
Suppose during tree expansion we have reached an odd number `w`. Now we will use a rule for `w`, depending on the modulo of `w`, to obtain `x` such that `w → x`, where both `w` and `x` are odd numbers. Now let me suppose there is another different odd number `y` such that we use the tree rule on `y`, depending on its modulo. Let us suppose we create the same odd number `x`, to get a repeated odd number. Now, use the inverse rule on `x`: it must yield either `w` or `y`, not both at the same time. Therefore, it contradicts that `x` can yield both `w` and `y` when one valid inverse rule is used on `x`.
- *Why a loop is impossible inside this tree*
Assume, for contradiction, that during the expansion starting from 1 we eventually enter a loop. That would mean we reach the same number twice along one forward path, like:
`1 → … → x1 → … → x2`, with `x1 = x2`.
So we first create the value `x1` somewhere in the expansion, and later, by continuing the expansion rules, we reach the same value again `x2`. Now consider running the process backward by inverting the rules. Since `x1` was generated from 1 by forward steps, reversing those steps must take `x1` back to 1 along a specific path. Because `x2 = x1`, reversing from `x2` must follow the exact same backward path and also reach 1. Therefore, `x2` cannot be part of a loop with `x1` or that avoids returning to 1 — once you are at that value, reversing forces you back to 1. This contradicts the assumption that a loop exists: `1 → … → x1 … … → x2`. So, no loop can occur.
Why is 1 not a counterexample of the tree:
Since every odd number in the tree greater than 1 must return to 1, if 1 itself loops or goes to infinity it is a second issue, because any odd number greater than 1 must return to 1 first in the tree. It becomes the sole attractor. In this logic, 1 is not a counter but the single terminal loop that defines the entire tree's structure.
So in short, starting from 1 a loop is impossible inside this tree because every yielding odd number will create its own tree where every odd number must return to it, and that odd number must return to 1. Therefore, if any odd number is not created by 1, it is simply unreachable from 1, and using inverse rules there is no guarantee it should reach 1. So if suppose the tree contains every odd number, then using inverse rules every odd number must reach 1.
Another proof in short:
Why a loop is impossible: assume a loop exists, represented by the sequence `1 → … → a1 → b → c → a2`, where `a1 = a2`. This structure implies that all odd numbers in the chain, starting from 1 up to `c`, must eventually reach 1 when inverting the forward rules. In the inverted rule, `c` reaches 1. If `c` goes to `a2` in the forward rules, then inverting the rules means we should reach `a1`. Since `a1 = a2`, starting from `a1` we should reach `a1`, not 1. This directly contradicts our initial assumption that `a1` must reach 1.
*Inverse tree rules restated*
Let’s split all odd numbers into three non-overlapping groups:
- Numbers of the form `4n + 3`
- Numbers of the form `8n + 1`
- Numbers of the form `8n + 5`
Given any odd number `x`, apply the rule that matches its form:
If `x = 4n + 3`, compute `(3x + 1) / 2` → yields `6n + 5`.
If `x = 8n + 1`, compute `(3x + 1) / 4` → yields `6n + 1`.
If `x = 8n + 5`, compute `(x − 1) / 4` → yields `2n + 1`.
Example starting from 9: applying the rules repeatedly gives
9 \rightarrow 7 \rightarrow 11 \rightarrow 17 \rightarrow 13 \rightarrow 3 \rightarrow 5 \rightarrow 1
*Tracing from the root 1 using forward tree rules*
Here are the shortest sequences reaching every odd number up to 25:
1: `1 → 1`
3: `1 → 5 → 3`
5: `1 → 5`
7: `1 → 5 → 3 → 13 → 17 → 11 → 7`
9: `1 → 5 → 3 → 13 → 17 → 11 → 7 → 9`
11: `1 → 5 → 3 → 13 → 17 → 11`
13: `1 → 5 → 3 → 13`
15: `1 → 5 → 3 → 13 → 53 → 35 → 23 → 15`
17: `1 → 5 → 3 → 13 → 17`
19: `1 → 5 → 3 → 13 → 17 → 11 → 7 → 29 → 19`
21: `1 → 5 → 21`
23: `1 → 5 → 3 → 13 → 53 → 35 → 23`
25: `1 → 5 → 3 → 13 → 17 → 11 → 7 → 29 → 19 → 25`
Rule summary for these paths:
Rule A1 `((4m − 1)/3)`: Used to reach numbers like 17 from 13.
Rule C1 `((2m − 1)/3)`: Used to reach 3 from 5, and 11 from 17.
Common rules `(4m + 1)`: Used for jumps like 1 → 5, 3 → 13, and 5 → 21.
*Now let me show how the tree forward rules are exactly opposite of the tree inverse rules*
Here, take the outputs `8n + 1`, `4n + 3`, and `8n + 5`. Here, let me divide all `8n + 5` numbers into three sets: `24n + 5`, `24n + 13`, and `24n + 21`. Now let me make pairs: `8n + 1` and `24n + 5`. These two numbers yield `6n + 1` numbers, and you can get in the forward tree that `6n + 1` numbers yield exactly these two sets. Again, make pairs of `4n + 3` and `24n + 21`. These two sets yield `6n + 5` numbers, and again you can get in the forward tree rules that `6n + 5` numbers yield exactly the same two sets: `4n + 3` and `24n + 21`. And now `24n + 13` will yield `6n + 3` numbers. You can get in the forward tree rules that `6n + 3` numbers yield exactly the same only one set: `6n + 3`. So you can see how the tree forward rules are directly opposite to the tree inverse rules without any exception.
(Relationship with odd to odd collatiz transform):->I will now show why the inverse rules of the tree defined above are essentially equivalent to the odd-to-odd Collatz transform.
Here is what the odd-to-odd Collatz transform means:
Start with any number of the form (4n+3).
Compute (\frac{3(4n+3)+1}{2}).
If the result is of the form (8n+1), then compute (\frac{3(8n+1)}{4}).
If the result is of the form (8n+5), then subtract 1 and divide by 4. Repeat this step as many times as needed until you reach a number of the form (4n+3) or (8n+1).
Once you reach (4n+3) or (8n+1), use the rules defined above to determine the next term in the sequence.
This works because every number of the form (8n+5) eventually “merges” into a root number of the form (4n+3) or (8n+1), and which root it merges into determines the next step.
*Proof: Every `8n + 5` number reaches either `4n + 3` or `8n + 1` by repeatedly applying `(x − 1) / 4`*
Write all odd numbers in sequence:
`1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, ...`
This sequence is the union of three arithmetic progressions:
`8n + 1`, `4n + 3`, and `8n + 5`.
In the `8n + 1` and `4n + 3` sequences there are no `8n + 5` numbers. Let us list all `8n + 1` and `4n + 3` numbers in increasing order:
`1, 3, 7, 9, 11, 15, 17, 19, 23, ...`
In this sequence all `8n + 5` numbers are missing. Now consider the `8n + 5` numbers generated from each root by repeatedly applying `x ↦ 4x + 1`:
- Root 1: `1, 5, 21, 85, 341, ...`
- Root 3: `3, 13, 53, 213, ...`
- Root 7: `7, 29, 117, 469, ...`
- And so on.
These are all `8n + 5` numbers whose root is either `8n + 1` or `4n + 3`, and together they must cover all `8n + 5` numbers.
An `8n + 5` number could be missed only if it does not have a root of the form `4n + 3` or `8n + 1`.
Suppose, for contradiction, that there is at least one `8n + 5` number, call it `x`, that has no root in the form `4n + 3` or `8n + 1`.
Now apply `(x − 1) / 4` to `x` repeatedly. The sequence cannot loop, and it cannot increase toward infinity, because every new odd number obtained is less than the previous one: `(x − 1)/4 < x` for `x > 1`.
Therefore the process must terminate at the smallest odd number in the chain. Since we assumed `x` has no root of the form `4n + 3` or `8n + 1`, the chain cannot stop at those forms. The only remaining possibility is that it terminates at 1, because 1 is the smallest odd number. But 1 is of the form `8n + 1`.
Thus our assumption is false. Every `8n + 5` number, when we repeatedly subtract 1 and divide by 4, must reach a number of the form `8n + 1` or `4n + 3`. If it does not reach one of those first, it must reach 1, which itself is `8n + 1`. Therefore the claim holds.
---
*What this proves:*
The inverse rule `(x − 1)/4` on `8n + 5` always descends to a “base” odd that is either `8n + 1` or `4n + 3`.