I'm vaguely aware that people have proved that by starting with any number, and iterating through the Collatz algorithm one will eventually reach a number divisible by 4.
But I am looking for the proof that one will eventually reach a number divisible by 8 for every odd number n divisible by 3. This seems to be the case, for example 3→16, 9→40, etc. but I'm looking for a proof of it.
Is it logically known that this is the case? How might one go about proving that?
On
There is a bijective function for all numbers of the form $8n+5: f(n−1)\frac{1}{4}$. However, this is nonobvious except for $5→1$. Let me explain.
One can state that for every even-odd sequence $n$, sequence $4n+1$ has two extra steps. For example: 27 - 111 steps, 109 - 113 steps, 437 - 115 steps, 1749 - 117 steps, 6997 - 119 steps, 27989 - 121 steps, … $\infty$
This follows from the salient fact that each time you multiply $4n+1$ by $3n+1$ – that is, $(((n*4)+1)3)+1$ – you add two factors of $2$.
This is not immediately obvious in even-odd sequences since, given that for any such orbit (if I may call it that), the first $n$ is absent from the next sequence. Thus, for example, sequence $501$ does not have the step $125$, and sequence $125$ does not have the step $31$.
501 → 1504 →752 → 376 → 188 → 94 → 47
125 → 376 → 188 → 94 → 47
31 → 94 → 47
The apparent difficulty of the conjecture, therefore, lies in the odd numbers, such as $27$, that are not multiples of $4$ plus $1$. That’s three out of four odd sequence numbers, of course. However, we see there are two other operations – injective functions – that knit all these sequence $n$s together, too. These are:
For every $4n+3$, $f(n+1)\frac{3}{2}-1$. For example: 27→41, 31→47.
For every $8n+1$, $f(n−1)\frac{3}{4}+1$. For example: 41→31, 49→37.
If the Collatz conjecture (every sequence ends in 1 -> 2 -> 4 -> 1) is true, then starting with any odd number n >= 3 encounters a number divisible by 8.
Proof: Let n be a number that doesn't encounter a multiple of 8. Starting with n, and assuming the Collatz conjecture is true, we eventually encounter the number 1, and this happens after an operation x -> 3x + 1 gives a power 2^k, which is k times divided by 2. We assumed that 3x + 1 is not divisible by 8, so k = 1 or k = 2, and 3x + 1 = 2 or 3x + 1 = 4. This implies x = 1. So this only happens if we started the sequence with x = 1.
The same argument shows there is also an element divisible by 16 because 3x + 1 = 8 is not possible, but not necessarily one divisible by 32 since 3x + 1 = 16 is possible (starting with x = 3 -> 10 -> 5 -> 16 -> 1)
PS. I'd be curious if the same can be proven without assuming the Collatz conjecture.