# Coding: Bring the Noise

%26lt;0011 Em

## More thoughts on the Collatz Conjecture

I made a quick housekeeping sweep of the blog recently, and wanted to revisit the Collatz Conjecture.  I’m sure it’s been suggested before, but I believe there’s another method of proving the conjecture:

$Collatz(k)$ for all $k \in [2^{n}, 2^{n+1}]$ where $n \in \mathbb{Z}^+ > 2$

That is to say, we only need prove that for an n > 2, all integers between consecutive powers of 2 resolve according to the collatz conjecture.  I’m not sure where to go from there, but for instance we can show that in general:

$2^n + 1 \Rightarrow 3^{r} + 1$ where r is the number of (divisible by 3) iterations such that $n = 2r$

## Derivation:

Consider $2^n + 1$ where n > 1

First step: $2^n + 1$ must be odd, so multiply by 3 and add 1.

$3(2^n +1) + 1$

$3\cdot2^n + 4$

Second step: $3\cdot2^n + 4$ must be even, so divide by 2.

$\frac{3\cdot2^n + 4}{2}$

$3\cdot2^{n-1 }+ 2$

Third step: $3\cdot2^{n-1}+ 2$ must be even, so divide by 2.

$\frac{3\cdot2^{n-1}+2}{2}$

$3\cdot2^{n-2}+1$

We’ve gone through 3 steps.  If n = 2, we’re at 4 and we’re done.  Let’s say n is very large, so that we can go through another 3 iterations and find a pattern.

Fourth step: $3\cdot2^{n-2}+1$ is odd again, so multiply by 3 and add 1.

$3(3\cdot2^{n-2}+1) + 1$

$3^2\cdot2^{n-2} + 4$

Fifth step: Even again, divide by 2.

$\frac{3^2\cdot2^{n-2} + 4}{2}$

$3^2\cdot2^{n-3} + 2$

Sixth step: Still even, divide by 2.

$\frac{3^2\cdot2^{n-3} + 2}{2}$

$3^2\cdot2^{n-4} + 1$

The next iteration will increment the power of 3, and give us a number divisible by 4, and so on.

More generally, we’ll have:

$3^{\frac{k}{3}}\cdot2^{n-2\frac{k}{3}}+1$ for k iterations where k is divisible by 3.

Letting $r = \frac{k}{3}$ we have

$3^r\cdot2^{n-2r}+1$

When $n=2r$ we can simplify:

$3^r+1$

I’m not sure where we go from here.  The next thing I want to do is a 3d plot of iterations to resolve against the position (from 0 to 1) between $2^n$ and $2^{n+1}$ for varying n.